树

树的一些定义和基本性质：

一棵树只有唯一的根节点。
子树的个数没有限制，但是它们一定是互不相交的。(一对多的关系，不能是多对多的关系)
1个N节点的树有N-1个边。
节点的度：节点的子树个数（度为0的节点称为叶子节点）。
树的度：树中节点度最大的值。
m棵树（一个森林）一共有k条边，那么该森林一共有m+k个节点。（假设每棵树有Ki条边，那么k1+k2+...+km = k。并且每棵树有Ki+1个节点。故（k1+1）+(k2+1）+...+(km+1)为该森林总共的节点数目。化简上式可得k+m。故：一共有k+m个节点)
路径长度：该路径上边的总数即路径长度。
节点层次：从一棵树的根节点开始，定义根为第一层，根的孩子为第二层。一直到最后一层。
树的深度：树中节点最大层次。
任意一棵树都可以采用儿子/兄弟表示法来方便的进行表示。f
二叉树的子树有左右之分（一般度为2的树不区分左右子树）。
完美二叉树（满二叉树）：所有分支节点（非叶节点）都有左右两棵子树，并且所有的叶节点都在同一层。
完全二叉树：若一棵完美二叉树的叶节点从右到左有缺失，则可形成完全二叉树。

二叉树的一些重要性质：

二叉树的第i层最多有2^(i-1)个节点。
深度为k的二叉树最多有2^k - 1个节点。（根据等比数列求和公式求得）
对于任意的二叉树，若n0表示叶节点的个数，n1是度为1的节点个数，n2是度为2的节点个数。那么有n0 = n2 + 1.节点总数是n = n0 + n1 + n2 = 1 + n1 + 2n2。
一棵n节点的完全二叉树深度是[log n] + 1（向下取整）
对于一颗二叉树而言，由中序遍历和先序遍历或者后续遍历可以唯一确定一颗二叉树。（先序遍历和后序遍历不能确定唯一的二叉树，因为这时候没法区分左子树和右子树）

对于完全二叉树，我们可以使用顺序存储来方便的实现。因为对于下标为i的节点，它的左儿子在下标为2i处，右儿子在下标为2i+1处。（二叉树的元素从下标为1的地方开始存放）。当然，不能超过二叉树的节点总个数N。但是顺序存储的缺点也很明显，不利于插入和删除。这个缺点总是无法避免的。

实际上，我们经常使用的是链式存储二叉树。下面给出链式存储二叉树的ADT。

typedef struct BTreeNode *BinTree;
typedef BinTree Position;
typedef int ElementType;

struct BTreeNode
{
	ElementType data;	//数据域
	
	BinTree left;		//左子树
	BinTree right;		//右子树
}

二叉树的操作集：

创建二叉树：层序创建二叉树，这样可以使得输入二叉树变得简单。（避免了求出二叉树的先序，中序，或者后序序列。）创建过程如下：
输入第一个数据，若不为0，则赋值，入队；若为0，则返回空树。
若队列不空，则出队一个元素，并创建该节点的左右子树。从输入序列读入下一数据，若为0，则将出队元素的左子树置空，否则，创建左子树，并赋值，入队。接着从输入序列读取下一个数据，若为0，则将出队元素的右子树置空，否则，创建右子树，并赋值，入队。（在这个过程中记得保存创建的节点。）重复这个步骤，直到队列为空。下面给出C++实现的代码。

BinTree * CreateBinTree() 
{
	ElementType data;
	PTree BT;
	PTree T;
	PTree p[1000];		//存储指针；二叉树的节点指针,这样才能将树连接起来
	int i = 0, j = 0;	//双下标来控制数组
	PQueue Q;
	Q = CreatQueue();
	BT = new BinTree;
	cin >> data;
	if (data != '0')
	{
		BT->data = data;
		BT->Left = NULL;
		BT->Right = NULL;
		EnQueue(*BT, *Q);		//根节点入队
	}
	else
	{
		return NULL;		//空树
	}
	p[0] = BT;				//p[0]要保存BT，否则树就找不到
	while (!IsEmptyQueue(*Q))	//层序建立法，队列不为空就继续
	{
		T = DeQueue(*Q);	//弹出一个节点
		cin >> data;		//读左子树
		if ('0' == data)
		{
			T->Left = NULL;		//左子树空
		}
		else
		{
			T->Left = new BinTree;		//左子树非空
			T->Left->data = data;	
			T->Left->Left = NULL;
			T->Left->Right = NULL;

			p[i]->Left = T->Left;		//将其加入到弹出节点的左子树
			p[++j] = T->Left;			//将左子树地址存到数组中
			EnQueue(*T->Left, *Q);		//左子树入队
		}
		//右子树的处理和左子树是类似的。
		cin >> data;		//读右子树
		if ('0' == data)
		{
			T->Right = NULL;			//右子树空
		}
		else
		{
			T->Right = new BinTree;
			T->Right->data = data;
			T->Right->Left = NULL;
			T->Right->Right = NULL;

			p[i]->Right = T->Right;		//将其加入到弹出节点的右子树
			p[++j] = T->Right;			//将右子树地址存到数组中
			EnQueue(*T->Right, *Q);		//右子树入队
		}
		i++;		//i自增，为找到下一个可能弹出的节点的准备
	}
	return BT;
}

先序创建二叉树：这是一个递归的过程，先创建根节点，然后递归创建左子树，递归创建右子树。代码实现如下。

BinTree * CreateBinTree(int i)
{
	BinTree * BT;
	ElementType data;
	cin >> data;
	BT = new BinTree;
	if ('0' != data)
	{
		BT->data = data;
		BT->Left = CreateBinTree(1);
		BT->Right =CreateBinTree(2);
	}
	else
	{
		return NULL;
	}
	return BT;
}

