树的基本概念：
可以把“树”理解成一种特别的图（graph），树是图的特例。
也可以把树理解成一种“半线性结构”（参考不平衡的二叉查找树，可能会有一边演变成线性结构）
以下的概念都以二叉树（每个节点只有两个分支）为例
0. 二叉树（binary tree）
二叉树的每个元素恰好有两个子树（其中一个可能为空）
每个元素的子树是有序的（左子树和右子树之分）
1. 节点（node）
相当于是图的顶点（vertex），如下图的顶点：A,B,C,D,E,F,G,H,I..
2. 枝（branch）
相当于图的边（edge）。如上图的A->B, B->D, C->E等
3. 根（root）
每棵树都有一个根节点，并且这个根节点是唯一的，不可能存在多个根节点。上图中，A 为 根节点。
4. 度（degree）
节点拥有的子树个数，称为节点的度。
5. 叶（leaf）
度为0的点，如上图的 G, H, I是叶。
6. 子树
7. 孩子（child） ： 结点的子树的根称为该结点的孩子。对一颗有根树，相邻两点，远离根的就是孩子。
8. 双亲（parent） ： 对一颗有根树，相邻两点，靠近根的就是双亲。
9. 兄弟（sibling） ： 同一个双亲的孩子之间互称兄弟。
10. 堂兄弟 ： 双亲在同一层的结点互为堂兄弟
11. 祖先/后代（ancestor/descendant）
对于一个有根树，某一个点的双亲，双亲的双亲...都是该点的祖先（ancestor），根节点是所有子节点是祖先，注意，双亲也属于祖先。
同理，一个点的孩子，孩子的孩子....都是该点的后代（descendant）。祖先/后代都是一个集合概念。
12. 层次（level）
从根开始定义，根为第一层，根的孩子为第二层。
13. 深度/高度（depth/height）
一个树的最大层数称为树的深度（depth）或树的高度（height）。
一个节点到下方的叶的最大层数之差，称为节点的高度。
高度和深度是相反的，高度是从下往上数，深度是从上往下数
14. 森林（forest）
很多棵树的集合称为森林，森林中，树与树之间互不相交。
小结
- 树是一种特殊的图，树中所有的点都是联通的
- 数是无环的连通图
- 树还有一些图的含义（有向/无向，权重，路径等，下次再补充）
二叉树的特性
- 一棵二叉树有 n （n > 0）个元素，那么它有 n - 1 条边（枝/branch）。
- 一棵二叉树的高度为 height （height >= 0），它至少有 height 个元素， 最多有 $2^{height} - 1$个元素。当这棵树恰好有 $2^{height} - 1$个元素时，称其为满二叉树。
- 一棵二叉树有 n （n > 0）个元素，它的最大高度为 n，最小高度为 $\log_{2}{(n+1)}$] 向上取整
- 完全二叉树 ： 从一棵满二叉树中删除 k 个编号为$2^{k} - i$ ($1\le i \le k < 2^k$），所得到的二叉树称为满二叉树。
- 第 n 层 的节点数为 $2^{n} - 1$ （n 从 1开始计数，即根节点的层数为1/高度为1）
其他特性
设完全二叉树的一个元素编号为 i （$1\le i \le n$），则：
- 当 i = 1，该元素为根节点。若 i > 1，则其父节点的编号为 [ i / 2 ]（向下取整）
- 如果 2i > n，则该元素无左孩子。否则，其左孩子的编号为 2 i。
- 如果 2i + 1 > n，则该元素无右孩子。否则，其右孩子的编号为 2i + 1。
二叉树的描述
二叉树的节点
1 #include <iostream> 2 using namespace std; 3 4 template<class T> 5 struct binaryTreeNode 6 { 7 /*从根节点开始沿着left Child和right Child指针域， 访问二叉树的所有节点*/ 8 T element; 9 binaryTreeNode<T> *leftChild; //左子树 10 binaryTreeNode<T> *rightChild; //右子树 11 12 binaryTreeNode() { 13 leftChild = rightChild = NULL; 14 } 15 16 binaryTreeNode(const T& theElement) { 17 element(theElement); //初始化element 18 leftChild = rightChild = NULL; 19 } 20 21 binaryTreeNode(const T& theElement, binaryTreeNode<T> *theLeftChild, binaryTreeNode<T> *theRightChild) { 22 element = theElement; 23 theLeftChild = leftChild; 24 theRightChild = rightChild; 25 } 26 };
二叉树的基本操作
二叉树的遍历（traversal）方式
二叉树的遍历是指：从根节点出发，按照某种次序访问二叉树中的所有节点，使得每个节点被访问一次，而且只能被访问一次。
一、先序遍历（Preorder Traversal， DLR）
这种遍历方式（DLR）先处理当前节点，然后处理左子树，最后处理右子树。是先处理节点再处理子树的方式。
以左图为例
先处理根节点 ①，然后处理左子树、右子树。在处理完左子树之后，为了能够正确的移动到右子树，它必须要保存根节点的信息。这种信息适合保存在栈里面（FILO）
以左图为例，先序遍历经过的节点分别是 ： 1 2 4 5 3 6 7
先序遍历的递归算法
/* 先序遍历 */ template<class T> void preOrder(binaryTreeNode<T> *t) { if (t != NULL) { //visit(t); //访问根节点 cout << t->element << ' '; //访问当前节点 preOrder(t->leftChild); //前序遍历左子树 preOrder(t->rightChild); //前序遍历右子树 } }
时间复杂度 ： O(n)
空间复杂度 ： O(n)
先序遍历的非递归算法
前面有说到，需要保存当前节点的信息，以便于处理完左子树之后，根据当前节点找出右子树。非递归算法，就要人工模拟这个机制来保存节点信息。这里考虑将节点保存在栈中，然后处理左子树，等处理完左子树之后，就将对应的节点弹出（出栈），以此来确定右子树。反复执行此过程，直到栈清空。
1 /*非递归先序遍历*/ 2 template<class T> 3 void preOrderNonRecursive(binaryTreeNode<T> *root) 4 { 5 if (root != NULL) 6 { 7 stack<binaryTreeNode<T>* > s; 8 binaryTreeNode<T> *r = root; 9 while (!s.empty() || r) 10 { 11 while (r) 12 { 13 s.push(r); //保存当前节点信息 14 cout << r->element << ' '; //访问当前节点 15 r = r->leftChild; 16 } 17 if (!s.empty()) 18 { 19 r = s.top(); 20 s.pop(); 21 r = r->rightChild; 22 } 23 } 24 } 25 }
分析：
对于上面的这颗二叉树，执行非递归先序遍历，为次创建了一个栈用来保存节点，首先看一下内层循环 while(r) ，先保存根节点 1 ，然后输出节点内容， 接着保存节点 2 ，4.。此时的 r 为 NULL，因此退出内层循环，进入 if 语句，然后弹出1个节点，访问节点的右孩子。当访问右孩子的时候，也要记录节点信息，将节点入栈。
时间复杂度 ： O(n)
空间复杂度 ： O(n)
二、中序遍历（Inorder Traversal，LDR）
中序遍历会把访问根节点的操作，放在访问左子树和右子树之间。
顺序：（1）中序遍历左子树 （2）访问根节点 （3）中序遍历右子树
中序遍历的递归算法
1 /*中序遍历*/ 2 template<class T> 3 void inOrder(binaryTreeNode<T> *root) 4 { 5 if (root != NULL) 6 { 7 inOrder(root->leftChild); //中序遍历左子树 8 cout << root->element << ' '; //访问根节点 9 inOrder(root->rightChild); //中序遍历右子树 10 } 11 }
时间复杂度 ： O(n)
空间复杂度 ： O(n)
中序遍历的非递归算法
非递归的中序遍历与非递归的先序遍历类似，唯一的区别：并不是先处理节点再转入左子树，而是等到节点弹出之后，才处理该节点（该节点弹出说明左子树已经处理完毕）
1 /*非递归中序遍历*/ 2 template<class T> 3 void inOrderNonRecursive(binaryTreeNode<T> *root) 4 { 5 if (root != NULL) 6 { 7 stack<binaryTreeNode<T>* > s; 8 binaryTreeNode<T> *r = root; 9 while (!s.empty() || r) 10 { 11 while (r) 12 { 13 s.push(r); 14 r = r->leftChild; 15 } 16 if (!s.empty()) 17 { 18 r = s.top(); 19 cout << r->element << ' '; //访问根节点 20 s.pop(); //访问完毕之后，弹出节点，说明左子树处理完了 21 r = r->rightChild; 22 } 23 } 24 } 25 }
时间复杂度 ： O(n)
空间复杂度 ： O(n)
三、后序遍历（Postorder Traversal，LRD）
先访问两颗子树，最后访问根节点
顺序：（1）后序遍历左子树 （2）后序遍历右子树 （3）访问根节点
后序遍历的递归算法
1 /*后序遍历*/ 2 template<class T> 3 void postOrder(binaryTreeNode<T> *root) 4 { 5 if (root != NULL) 6 { 7 postOrder(root->leftChild); //后序遍历左子树 8 postOrder(root->rightChild); //后序遍历右子树 9 visit(root); //访问根节点 10 } 11 }
时间复杂度 ： O(n)
空间复杂度 ： O(n)
后序遍历的非递归算法
注意，实现后序遍历时，每个节点必须访问两次。在处理完该节点的左子树之后访问一次，处理完右子树之后再访问一次，总共两次。也就是说，只有在第二次访问该节点的时候，才需要对该节点进行操作，那么如何区分这两次访问呢？
思路：把元素弹出后，判断它与栈顶元素的右节点是否相同。如果相同，说明左右子树都已经处理完毕，只需要将栈顶这个元素也弹出来并打印元素信息就可以了。
1 /*非递归后序遍历*/ 2 template<class T> 3 void postOrderNonRecursive(binaryTreeNode<T> *root) 4 { 5 if (root != NULL) 6 { 7 stack<binaryTreeNode<T>* > s; 8 binaryTreeNode<T> *r = root; 9 binaryTreeNode<T> *receive = NULL; //用来接收栈顶元素，判断其弹出元素与栈顶元素的右节点是否相同 10 while (!s.empty() || r) 11 { 12 if (r != NULL) 13 { 14 s.push(r); 15 r = r->leftChild; 16 } 17 else 18 { 19 receive = s.top(); 20 if (receive->rightChild != NULL && receive->rightChild != r) 21 { 22 receive = receive->rightChild; 23 } 24 else 25 { 26 s.pop(); 27 cout << receive->element << ' '; 28 r = receive; 29 receive = NULL; 30 } 31 } 32 } 33 } 34 }
时间复杂度 ： O(n)
空间复杂度 ： O(n)
四、层次遍历（Level Order Traversal）
顾名思义，就是按层遍历，先遍历第一层，接下来从左至右遍历第二层
顺序：（1）访问根节点（2）遍历第1层时，把第 i + 1 层各节点放在队列中（3）跳到下一层，并访问那一层的节点（4）如此反复直到每一层都处理完
1 /*层次遍历*/ 2 template<class T> 3 void levelOrder(binaryTreeNode<T> *root) 4 { 5 if (root != NULL) 6 { 7 binaryTreeNode<T> *temp; 8 queue<binaryTreeNode<T>* > q; 9 q.push(root); 10 while (!q.empty()) 11 { 12 temp = q.front(); 13 cout << temp->element; 14 if (temp->leftChild) 15 { 16 q.push(temp->leftChild); 17 } 18 if (temp->rightChild) 19 { 20 q.push(temp->rightChild); 21 } 22 q.pop(); 23 } 24 } 25 }
