AI 助理
备案控制台
开发者社区 云计算 文章 正文

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

2016-10-29 2021
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 结构概念如下： 二叉排序树(binary sort tree): 1、也叫做二叉查找树 2、如果他的左子树不为空，则左子树上所有结点的 值均小于他的根结构的值 3、如果他的右子树不为空，则右子树上所有结点的 ...
结构概念如下：

二叉排序树(binary sort tree):

1、也叫做二叉查找树

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

值均小于他的根结构的值

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

值均大于他的根结构的值

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

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

下面就是一颗典型的二叉树，只是是字母，可以将字母换位字母的顺序进行审视，但是它不是平衡二叉树


排序二叉树(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;

  9. typedef struct BiTnode
  10. {
  11.         int data;
  12.         struct BiTnode *lchild,*rchild;
  13. } BiTnode,*BiTree;


  16. bool SearchBst(BiTree T,int key,BiTree *f,BiTree *p);
  17. bool InsertBst(BiTree *T,int key) ;
  18. void Inordervist(const BiTree T);
  19. void BTreedestroy(BiTree tree);
  20. bool DeleteBst(BiTree *T,int key);
  21. 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 = T's 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 p's parent poniter,
  12.    p = if sucess p is pointer to find node pointer,if failed is pointer to last
  13.    search node pointer

  15. */

  17. bool SearchBst(BiTree T,int key,BiTree *f,BiTree *p)
  18. {
  19.         if(!T)
  20.         {
  21.                 *p = *f;
  22.                 return false;
  23.         }
  24.         else if(key == T->data)
  25.         {
  26.                 *p = T;
  27.                 return true;
  28.         }
  29.         else if(key < T->data)
  30.         {
  31.                 *f = T;
  32.                 return SearchBst(T->lchild,key,f,p);
  33.         }
  34.         else
  35.         {
  36.                 *f = T;
  37.                 return SearchBst(T->rchild,key,f,p);
  38.         }
  39. }

  41. /*
  42.    T = Bst root node
  43.    key = key to insert
  44.    */
  45. bool InsertBst(BiTree *T,int key)
  46. {
  47.         BiTree p = NULL ,s = NULL ,f=NULL;
  48.         if(!SearchBst(*T,key,&f,&p)) //init NULL,KEY,NULL,&P=NULL
  49.         {
  50.                 s = (BiTree)calloc(1,sizeof(BiTnode));
  51.                 s->data =key;
  52.                 s->lchild = s->rchild = NULL;

  54.                 if(!p)
  55.                 {
  56.                         printf("Create Tree with key:%d\n",key);
  57.                         *T = s; //create Bst one node
  58.                 }
  59.                 else if(key < p->data)
  60.                 {
  61.                         printf("Insert Key To Tree(left):%d\n",key);
  62.                         p->lchild = s;
  63.                 }
  64.                 else
  65.                 {
  66.                         printf("Insert Key To Tree(right):%d\n",key);
  67.                         p->rchild = s;
  68.                 }
  69.                 return true;
  70.         }
  71.         else
  72.         {
  73.                 return false;
  74.         }
  75. }
  76. /*
  77. inorder traversal method
  78. */

  80. void Inordervist(const BiTree T)
  81. {
  82.         if(T)
  83.         {
  84.                 Inordervist(T->lchild);
  85.                 printf("%d\n",T->data);
  86.                 Inordervist(T->rchild);
  87.         }
  88. }

  90. /*
  91. postorder traversal method to destroy tree
  92. */

  94. void BTreedestroy(BiTree T)
  95. {

  97.         if(T)
  98.         {
  99.         BTreedestroy(T->lchild);
  100.         BTreedestroy(T->rchild);
  101.         printf("Delete node for Key%d\n",T->data);
  102.         xfree(T);
  103.         }
  104. }


  107. bool DeleteBst(BiTree *T,int key)//use **p *p is parent->child,here is very import
  108. {
  109.         if(!*T)//
  110.         {
  111.                 printf("no delete data %d find\n........\n",key);
  112.                 return true;
  113.         }
  114.         else
  115.         {
  116.                 if(key == (*T)->data)
  117.                 {
  118.                         return Delete(T);
  119.                 }
  120.                 else if(key < (*T)->data)
  121.                 {
  122.                         return DeleteBst(&(*T)->lchild,key);//here use lchild pointer's address
  123.                 }
  124.                 else
  125.                 {
  126.                         return DeleteBst(&(*T)->rchild,key);
  127.                 }
  128.         }
  129. }

  131. bool Delete(BiTree *p)//use **p *p is parent->child,here is very import
  132. {
  133.         BiTree q,s;

  135.         printf("delete data :%d\n........\n",(*p)->data);
  136.         if((*p)->rchild == NULL)//right node is NULL
  137.         {
  138.                 q = *p;
  139.                 *p = (*p)->lchild;
  140.                 xfree(q);
  141.         }
  142.         else if((*p)->lchild ==NULL)//leaf node is NULL
  143.         {
  144.                 q = *p;
  145.                 *p = (*p)->rchild;
  146.                 xfree(q);
  147.         }
  148.         else //exp:use ...20 30 50 (60 delete)... use 50 replace 60 ,use replace not free find node
  149.         {
  150.                 q = *p;
  151.                 //---------------
  152.                 s = (*p)->lchild;
  153.                 while(s->rchild) //if s->rchild is NULL q=*p mean (*p)->lchild s have no right node
  154.                 {
  155.                         q = s;
  156.                         s = s->rchild;
  157.                 }
  158.                 (*p)->data = s->data;

  160.                 /*-------------- here find near delete node small data,frist find lchild then find
  161.                 all small data root node then find last right node this is require data*/

  163.                 if(q!=*p) //if (*p)->lchild s have right node
  164.                 {
  165.                         q->rchild =s->lchild;
  166.                 }
  167.                 else // if (*p)->lchild s have no right node
  168.                 {
  169.                         q->lchild = s ->lchild;
  170.                 }
  171.                 xfree(s);//free find last right node,beacuse it's data used for find node
  172.         }
  173. }





点击(此处)折叠或打开

  1. 测试用例和主函数
  2. main.c
  3. #include<stdio.h>
  4. #include"bstort.h"


  7. int main(void)
  8. {
  9.         BiTree root = NULL;
  10.         InsertBst(&root,10);
  11.         InsertBst(&root,20);
  12.         InsertBst(&root,40);
  13.         InsertBst(&root,5);
  14.         InsertBst(&root,1);
  15.         InsertBst(&root,-1);
  16.         InsertBst(&root,-20);
  17.         InsertBst(&root,100);
  18.         printf("Use inorder traversal method:\n");
  19.         Inordervist(root);
  20.         DeleteBst(&root,30);
  21.         DeleteBst(&root,10);
  22.         printf("Use inorder traversal method:\n");
  23.         Inordervist(root);
  24.         printf("Use postorder traversal method destroy Bst:\n");
  25.         BTreedestroy(root);
  26. }

结构如下：
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，然后再次进行中序遍历，最后使用后续遍历删除。
可以看到结果如我们希望的。

关键词：
数据结构二叉树
数据结构查询
数据结构bst
数据结构遍历
数据结构排序
重庆八怪
目录
相关文章
XIAZHI
|
26天前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
75 4
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
124 8
Dylaniou
|
2月前
|
存储 缓存 索引
从底层数据结构和CPU缓存两方面剖析LinkedList的查询效率为什么比ArrayList低
本文详细对比了ArrayList和LinkedList的查询效率，从底层数据结构和CPU缓存两个方面进行分析。ArrayList基于动态数组，支持随机访问，查询时间复杂度为O(1)，且CPU缓存对其友好；而LinkedList基于双向链表，需要逐个节点遍历，查询时间复杂度为O(n)，且CPU缓存对其帮助不大。文章还探讨了CPU缓存对数组增删操作的影响，指出缓存主要作用于读取而非修改。通过这些分析，加深了对这两种数据结构的理解。
Dylaniou
47 2
java冯坚持
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
29 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
2月前
|
存储 算法 数据管理
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
这篇文章通过需求分析、代码实现和测试验证，详细介绍了二叉排序树的创建、遍历和删除操作，以及二叉平衡树（AVL）的自平衡特性和单旋转操作，旨在提高树结构在数据管理中的效率和性能。
java冯坚持
49 0
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
java冯坚持
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
32 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
阿客不是客
|
2月前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
30 0
java冯坚持
|
2月前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
31 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
166 9
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
30 1