遍历二叉树：按照访问节点的顺序，我们把对二叉树的遍历分为4中方式：前序遍历，中序遍历，后序遍历，层序遍历。其中前3中遍历方式是按照访问根节点的顺序命名的。层序遍历是根据树的层次来访问节点的，从树根开始，逐层访问树的节点。
先序遍历递归版实现代码：（访问根节点，先序遍历左子树，先序遍历右子树）

void PreorderTraversal(PTree BT)
{
	if (BT)
	{
		cout << BT->data << ' ';
		PreorderTraversal(BT->Left);
		PreorderTraversal(BT->Right);
	}
}

中序遍历递归版实现代码：（中序遍历左子树，访问根节点，中序遍历右子树）

void InorderTraversal(PTree BT)
{
	if (BT)
	{
		InorderTraversal(BT->Left);
		cout << BT->data << " ";
		InorderTraversal(BT->Right);
	}
}

后序遍历递归版实现代码：（后序遍历左子树，后序遍历右子树，访问根节点）

void PostorderTraversal(PTree BT)
{
	if (BT)
	{
		PostorderTraversal(BT->Left);
		PostorderTraversal(BT->Right);
		cout << BT->data << " ";
	}
}

先序遍历非递归实现代码：

void PreorderTraversal(PTree BT, int i)
{
	PTree T;
	PStack S = CreatStack();
	T = BT;

	while (T || !IsEmptyStack(*S))
	{
		while (T)
		{
			cout << T->data << ' ';			//入栈之前就输出
			PushStack(*S, *T);				//左子树入栈
			T = T->Left;
		}
		if (!IsEmptyStack(*S))
		{
			T = PopStack(*S);				//弹出元素
			//将输出放在这里就是中序遍历
			T = T->Right;					//转右子树
		}
	}
}

中序遍历和前序的最后一句是递归调用，这句递归调用是“尾递归”。可以在不借助堆栈的情况下使用循环语句来完成。所以前序和中序的非递归函数是几乎一致的。都是借助一个堆栈，将左子树入栈，然后弹出转右子树。但是后序遍历的最后一句并不是“尾递归”，使得无法仅通过一个堆栈就完成。所以后序遍历的非递归版本和上面的看起来有些不一样。
后序遍历非递归实现代码：

void PostorderTraversal(PTree BT, int i)
{
	//前序遍历是：根，左子树，右子树
	//后序遍历是：左子树，右子树，根
	//想法是将前序遍历的顺序改为根，右子树，左子树，然后压入堆栈。
	//最后将元素从堆栈弹出，顺序就变为：左子树，右子树，根
	//这样就完成了后序遍历二叉树
	PTree T = BT;
	PStack S1 = CreatStack();
	PStack S2 = CreatStack();		//借助这个栈来实现后序遍历输出
	
	while (T || !IsEmptyStack(*S1))
	{
		while (T)
		{
			PushStack(*S1, *T);	//根	
			PushStack(*S2, *T);
			T = T->Right;		//右子树入栈
		}
		if (!IsEmptyStack(*S1))
		{
			T = PopStack(*S1);	//弹出元素
			T = T->Left;		//左子树入栈
		}
	}
	while (!IsEmptyStack(*S2))	//弹出栈
	{
		T = PopStack(*S2);
		cout << T->data << " ";
	}
}

层序遍历二叉树：层序遍历和层序创建一样，需要借助一个队列来完成。它的操作过程是，访问根节点，访问左儿子，访问右儿子。

void Levelordertraversal(PTree BT)
{
	//从队列中取出一个元素
	//访问该元素
	//将该元素的非空左儿子和非空右儿子入队。
	//重复这个过程，直到队列为空。

	PQueue Q;
	BinTree* T;	
	if (!BT)				//空树
	{
		return;
	}
	else
	{
		Q = CreatQueue();		//创建队列
		EnQueue(*BT, *Q);		//根节点入队

		while (!IsEmptyQueue(*Q))
		{
			T = DeQueue(*Q);
			cout << T->data << " ";
			if (T->Left)
			{
				EnQueue(*T->Left, *Q);		//左子树入队
			}
			if (T->Right)
			{
				EnQueue(*T->Right, *Q);	//右子树入队
			}
		}
	}
}

二叉树是否为空的判断是非常简单的。下面给出。

二叉树是否为空

bool IsEmpty(PTree BT)
{
	return (NULL == BT) ? true : false;
}

输出二叉树的叶节点

void PreorderPrintLeaves(BinTree * BT)
{    //这里采用了先序遍历方式
    if (BT)
    {
        if (!BT->Left && !BT->Right)    //左右子树都为空的节点是叶节点
        {
            cout << BT->data << " ";
        }
        PreorderPrintLeaves(BT->Left);
        PreorderPrintLeaves(BT->Right);
    }
}

求二叉树的高度
求一颗二叉树的高度，可以采用后序遍历的方式。根节点的高度就是一棵树的高度，而根节点的高度等于其左子树和右子树高度的最大值加1。所以首先需要求出左子树和右子树的高度，因此，后序遍历的原理就很适合。
```
int PostorderGetHeight(BinTree * BT)
{
	int L, R, maxsize;
	if (BT)
	{
		L = PostorderGetHeight(BT->Left);
		R = PostorderGetHeight(BT->Right);
		maxsize = L > R ? L : R;
		return maxsize + 1;
	}
	else
	{
		return 0;		//空树深度为0
	}
}
```
二叉树的操作基本就这么多了，关于完整代码的实现，我放在了百度云盘里，想看的朋友下载下来看吧！
百度云盘链接：https://pan.baidu.com/s/1ECw8uo22B06M6wNrP_KfWw
提取码: j4wt