1. 首页
  2. IT资讯

数据结构 排序二叉树(BST) 插入删除查询 中序遍历 销毁(后序遍历)

结构概念如下:

二叉排序树(binary sort tree):

1、也叫做二叉查找树

2、如果他的左子树不为空,则左子树上所有结点的

值均小于他的根结构的值

3、如果他的右子树不为空,则右子树上所有结点的

值均大于他的根结构的值

4、他的左右子树分别为二叉排序树

5、按照二叉树中序遍历其返回结果树有序的

下面就是一颗典型的二叉树,只是是字母,可以将字母换位字母的顺序进行审视,但是它不是平衡二叉树
数据结构 排序二叉树(BST) 插入删除查询 中序遍历 销毁(后序遍历)

排序二叉树(BST)的优点在于进行数据查找比较方便,因为他是按照数据来到的顺序进行如上的规则进行的
建树,只要如上的规则进行查找就能找到需要的数据。但是其缺点也是显而易见,树的深度是不可控制的
而且可能极不均匀,考虑 1 2 3 4 5 6 7,这样的数据建树全部节点都在左子树上,级不均匀。那么给
搜索数据的性能带来的较大的影响,所以引入了AVL树平衡二叉树,这个在后面再说

关于排序二叉树BST的各种操作都使用了递归算法,给出递归算法一张我认为很好的图:

这张图实际体现了递归的真谛 顺序调用反向返回,这个列子和图来自小甲鱼C视频也可能来自大话数据结构
上面的代码实际上是:

void print()
{
    char a;
    scanf(“%c”,&a);
      if(a!=’#’) print();
      if(a!=’#’) printf(“%c”,a);
}

关于递归的经典 费布那切数列和汉诺塔等都可以了解一下;
下面回归正题,直接给出代码和测试用例。说明代码大部分来自大话数据结构,销毁和中序遍历是我自己写的,但是我自己进行了理解。
主要删除数据比较难,分为3种情况
1、删除节点的左子树为空,更改*p = (*p)->rchild;注意这里的*p代表的是parent->child,所以这样做就是将父节原来指向删除节点的指针,指向删除节点的下一个右孩子
2、删除节点的右子树为空,同理更改*p = (*p)->lchild;注意这里的*p代表的是parent->child,所以这样做就是将父节原来指向删除节点的指针,指向删除节点的下一个左孩子
3、删除节点左右子树都不为空,需要进行找到直接前驱或者直接后继节点进行数据代替。这个就比较复杂直接看代码吧
分别进行讨论。 
其他操作相对简单不用再秒素就是递归,但是需要注意排序返回数据是用中序遍历,销毁树用的是后序遍历。
代码如下:

点击(此处)折叠或打开

  1. 头文件
  2. bstort.h
  3. #include<stdio.h>
  4. typedef int bool;
  5. #define false 0
  6. #define true 1
  7. #define xfree(x) free(x); x = NULL;
  8. typedef struct BiTnode
  9. {
  10.         int data;
  11.         struct BiTnode *lchild,*rchild;
  12. } BiTnode,*BiTree;
  13. bool SearchBst(BiTree T,int key,BiTree *f,BiTree *p);
  14. bool InsertBst(BiTree *T,int key) ;
  15. void Inordervist(const BiTree T);
  16. void BTreedestroy(BiTree tree);
  17. bool DeleteBst(BiTree *T,int key);
  18. bool Delete(BiTree *p);

点击(此处)折叠或打开

  1. 实现程序
  2.  bstort.c
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include“bstort.h”
  6. /*
  7.    T = Bst root node
  8.    key = search key
  9.    f = Ts parent node,used if search failed save last search node pointer
  10.    if search failed last T is NULL,inital vlaues is NULL,
  11.    is sucuess f is pointer to ps parent poniter,
  12.    p = if sucess p is pointer to find node pointer,if failed is pointer to last
  13.    search node pointer
  14. */
  15. bool SearchBst(BiTree T,int key,BiTree *f,BiTree *p)
  16. {
  17.         if(!T)
  18.         {
  19.                 *p = *f;
  20.                 return false;
  21.         }
  22.         else if(key == T>data)
  23.         {
  24.                 *p = T;
  25.                 return true;
  26.         }
  27.         else if(key < T>data)
  28.         {
  29.                 *f = T;
  30.                 return SearchBst(T>lchild,key,f,p);
  31.         }
  32.         else
  33.         {
  34.                 *f = T;
  35.                 return SearchBst(T>rchild,key,f,p);
  36.         }
  37. }
  38. /*
  39.    T = Bst root node
  40.    key = key to insert
  41.    */
  42. bool InsertBst(BiTree *T,int key)
  43. {
  44.         BiTree p = NULL ,s = NULL ,f=NULL;
  45.         if(!SearchBst(*T,key,&f,&p)) //init NULL,KEY,NULL,&P=NULL
  46.         {
  47.                 s = (BiTree)calloc(1,sizeof(BiTnode));
  48.                 s>data =key;
  49.                 s>lchild = s>rchild = NULL;
  50.                 if(!p)
  51.                 {
  52.                         printf(“Create Tree with key:%dn”,key);
  53.                         *T = s; //create Bst one node
  54.                 }
  55.                 else if(key < p>data)
  56.                 {
  57.                         printf(“Insert Key To Tree(left):%dn”,key);
  58.                         p>lchild = s;
  59.                 }
  60.                 else
  61.                 {
  62.                         printf(“Insert Key To Tree(right):%dn”,key);
  63.                         p>rchild = s;
  64.                 }
  65.                 return true;
  66.         }
  67.         else
  68.         {
  69.                 return false;
  70.         }
  71. }
  72. /*
  73. inorder traversal method
  74. */
  75. void Inordervist(const BiTree T)
  76. {
  77.         if(T)
  78.         {
  79.                 Inordervist(T>lchild);
  80.                 printf(“%dn”,T>data);
  81.                 Inordervist(T>rchild);
  82.         }
  83. }
  84. /*
  85. postorder traversal method to destroy tree
  86. */
  87. void BTreedestroy(BiTree T)
  88. {
  89.         if(T)
  90.         {
  91.         BTreedestroy(T>lchild);
  92.         BTreedestroy(T>rchild);
  93.         printf(“Delete node for Key%dn”,T>data);
  94.         xfree(T);
  95.         }
  96. }
  97. bool DeleteBst(BiTree *T,int key)//use **p *p is parent>child,here is very import
  98. {
  99.         if(!*T)//
  100.         {
  101.                 printf(“no delete data %d findn……..n”,key);
  102.                 return true;
  103.         }
  104.         else
  105.         {
  106.                 if(key == (*T)>data)
  107.                 {
  108.                         return Delete(T);
  109.                 }
  110.                 else if(key < (*T)>data)
  111.                 {
  112.                         return DeleteBst(&(*T)>lchild,key);//here use lchild pointers address
  113.                 }
  114.                 else
  115.                 {
  116.                         return DeleteBst(&(*T)>rchild,key);
  117.                 }
  118.         }
  119. }
  120. bool Delete(BiTree *p)//use **p *p is parent>child,here is very import
  121. {
  122.         BiTree q,s;
  123.         printf(“delete data :%dn……..n”,(*p)>data);
  124.         if((*p)>rchild == NULL)//right node is NULL
  125.         {
  126.                 q = *p;
  127.                 *p = (*p)>lchild;
  128.                 xfree(q);
  129.         }
  130.         else if((*p)>lchild ==NULL)//leaf node is NULL
  131.         {
  132.                 q = *p;
  133.                 *p = (*p)>rchild;
  134.                 xfree(q);
  135.         }
  136.         else //exp:use ...20 30 50 (60 delete)... use 50 replace 60 ,use replace not free find node
  137.         {
  138.                 q = *p;
  139.                 //
  140.                 s = (*p)>lchild;
  141.                 while(s>rchild) //if s>rchild is NULL q=*p mean (*p)>lchild s have no right node
  142.                 {
  143.                         q = s;
  144.                         s = s>rchild;
  145.                 }
  146.                 (*p)>data = s>data;
  147.                 /* here find near delete node small data,frist find lchild then find
  148.                 all small data root node then find last right node this is require data*/
  149.                 if(q!=*p) //if (*p)>lchild s have right node
  150.                 {
  151.                         q>rchild =s>lchild;
  152.                 }
  153.                 else // if (*p)>lchild s have no right node
  154.                 {
  155.                         q>lchild = s >lchild;
  156.                 }
  157.                 xfree(s);//free find last right node,beacuse its data used for find node
  158.         }
  159. }

点击(此处)折叠或打开

  1. 测试用例和主函数
  2. main.c
  3. #include<stdio.h>
  4. #include“bstort.h”
  5. int main(void)
  6. {
  7.         BiTree root = NULL;
  8.         InsertBst(&root,10);
  9.         InsertBst(&root,20);
  10.         InsertBst(&root,40);
  11.         InsertBst(&root,5);
  12.         InsertBst(&root,1);
  13.         InsertBst(&root,1);
  14.         InsertBst(&root,20);
  15.         InsertBst(&root,100);
  16.         printf(“Use inorder traversal method:n”);
  17.         Inordervist(root);
  18.         DeleteBst(&root,30);
  19.         DeleteBst(&root,10);
  20.         printf(“Use inorder traversal method:n”);
  21.         Inordervist(root);
  22.         printf(“Use postorder traversal method destroy Bst:n”);
  23.         BTreedestroy(root);
  24. }

结构如下:
Create Tree with key:10
Insert Key To Tree(right):20
Insert Key To Tree(right):40
Insert Key To Tree(left):5
Insert Key To Tree(left):1
Insert Key To Tree(left):-1
Insert Key To Tree(left):-20
Insert Key To Tree(right):100
Use inorder traversal method:
-20
-1
1
5
10
20
40
100
no delete data 30 find
……..
delete data :10
……..
Use inorder traversal method:
-20
-1
1
5
20
40
100
Use postorder traversal method destroy Bst:
Delete node for Key-20
Delete node for Key-1
Delete node for Key1
Delete node for Key100
Delete node for Key40
Delete node for Key20
Delete node for Key5

这里首先演示了建树,然后演示了中序遍历返回有序的结果,然后删除一个不包含的数据30,
然后删除一个包含的数据10,然后再次进行中序遍历,最后使用后续遍历删除。
可以看到结果如我们希望的。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7728585/viewspace-2127320/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:深沉的少年,转转请注明出处:http://www.cxybcw.com/183876.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code