二叉树的定义与C++实现

        树，是有限节点的集合。生活中的树是树根在下面，数据结构中的树的根在顶部，如下图：

        公司的人员组织架构，董事长，总经理，副总。。。，这种模型可以用二叉树表示，还有一些压缩算法也用到了树结构。

树的几个概念

（1）度：有几个直接的孩子，例如，A的度是3，它有BCD三个孩子，B的度是2，它有EF两个孩子，度为0的节点也就是叶子节点（终端节点）

（2）祖先：E的祖先是B,A , 从当前节点一直往上找

（3）叶子节点：下面的一层称为叶子节点，也可以称为终端节点。

（4）根：非叶子节点。

（5）树的深度，如下图

 （6）森林：不交叉的几棵树在一起称为森林

二叉树

       所有节点的度都小于等于2的树称为二叉树。下面这几种都可以称为二叉树

1、二叉树的遍历

       3种遍历方式，根据根节点的位置，分为前序，中序，后序。

                                                                               前序：根左右，ABC

                                                                              中序 ：左根右, BAC

                                                                        后序遍历：左右根, BCA

       例如下面这颗二叉树

          从根节点A在结果中的位置也可以看出是那种遍历方式。

2、二叉树的存储结构

     （1）顺序存储，类似于数组，例如下面这颗二叉树，在数组中的存储是：3561972

       数组存储时，如果节点不存在就用0表示，例如下面的，在数组中就是35019

        顺序存储可以作为一种特殊形式，有相关需求时可以采用，

     （2）链式存储，这是二叉树最好的存储形式，用一个结构体表示节点，有数据成员，指向左子树的指针，指向右子树的指针。

        

3、满二叉树与完全二叉树

       完全二叉树的定义：如果二叉树的深度为h, 除h层外，其它各层的节点数都达到最大数，且第h层的所有节点都连续集中在最左边，这种二叉树称为完全二叉树。

       

      

C++实现二叉树

     下面介绍如何用数组和链表，例如实现下面这颗树

  基于数组的二叉树实现 

  头文件TreeArray.h

/*

用数组实现二叉树

*/

#pragma once

//节点的插入方向
enum DIRECTION
{
	LEFT,
	RIGHT
};

class TreeArray
{
public:
	TreeArray(int size, int *pRoot);    //构造创建树
	~TreeArray();           //销毁树

	int *SearchNode(int nodeIndex);
	bool AddNode(int nodeIndex, DIRECTION dirc, int *pNode);
	bool DeleteNode(int nodeIndex, int *pNode);
	void TreeTraverse();    //遍历树

private:
	int *m_pTree;
	int m_iSize;    //树的容量
};

   TreeArray.cpp

#include "TreeArray.h"
#include 

using namespace std;

TreeArray::TreeArray(int size,int *pRoot)
{
	if (size > 0)
	{
		m_iSize = size;
		m_pTree = new int[size];

		for (int i = 0; i < size; i++)
		{
			m_pTree[i] = 0;
		}

		m_pTree[0] = *pRoot;
	}
	else
	{
		m_iSize = 0;
		m_pTree = nullptr;
	}
}

TreeArray::~TreeArray()
{
	if (m_pTree != nullptr)
	{
		delete[] m_pTree;
		m_pTree = nullptr;
	}
}

int * TreeArray::SearchNode(int nodeIndex)
{
	if (nodeIndex < m_iSize && m_pTree >= 0)
	{
		if (m_pTree[nodeIndex] == 0)  //0表示空节点
		{
			return nullptr;
		}
	}
	else 
	{
		return nullptr;
	}

	return &m_pTree[nodeIndex];
}

bool TreeArray::AddNode(int nodeIndex, DIRECTION dirc, int * pNode)
{
	if (nodeIndex < 0 || nodeIndex >= m_iSize)
	{
		return false;
	}

	if (m_pTree[nodeIndex] == 0)
	{
		return false;
	}

	if (dirc == LEFT)
	{
		int insertId = nodeIndex * 2 + 1;
		if (insertId >= m_iSize)
		{
			return false;
		}

		if (m_pTree[insertId] != 0)
		{
			return false;
		}

		m_pTree[insertId] = *pNode;
	}
	else if (dirc == RIGHT)
	{
		int insertId = nodeIndex * 2 + 2;
		if (insertId >= m_iSize)
		{
			return false;
		}

		if (m_pTree[insertId] != 0)
		{
			return false;
		}

		m_pTree[insertId] = *pNode;
	}

	return true;
}

bool TreeArray::DeleteNode(int nodeIndex, int * pNode)
{
	if (nodeIndex < 0 || nodeIndex >= m_iSize)
	{
		return false;
	}

	if (m_pTree[nodeIndex] == 0)
	{
		return false;
	}

	*pNode = m_pTree[nodeIndex];
	m_pTree[nodeIndex] = 0;
	return true;
}

