二叉树算法算法【二叉树的创建、插入、删除、查找】 ...

一、原理

1.1、二叉排序树的插入

1.2、二叉树的删除

（1）删除度为0的节点，就是末了的叶子节点，直接删除就可以了.
（2）删除度为1的节点，就是爷爷节点接收孙子节点。

（3）删除度为2的节点就是找到该节点的前驱和后继，然后降当前节点与前驱节点的值交换，就酿成了前面两度为0或者1的节点删除的情况，然后在进行删除就可以了。

二、代码

1. #include <iostream>
2. #include <vector>
3. #include <string>
4. using namespace std;
5. /* 对二叉树的的操作 */
7. /* 二叉树的节点 */
8. typedef struct Node
9. {
10.         int key;
11.         struct Node* Lchild, * Rchild;
12. }g_Node;
14. /* 创建一个节点 */
15. g_Node* getNewNode(int key)
16. {
17.         g_Node* node = (g_Node*)malloc(sizeof(g_Node));
19.         node->key = key;
20.         node->Lchild = NULL;
21.         node->Rchild = NULL;
22.         return node;
23. }
25. /* 向树中某个节点后插入如一个随机数节点:采用递归的方式插入树中元素 */
26. //g_Node* insert(g_Node* root, int key)
27. //{
28. //        if (NULL == root)  return getNewNode(key);
29. //        //随机插入树的左边或者右边
30. //        if (rand() % 2)  root->Lchild = insert(root->Lchild, key);
31. //        else root->Rchild = insert(root->Rchild, key);
32. //        return root;
33. //}
35. /* 向树中插入顺序树：创建二叉树 */
36. g_Node* insert(g_Node* root, int key)
37. {
38.         if (NULL == root)  return getNewNode(key);
39.         //随机插入树的左边或者右边
40.         if (key < root->key)  root->Lchild = insert(root->Lchild, key);
41.         else root->Rchild = insert(root->Rchild, key);
42.         return root;
43. }
45. /* 从根节点清理掉一个树:采用递归深入清理的方式 */
46. void clear(g_Node* root)
47. {
48.         if (NULL == root) return;
49.         clear(root->Lchild);
50.         clear(root->Rchild);
51.         free(root);
52.         return;
53. }
55. /* 二叉树打印函数：采用递归的方式，向内打印 */
56. int tot = 0;
57. void displayTree_V2(g_Node* root) {
58.         if (root == NULL) return;
59.         int start, end;
60.         tot += 1;
61.         start = tot;
62.         if (root->Lchild) displayTree_V2(root->Lchild);
63.         if (root->Rchild) displayTree_V2(root->Rchild);
64.         tot += 1;
65.         end = tot;
66.         printf("%d : [%d, %d]\n", root->key, start, end);
67.         return;
68. }
70. #define MAX_NODE 20
71. void displayTree_V1(g_Node* root) {
72.         g_Node* queue[MAX_NODE + 5];
73.         int head, tail;
74.         head = tail = 0;
75.         queue[tail++] = root;
76.         while (head < tail) {
77.                 g_Node* node = queue[head];
78.                 printf("\nnode : %d\n", node->key);
79.                 if (node->Lchild) {
80.                         queue[tail++] = node->Lchild;
81.                         printf("\t%d->%d (left)\n", node->key, node->Lchild->key);
82.                 }
83.                 if (node->Rchild) {
84.                         queue[tail++] = node->Rchild;
85.                         printf("\t%d->%d (right)\n", node->key, node->Rchild->key);
86.                 }
87.                 head++;    //如果打印到了结尾了，tail索引就不会在增加，但是head还是增加的，最终就会跳出循环
88.         }
89.         return;
90. }
92. /* 二叉树的查找:递归的方式向下查找 */
93. bool findBinaryTree(g_Node* root, int key)
94. {
95.         bool ret;
96.         if (NULL == root) return false;
97.         if (key == root->key) return true;
98.         if (key < root->key) ret = findBinaryTree(root->Lchild, key);
99.         else ret = findBinaryTree(root->Rchild, key);
100.         return ret;
101. }
103. /* 找到节点的前驱节点 */
104. g_Node* getProNode(g_Node* root)
105. {
106.         if (NULL == root) return root;
107.         root = root->Lchild;
108.         while (root) root = root->Rchild;
109.         return root;
110. }
112. /*
113. * 二叉树删除节点:
114. * （1）删除度为0的节点
115. * （2）删除度为1的节点
116. * （3）删除度为2的节点：找到节点的前驱，之后与前驱节点交换，
117. *                                             降为删除度为0和度为1的节点。
118. */
119. g_Node* deleteNodeTree(g_Node* root, int key)
120. {
121.         if (NULL == root) return root;
122.         if (key < root->key) root->Lchild = deleteNodeTree(root->Lchild, key);
123.         else if(key>root->key) root->Rchild = deleteNodeTree(root->Rchild, key);
124.         else {
125.                 //删除度为0的节点
126.                 if (root->Lchild == NULL && root->Rchild == NULL)   
127.                 {
128.                         free(root);   //直接删除
129.                         return NULL;
130.                 }    //删除度为1的节点
131.                 else if (root->Lchild == NULL || root->Rchild == NULL)
132.                 {   //root的子节点由root的父节点承接
133.                         g_Node* temp = root->Lchild ? root->Lchild : root->Rchild;
134.                         free(root);
135.                         return temp;
136.                 }
137.                 else  //删除度为2的节点
138.                 {
139.                         g_Node* temp = getProNode(root);   //找到节点的前驱
140.                         root->key = temp->key;   //与前驱交换key数值
141.                         //继续递归调用，删除掉交换值后的节点，变成度为0、1的节点删除问题。
142.                         root->Lchild = deleteNodeTree(root->Lchild, temp->key);
143.                 }
144.         }
145.         return root;
146. }
149. int main()
150. {
151.         g_Node* root = NULL;
152.         for (int i = 0; i < MAX_NODE; i++)      //创建二叉树
153.         {
154.                 root = insert(root, rand() % 100);
155.         }
156.         displayTree_V1(root);
157.         displayTree_V2(root);
158.         int data = rand() % 100;
159.         bool ret = findBinaryTree(root, data);
160.         printf("find:%d, %d\r\n", ret, data);
161.         deleteNodeTree(root, data);
162.         displayTree_V2(root);
163.         clear(root);
164.         return 0;
165. }

复制代码

终极的运行效果如下所示：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。