详解⼆叉查找树算法的实现（c语⾔）
regard是什么意思树（Tree）是n（n≥0）个结点的有限集。在任意⼀棵⾮空树中：（1）有且仅有⼀个特定的被称为根（Root）的结点；（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2，…，T m，其中每⼀个集合本⾝⼜是⼀棵树，并且称为根的⼦树（SubTree）。
结点拥有的⼦树数称为结点的度（Degree）。度为0的结点称为叶⼦（Leaf）或终端结点。度不为0的结点称为⾮终端结点或分⽀结点。树的度是树内各结点的度的最⼤值。
结点的⼦树的根称为该结点的孩⼦（Child），相应地，该结点称为孩⼦的双亲（Parent）。
结点的层次（Level）是从根结点开始计算起，根为第⼀层，根的孩⼦为第⼆层，依次类推。树中结点的最⼤层次称为树的深度（Depth）或⾼度。
如果将树中结点的各⼦树看成从左⾄右是有次序的（即不能互换），则称该树为有序树，否则称为⽆序树。
1、⼆叉树
⼆叉树（Binary Tree）的特点是每个结点⾄多具有两棵⼦树（即在⼆叉树中不存在度⼤于2的结点），并且⼦树之间有左右之分。
⼆叉树的性质：
（1）、在⼆叉树的第i层上⾄多有2i-1个结点（i≥1）。
（2）、深度为k的⼆叉树⾄多有2k-1个结点（k≥1）。
做鬼脸 英语（3）、对任何⼀棵⼆叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
⼀棵深度为k且有2k-1个结点的⼆叉树称为满⼆叉树。
可以对满⼆叉树的结点进⾏连续编号，约定编号从根结点起，⾃上⽽下，⾃左⾄右，则由此可引出完全⼆叉树的定义。深度为k且有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为k的满⼆叉树中编号从1到n的结点⼀⼀对应时，称之为完全⼆叉树。
（4）、具有n个结点的完全⼆叉树的深度为不⼤于log2n的最⼤整数加1。
（5）、如果对⼀棵有n个结点的完全⼆叉树的结点按层序编号（从第1层到最后⼀层，每层从左到右），则对任⼀结点i（1≤i≤n），有
a、如果i=1，则结点i是⼆叉树的根，⽆双亲；如果i>1，则其双亲是结点x（其中x是不⼤于i/2的最⼤整数）。
b、如果2i>n，则结点i⽆左孩⼦（结点i为叶⼦结点）；否则其左孩⼦是结点2i。
c、如果2i+1>n，则结点i⽆右孩⼦；否则其右孩⼦是结点2i+1。
⼆叉树的链式存储：
链式⼆叉树中的每个结点⾄少需要包含三个域，数据域和左、右指针域。
⼆叉树的遍历：
2012年职称英语考试成绩查询假如以L、D、R分别表⽰遍历左⼦树、访问根结点和遍历右⼦树，则可有DLR、DRL、LRD、LDR、RLD、RDL这六种遍历⼆叉树的⽅案。若限定先左后右，则只有三种⽅案，分别称之为先（根）序遍历、中（根）序遍历和后（根）序遍历，它们以访问根结点的次序来区分。
2、⼆叉查找树
⼆叉查找树（BinarySearch Tree，也叫⼆叉搜索树，或称⼆叉排序树Binary Sort Tree）或者是⼀棵空树，或者是具有下列性质的⼆叉树：
（1）、若它的左⼦树不为空，则左⼦树上所有结点的值均⼩于它的根结点的值；
（2）、若它的右⼦树不为空，则右⼦树上所有结点的值均⼤于它的根结点的值；
（3）、它的左、右⼦树也分别为⼆叉查找树。
本科转学出国3、⼆叉查找树的基本运算
（1）、插⼊
xiling在⼆叉查找树中插⼊新结点，要保证插⼊新结点后仍能满⾜⼆叉查找树的性质。例⼦中的插⼊过程如下：
a 、若⼆叉查找树root 为空，则使新结点为根；
b 、若⼆叉查找树root 不为空，则通过arch_bst_for_inrt 函数寻找插⼊点并返回它的地址（若新结点中的关键字已经存在，则返回空指针）；
c 、若新结点的关键字⼩于插⼊点的关键字，则将新结点插⼊到插⼊点的左⼦树中，⼤于则插⼊到插⼊点的右⼦树中。 [cpp]
01. /* bst - binary arch/sort tree 02. * by Richard Tang <> 03. */ 04. #inclu
de <stdio.h> 05. #include <stdlib.h> 06. 07. typedef int data_type; 08. 09. typedef struct bst_node { 10. data_type data; 11. struct bst_node *lchild, *rchild; 12. }bst_t, *bst_p; [cpp]
video glass01. static bst_p arch_bst_for_inrt(bst_p *root, data_type key) 02. { 03. bst_p s, p = *root; 04. 05. while (p) { 06. s = p; 07. 08. if (p->data == key) 09. return NULL; 10. 11. p = (key < p->data) ? p->lchild : p->rchild; 12. } 13. 14. return s; 15. } 16. 17. void inrt_bst_node(bst_p *root, data_type data) 18. { 19. bst_p s, p; 20. 21. s = malloc(sizeof (struct bst_node)); 22. if (!s) 23. perror("Allocate dynamic memory"); 24. 25. s -> data = data; 26. s -> lchild = s -> rchild = NULL; 27. 28. if (*root == NULL) 29. *root = s; 30. el { 31. p = arch_bst_for_inrt(root, data); 32. if (p == NULL) { 33. fprintf(stderr, "The %d already exists.\n", data); 34. free(s); 35. return ; 36. } 37. 38. if (data < p->data) 39. p->lchild = s; 40. el 41. p->rchild = s; 42. } 43. }
（2）、遍历
中序遍历⼆叉查找树可得到⼀个关键字的有序序列。
（3）、删除
删除某个结点后依然要保持⼆叉查找树的特性。例⼦中的删除过程如下：
balanceddiet
a 、若删除点是叶⼦结点，则设置其双亲结点的指针为空。
b 、若删除点只有左⼦树，或只有右⼦树，则设置其双亲结点的指针指向左⼦树或右⼦树。
c 、若删除点的左右⼦树均不为空，则：
1）、查询删除点的右⼦树的左⼦树是否为空，若为空，则把删除点的左⼦树设为删除点的右⼦树的左⼦树。
officer2）、若不为空，则继续查询左⼦树，直到找到最底层的左⼦树为⽌。 [cpp]
01. static int print(data_type data) 02. { 03. printf("%d ", data); 04. 05. return 1; 06. } 07. 08. int pre_order_traver(bst_p root, int (*visit)(data_type data)) 09. { 10. if (root) { 11. if (visit(root->data)) 12. if (pre_order_traver(root->lchild, visit)) 13. if (pre_order_traver(root->rchild, visit)) 14. return 1; 15. return 0; 16. } 17. el 18. return 1; 19. } 20. 21. int post_order_traver(bst_p root, int (*visit)(data_type data)) 22. { 23. if (root) { 24. if (post_order_traver(root->lchild, visit)) 25. if (visit(root->data)) 26. if (post_order_traver(root->rchild, visit)) 27. return 1; 28. return 0; 29. } 30. el 31. return 1; 32. }
4、⼆叉查找树的查找分析
同样的关键字，以不同的插⼊顺序，会产⽣不同形态的⼆叉查找树。 01. void delete_bst_node(bst_p *root, data_type data) 02. { 03. bst_p p = *root, parent, s; 04. 05. if (!p) { 06. fprintf(stderr, "Not found %d.\n", data); 07. return ; 08. } 09. 10. if (p->data == data) { 11. /* It's a leaf node */ 12. if (!p->rchild && !p->lchild) { 13. *root = NULL; 14. free(p); 15. } 16. /* the right child is NULL */ 17. el if (!p->rchild) { 18. *root = p->lchild; 19. free(p); 20. } 21. /* the left child is NULL */ 22. el if (!p->lchild) { 23. *root = p->rchild; 24. free(p); 25. } 26. /* the node has both children */ 27. el { 28. s = p->rchild; 29. /* the s without left child */ 30. if (!s->lchild) 31. s->lchild = p->lchild; 32. /* the s have left child */ 33. el { 34. /* find the smallest node in the left subtree of s */ 35. while (s->lchild) { 36. /* record the parent node of s */ 37. parent = s; 38. s = s->lchild; 39. } 40. parent->lchild = s->rchild; 41. s->lchild = p->lchild; 42. s->rchild = p->rchild; 43. } 44. *root = s; 45. free(p); 46. } 47. } 48. el if (data > p->data) { 49. delete_bst_node(&(p->rchild), data); 50. } 51. el if (data < p->data) { 52. delete_bst_node(&(p->lchild), data); 53. } 54. }
运⾏两次，以不同的顺序输⼊相同的六个关键字：
根据前序遍历的结果可得到两次运⾏所产⽣的⼆叉查找树的形态并不相同，如下图： 01. int main(int argc, char *argv[]) 02. { 03. int i, num; 04. bst_p root = NULL; 05. 06. if (argc < 2) { 07. fprintf(stderr, "Usage: %s num\n", argv[0]); 08. exit(-1); 09. } 10. 11. num = atoi(argv[1]); 12. data_type arr[num]; 13. printf("Plea enter %d integers:\n", num); 14. for (i = 0; i < num; i++) { 15. scanf("%d", &arr[i]); 16. inrt_bst_node(&root, arr[i]); 17. } 18. 19. printf("\npre order traver: "); 20. pre_order_traver(root, print); 21. printf("\npost order traver: "); 22. post_order_traver(root, print); 23. printf("\n"); 24. 25. delete_bst_node(&root, 45); 26. 27. printf("\npre order traver: "); 28. pre_order_traver(root, print); 29. printf("\npost order traver: "); 30. post_order_traver(root, print); 31. printf("\n"); 32. 33. return 0; 34. }mssu
曲轴箱