void TreeArray::TreeTraverse()
{
	for (int i = 0; iAddNode(1, RIGHT, &node4);

	int node5 = 900;
	int node6 = 700;
	pTree->AddNode(2, LEFT, &node5);
	pTree->AddNode(2, RIGHT, &node6);

	//遍历
	pTree->TreeTraverse();

	//查找
	int *pValue = pTree->SearchNode(3);
	cout index == nodeIndex)
	{
		return this;
	}

	Node *temp = NULL;
	if (this->pLChild != NULL)
	{
		if (this->pLChild->index == nodeIndex)
		{
			return this->pLChild;
		}
		else
		{
			temp = this->pLChild->SearchNode(nodeIndex);
			if (temp != NULL)
			{
				return temp;
			}
		}
	}

	if (this->pRChild != NULL)
	{
		if (this->pRChild->index == nodeIndex)
		{
			return this->pRChild;
		}
		else
		{
			temp = this->pRChild->SearchNode(nodeIndex);
			if (temp != NULL)
			{
				return temp;
			}
		}
	}

	return NULL;
}

void Node::DeleteNode()
{
	if (this->pLChild != NULL)
	{
		this->pLChild->DeleteNode();
	}
	if (this->pRChild != NULL)
	{
		this->pRChild->DeleteNode();
	}
	if (this->pParent != NULL)
	{
		if (this->pParent->pLChild == this)
		{
			this->pParent->pLChild = NULL;
		}
		if (this->pParent->pRChild == this)
		{
			this->pParent->pRChild = NULL;
		}
	}

	delete this;
}

void Node::PreOrderTraversal()
{
	cout index pLChild->PreOrderTraversal();
	}
	if (this->pRChild != NULL)
	{
		this->pRChild->PreOrderTraversal();
	}
}

void Node::MiddleOrderTraversal()
{

	if (this->pLChild != NULL)
	{
		this->pLChild->MiddleOrderTraversal();
	}

	cout index pRChild->MiddleOrderTraversal();
	}
}

void Node::LastOrderTraversal()
{
	if (this->pLChild != NULL)
	{
		this->pLChild->LastOrderTraversal();
	}

	if (this->pRChild != NULL)
	{
		this->pRChild->LastOrderTraversal();
	}

	cout index SearchNode(nodeIndex);
}

bool Tree::AddNode(int nodeIndex, DIRECTION direction, Node *pNode)
{
	Node *temp = SearchNode(nodeIndex);
	if(temp == NULL)
	{
		return false;
	}
	
	Node *node = new Node();
	if(node == NULL)
	{
		return false;
	}
	node->index = pNode->index;
	node->data = pNode->data;
	node->pParent = temp;

	if(direction == LEFT)
	{
		temp->pLChild = node;
	}

	if(direction == RIGHT)
	{
		temp->pRChild = node;
	}

	return true;
	
}

bool Tree::DeleteNode(int nodeIndex, Node *pNode)
{
	Node *temp = SearchNode(nodeIndex);
	if(temp == NULL)
	{
		return false;
	}

	if(pNode != NULL)
	{
		pNode->data = temp->data;
	}

	temp->DeleteNode();
	return true;
}

void Tree::PreOrderTraversal()
{
	m_pRoot->PreOrderTraversal();
}

void Tree::MiddleOrderTraversal()
{
	m_pRoot->MiddleOrderTraversal();
}

void Tree::LastOrderTraversal()
{
	m_pRoot->LastOrderTraversal();
}

 main方法测试：

#include 
#include "Tree.h"

int main(void)
{
	Node *node1 = new Node();
	node1->index = 1;
	node1->data = 500;

	Node *node2 = new Node();
	node2->index = 2;
	node2->data = 800;

	Node *node3 = new Node();
	node3->index = 3;
	node3->data = 200;

	Node *node4 = new Node();
	node4->index = 4;
	node4->data = 600;

	Node *node5 = new Node();
	node5->index = 5;
	node5->data = 900;

	Node *node6 = new Node();
	node6->index = 6;
	node6->data = 700;

	Tree *tree = new Tree(666);

	tree->AddNode(0, LEFT, node1);
	tree->AddNode(0, RIGHT, node2);

	tree->AddNode(1, LEFT, node3);
	tree->AddNode(1, RIGHT, node4);

	tree->AddNode(2, LEFT, node5);
	tree->AddNode(2, RIGHT, node6);

	//tree->DeleteNode(6, NULL);
	//tree->DeleteNode(5, NULL);

	tree->DeleteNode(2, NULL);

	tree->PreOrderTraversal();

	//tree->MiddleOrderTraversal();
	//tree->LastOrderTraversal();

	delete tree;

	system("pause");
	return 0;
}

 以上就是二叉树的两种实现方，推荐使用链表的形式。