树基本概念及用法

1.树的基础知识概述

树状图是一种数据结构，它是由 n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

专业术语	中 文	描 述
Root	根节点	一棵树的顶点
Child	孩子节点	一个结点含有的子树的根结点称为该结点的子结点
Leaf	叶子节点	没有孩子的节点（度为0）
Degree	度	一个节点包含的子树的数量
Edge	边	一个节点与另外一个节点的连接
Depth	深度	根节点到这个节点经过的边的数量
Height	节点高度	从当前节点到叶子节点形成路径中边的数量
Level	层级	节点到根节点最长路径的边的总和
Path	路径	一个节点和另一个节点之间经过的边和 Node 的序列

 
2.二叉树

2.1二叉树的基本概念

二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两个互不相交的、分别称为根结点左子树和右子树的二叉树组成。
二叉树是一个每个结点最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。

1. （1）在风控二叉树，第i-1层的结点总数不超过，i>=1；
2. （2）深度为h-1的二叉树最多有-1个结点（h>=1），最少有h个结点
3. （3）对于任意一棵二叉树，如果叶节点为N0，而度数为2 的结点总数为N2，则N0=N2+1；<br>　　 每个度为1的结点有1条边，度为2的结点有两条边。所以总边数为1*n1+2*n2，总边数等于结点数减1，即  N-1 = 1*n1+2*n2。其中总结点数又等于度为1、度为2、度为0的结点数和，即 N = n1 + n2 + n0；联立可得N0=N2+1。

复制代码

2.2二叉树的特点

1. 1.每个结点最多有两个子树，所以二叉树中不存在度大于2的结点。
2. 2.左子树和右子树是有顺序的，次序不能颠倒。即使树中只有一颗子树，也要区分是左子树还是右子树。

复制代码

2.3二叉树的五种形态

1. 1.空二叉树。
2. 2.只有一个根结点。
3. 3.根结点只有左子树。
4. 4.根结点只有右子树。
5. 5.根结点既有左子树，又有右子树。

复制代码

2.4特殊二叉树

1. 1）完全二叉树 ——若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树（堆就是完全二叉树）。

复制代码

　　

1. 2）满二叉树 ——除了叶结点外每一个结点都有左右子节点且叶子结点都处在最底层的二叉树。

复制代码

　　

1. 3）平衡二叉树 ——又被称为 AVL 树，它是一颗<strong>空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。</strong>

复制代码

　　

1. 4）二叉搜索树 ——又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树：（右边>=根>=左边）
2.         1）若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；
3.         2）若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
4.         3）左、右子树也分别为二叉排序树。

复制代码

　　

1. 5）红黑树 ——是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：
2.         1）节点是红色或黑色；
3.         2）根节点是黑色；
4.         3）所有叶子节点都是黑色；
5.         4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个
6.                 连续为红色的结点）；
7.         5）从<strong>任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点</strong>。 （没有度为
8.                 1的结点）。
9.         以上规则可以保证左右子树结点数差距不超过两倍~

复制代码

　　
 
 
 2.5二叉树的性质

1. 1.在二叉树的第i层上最多有2i-1个结点(i≥1)。
2. 2.深度为k的二叉树最多有2k-1个结点(k≥1)。
3. 3.对于任何一个二叉树，如果其叶子结点数为n0，度数为2的结点数为n2，那么n0=n2+1，也就是叶子结点数为度为2的结点数加1。
4. 4.具有n个结点的完全二叉树深度为(log2n)+1。
5. 5.对具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对二叉树的所有结点从1开始编号，则对于任意的序号为i的结点有:
6. A. 如果i>1，那么序号为i的结点的双亲结点序号为i/2;
7. B. 如果i=1，那么序号为i的结点为根节点，无双亲结点;
8. C. 如果2i<=n，那么序号为i的结点的左孩子结点序号为2i;
9. D. 如果2i>n，那么序号为i的结点无左孩子;
10. E. 如果2i+1<=n，那么序号为i的结点右孩子序号为2i+1;
11. F. 如果2i+1>n，那么序号为i的结点无右孩子。

复制代码

3.二叉搜索树的算法实现

比如有以下数据：
 
当我们想保证查找效率时，可以用顺序表存储，当我们想保证插入和删除效率时，我们可以用链式表存储，有没有一种存储方法可以同时兼顾顺序表和链式表的优点？
使用二叉树，便可兼顾查找效率和插入删除效率~
 
 
 
 
二叉树一般采用链式存储方式：每个结点包含两个指针域，指向两个孩子结点，还包含一个数据域，存储结点信息。
 
 
 
 
结点结构体定义：

1. 1 typedef struct _BNode {
2. 2     int data;
3. 3     struct _BNode *lchild, *rchild;
4. 4 }Bnode,*Btree;

复制代码

3.1二叉搜索树插入结点

