树

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

• 一棵树只有唯一的根节点。
• 子树的个数没有限制，但是它们一定是互不相交的。(一对多的关系，不能是多对多的关系)
• 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;		//右子树
}

二叉树的操作集：

1. 创建二叉树：层序创建二叉树，这样可以使得输入二叉树变得简单。（避免了求出二叉树的先序，中序，或者后序序列。）创建过程如下： 输入第一个数据，若不为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; }
2. 遍历二叉树：按照访问节点的顺序，我们把对二叉树的遍历分为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); //右子树入队 } } } } 二叉树是否为空的判断是非常简单的。下面给出。
3. 二叉树是否为空 bool IsEmpty(PTree BT) { return (NULL == BT) ? true : false; }
4. 输出二叉树的叶节点 void PreorderPrintLeaves(BinTree * BT) { //这里采用了先序遍历方式 if (BT) { if (!BT->Left && !BT->Right) //左右子树都为空的节点是叶节点 { cout << BT->data << " "; } PreorderPrintLeaves(BT->Left); PreorderPrintLeaves(BT->Right); } }
5. 求二叉树的高度 求一颗二叉树的高度，可以采用后序遍历的方式。根节点的高度就是一棵树的高度，而根节点的高度等于其左子树和右子树高度的最大值加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