[数据结构与算法] 二叉树
树的基本概念:
可以把“树”理解成一种特别的图(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 }