1. 1  
2. 2 //二叉树插入结点
3. 3 /*将插入结点e，与结点root结点进行比较，若小于则去到左子树，否则
4. 4 去右子树进行比较，重复以上操作直到找到一个空位置放置该结点
5. 5 */
6. 6 bool InsertBtree(Btree* root, Bnode* node) {
7. 7     Bnode* temp = NULL;
8. 8     Bnode* parent = NULL;
9. 9     if (!node) {            //如果插入结点为空，返回false
10. 10         return false;
11. 11     }else {                    //清空插入结点的左右子树
12. 12         node->lchild = NULL;
13. 13         node->rchild = NULL;
14. 14     }
15. 15  
16. 16     if (!(*root)) {            //如果根节点不存在，将插入结点作为根节点
17. 17         *root = node;
18. 18         return true;
19. 19     }else {                    
20. 20         temp = *root;
21. 21     }
22. 22  
23. 23     while (temp != NULL) {
24. 24         parent = temp;
25. 25         if (temp->data>node->data) {    //小于，继续向左
26. 26             temp = temp->lchild;
27. 27         }
28. 28         else {                            //大于，继续向右（不可以有相同的值）
29. 29             temp=temp->rchild;
30. 30         }  
31. 31         //while循环结束，parent所处位置即为要插入结点的父结点
32. 32     }
33. 33     if (node->data < parent->data) {
34. 34         parent->lchild = node;
35. 35     }
36. 36     else {
37. 37         parent->rchild = node;
38. 38     }
39. 39     return true;
40. 40 }

复制代码

3.2二叉搜索树删除结点

1. 将要删除的节点的值，与节点 root 节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以上操作直到找到一个节点的值等于删除的值，则将此节点删除。删除时有 4 中情况须分别处理：

复制代码

 1.删除节点不存在左右子节点，即为叶子节点，直接删除

 
 2.删除节点存在左子节点，不存在右子节点，直接把左子节点替代删除节点

 
  3.删除节点存在右子节点，不存在左子节点，直接把右子节点替代删除节点

 
 4.删除节点存在左右子节点，则取左子树上的最大节点或右子树上的最小节点替换删除节点。

 
 代码实现：

1. 1 //查找左子树最大值
2. 2 int findLeftMax(Btree* root) {
3. 3     /*采用递归方式查找
4. 4     * if (root->rchild == NULL)
5. 5         return root->data;
6. 6     return findMax(root->rchild);
7. 7     */
8. 8     //采用循环查找
9. 9     Btree indexNode = *root;
10. 10     while (indexNode->rchild)
11. 11         indexNode = indexNode->rchild;
12. 12     return indexNode->data;
13. 13 }
14. 14  
15. 15  
16. 16 //采用递归的方式删除结点
17. 17 /*
18. 18     这种递归方式，是将要修改的结点的一层一层的返回
19. 19 */
20. 20 Btree deleteNode(Btree* root, int value) {
21. 21     Btree compareNode = *root;        
22. 22     //节点为空（递归找不到value/根节点为空），直接返回
23. 23     if (!compareNode)return compareNode;            
24. 24     //大于
25. 25     if (compareNode->data > value) {
26. 26         //左子树重新被赋值
27. 27         compareNode->lchild = deleteNode(&(compareNode->lchild), value);        
28. 28         return compareNode;                                                               
29. 29     }
30. 30     //小于
31. 31     else if (compareNode->data < value) {        
32. 32         //右子树重新被赋值
33. 33         compareNode->rchild = deleteNode(&(compareNode->rchild), value);        
34. 34         return compareNode;
35. 35     }
36. 36     else {//等于                                            
37. 37         Btree temp = NULL;
38. 38         //无左右子节点，直接返回NULL
39. 39         if (compareNode->lchild == NULL && compareNode->rchild == NULL) {        
40. 40             delete compareNode;
41. 41         }
42. 42         //有左子树，返回左子树
43. 43         else if (compareNode->lchild && compareNode->rchild == NULL) {            
44. 44             temp = compareNode->lchild;
45. 45             delete compareNode;
46. 46         }
47. 47         //有右子树，返回右子树
48. 48         else if (compareNode->rchild && compareNode->lchild == NULL) {            
49. 49             temp = compareNode->rchild;
50. 50             delete compareNode;
51. 51         }
52. 52         else {                                            
53. 53             //这里采用左子树最大值替换               
54. 54             int leftMax = findLeftMax(&(compareNode->lchild));               
55. 55             //最大值替换删除结点的值
56. 56             compareNode->data = leftMax;                                       
57. 57             //将最大值从树中删除
58. 58             compareNode->lchild = deleteNode(&(compareNode->lchild), leftMax);
59. 59             temp= compareNode;
60. 60         }
61. 61         return temp;
62. 62     }
63. 63 }

复制代码

3.3二叉搜索树查找 

1. 1 // 采用递归方式查找结点
2. 2 /*
3. 3 Bnode* queryByRec(Btree root, int value) {
4. 4     if (root == NULL || root->data==value ){
5. 5         return root;
6. 6     }
7. 7     else if (root->data < value) {
8. 8         return queryByRec(root->lchild, value);
9. 9     }
10. 10     else {
11. 11         return queryByRec(root->rchild, value);
12. 12     }
13. 13 }*/
14. 14  
15. 15 // 使用非递归方式查找结点
16. 16  
17. 17 Bnode* queryByLoop(Btree root, int value) {
18. 18     while (root != NULL && root->data!=value) {
19. 19         if (root->data>value) {
20. 20             root = root->lchild;
21. 21         }
22. 22         else {
23. 23             root = root->rchild;
24. 24         }
25. 25     }
26. 26     return root;
27. 27 }

复制代码

3.4二叉搜索树遍历结点

3.4.1前序遍历

1. 前序遍历，简单来说就是遍历根-左孩子-右孩子

复制代码

 
如上图，前序遍历的结果为 19 7 5 11 15 25 21 61
 
[code]1 void PreOrderRec(int x)//x为根节点2 {3     if (x == 0)return;//若遍历完成，返回函数4     cout