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

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

2016-10-29 2031
版权
举报
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 结构概念如下： 二叉排序树(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
重庆八怪
+关注
661文章
目录
打赏
0
0
0
0
91
分享
相关文章
修己xj
|
1天前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构，广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型（如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等）及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历，并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力，优化算法设计。
修己xj
29 9
算法系列之数据结构-二叉树
RossyYan
|
2月前
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
60 12
RossyYan
|
2月前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
57 10
RossyYan
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
55 2
三三是该溜子
|
3月前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
63 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
RossyYan
|
2月前
|
数据采集 存储 算法
【C++数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】
本文介绍了图的遍历算法，包括深度优先遍历（DFS）和广度优先遍历（BFS）。深度优先遍历通过递归方式从起始节点深入探索图，适用于寻找路径、拓扑排序等场景；广度优先遍历则按层次逐层访问节点，适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例，演示了如何实现这两种遍历方法，并附有测试用例及结果，帮助读者理解和实践图的遍历算法。
RossyYan
53 0
XIAZHI
|
4月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
138 4
ephemerals__
|
4月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
381 9
那年春天
|
4月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
64 1
RossyYan
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
158 77

热门文章

最新文章

  • 1
    c语言及数据结构实现简单贪吃蛇小游戏
    10
  • 2
    Redis原理—1.Redis数据结构
    4
  • 3
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
    2
  • 4
    算法系列之数据结构-二叉树
    29
  • 5
    STL——栈和队列和优先队列
    15
  • 6
    算法系列之数据结构-二叉搜索树
    40
  • 7
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
    8
  • 8
    【C++数据结构——查找】二分查找（头歌实践教学平台习题）【合集】
    2
  • 9
    C 408—《数据结构》易错考点200题（含解析）
    10
  • 10
    C 408—《数据结构》算法题基础篇—链表（上）
    5
  • 1
    算法系列之数据结构-二叉搜索树
    40
  • 2
    算法系列之数据结构-二叉树
    29
  • 3
    STL——栈和队列和优先队列
    16
  • 4
    Redis原理—1.Redis数据结构
    42
  • 5
    c语言及数据结构实现简单贪吃蛇小游戏
    56
  • 6
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
    30
  • 7
    C 408—《数据结构》算法题基础篇—链表（下）
    87
  • 8
    C 408—《数据结构》算法题基础篇—链表（上）
    97
  • 9
    C 408—《数据结构》算法题基础篇—数组（通俗易懂）
    72
  • 10
    C 408—《数据结构》图、查找、排序专题考点（含解析）
    76

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    通义万相：视觉生成大模型再进化