二叉查找树

最新推荐文章于 2023-10-28 13:27:28 发布
最新推荐文章于 2023-10-28 13:27:28 发布
阅读量668 收藏 1
点赞数
分类专栏： 数据结构 面试问题

二叉树的先序遍历：NLR

中序遍历：LNR

后续遍历：LRN

N：访问结点本身
L：遍历该结点的左子树

R：遍历该结点的右子树


最近看《算法导论》，发现里面短短几页篇幅却包含着很多内容。要完全理解它可以试试不看书自己总结出来。如果可以不看书写出来才算真的"吃进去"了，否则都不算掌握了。大家可以检测下！借这篇文章来稍微总结下，便于以后查阅。

下面说说二叉查找树( Binary search tree)。

1、二叉查找树和二叉堆的区别(前者简称 bstree ，后者简称 heap)

区别一：性质不同。heap(此处默认说的是最小堆)的左右孩子节点都比父亲大，而bstree 的左孩子中的所有节点比父亲小，而右孩子中的所有节点比父亲大。

区别二：排序方式不同。heap 的根节点永远是最小节点，所以只需要依次弹出root节点，由此组成的序列即是；而 bstree 的中序遍历才得到的是排序结果。

区别三：堆有特殊性质，一般可用数组实现，index[parent] 等于 index[child]/2 。

2、二叉树操作中的难点

查找二叉树的前驱、后继，以及插入、删除操作！

------------------------------------------------------------------------------------------------------------------------------------

下面依次列出各种操作的伪码：

遍历

1、递归实现中序遍历

遍历整棵树可以调用 PRINT-BSTREE(root[T])。

PRINT-BSTREE(x)
    if x ≠ NIL  then    //只能这么表示"不等于"了，"NIL"相当于"NULL指针"
       PRINT-BSTREE(left[x])
       print key[x]
       PRINT-BSTREE(right[x])

2、非递归中序遍历(需要借助Stack来实现)

PRINT-BSTREE(x)
    S <---- {NIL}   //无法输入书中那种集合空，暂用"{NIL}"来替代   
    while TRUE do        
        if left[x] ≠ NIL then
           x <--- left[x]
           PUSH(S, x)  //将该节点压入栈
        else 
           print key[x]   // 如果没有左孩子了，则输出该节点
           if right[x] ≠ NIL then
              x <---- right[x]
           else
              if S == {NIL} then
                 break   // 循环退出条件：到达叶子节点，且栈为空，即已经输出最后那个节点
             else  x <----  POP(S) //到达叶子节点了，该节点没有孩子


查找

1、递归查找某个元素

如果要从根节点开始查找，则调用 FIND-RECURSION(root[T], k)。

FIND-RECURSION(x,k)
    if x ≠ NIL and key[x] ≠ k then
       if k < key[x] then
          return FIND-RECURSION(left[x], k)
       else
          return FIND-RECURSION(right[x], k)

    return x //返回指向这个节点的指针，或者没找到，返回空

2、非递归查找某个元素

FIND(x,k)
    while x ≠ NIL and key[x] ≠ k do
       if k < key[x] then
          x <--- left[x]
       else
         x <--- right[x]
     return x

3、查找树的最小值(在查找前驱和后继的时候有用)

FIND-MIN(x)
    y <--- NIL
    while left[x] ≠ NIL do
        y <---- x
        x <---- left[x]  
    return y

4、查找树的最大值

FIND-MAX(x)
    y <--- NIL
    while right[x] ≠ NIL do
        y <---- x
        x <---- right[x]  
    return y

5、查找某个元素的前驱

如果知道元素的值，比如 k，可以先用 p = FIND(x,k) 得到指向该节点的指针，然后再调用下面的函数 FIND-PREV(p)

FIND-PREV(x)   //暂且用prev这个词来代表 "前驱"
    if left[x]  ≠  NIL then
       return FIND-MAX(left[x]) //如果该节点有左孩子，则左子树中最大的节点就是它的前驱
    else 
       y <--- p[x]   //p[x]表示x节点的父节点
       while y ≠ NIL and right[y] ≠ x  do
           x <--- y
           y <--- p[y]
      return y  //如果x没有左孩子，则它的前驱肯定是它的某个父亲，满足这个条件：某个父亲P 的右子树包含了x(或者说x所在的子树) ，则P 就是x的前驱。

6、查找某个元素的后继(和前驱类似)

FIND-NEXT(x)   //暂且用next这个词来代表 "后继"
    if right[x] ≠  NIL then
       return FIND-MIN(right[x]) //如果该节点有右孩子，则右子树中最小的节点就是它的后继
    else 
       y <--- p[x]   //p[x]表示x节点的父节点
       while y ≠ NIL and left[y] ≠ x  do
           x <--- y
           y <--- p[y]
      return y  //如果x没有右孩子，则它的前驱肯定是它的某个父亲，满足这个条件：某个父亲P 的左子树包含了x(或者说x所在的子树) ，则P 就是x的后继。


插入

向二叉树中插入节点，先需要生成节点m，然后调用 INSERT(T, m)。

INSERT(T,m)  
    x <---- root[T] 
    y <--- NIL    //用来记录要插入节点位置的父亲
    while x ≠ NIL do //寻找要插入的位置
        y <--- x
        if key[m] < key[x]  then
           x <--- left[x]
        else
           x <--- right[x]
    p[m] <--- y   //对该节点的parent指针赋值
    if y == NIL  then
       root[T] <--- m
    else if key[m] < key[y] then
              left[y] <--- m
    else    right[y] <--- m


删除

删除操作是最复杂的，该节点分三种情况：没有孩子，有一个孩子，有两个孩子。对于两个孩子的情况，我们采用"逻辑删除"，也就是删除掉它的"后继"节点，把这个节点的值赋给要删除的节点！

先要通过 m = FIND(root[T],k) 来找到这个要删除节点的指针，而后调用 DELETE(T, m)来删除

DELETE(T,m)
     x <--- NIL 
     y <--- NIL
     if left[m]==NIL or right[m]==NIL then
        x <--- m   //如果至多只有一个孩子，则x指向该节点本身
     else
        x <--- FIND-NEXT(m)  // 如果有两个孩子，则x指向m的后继节点，由于后继节点没有左孩子，所以可以将删除后继的操作和上面结合起来
     
     if left[x] ≠ NIL then    //x指向的是y节点的孩子节点(y最多有一个孩子)，如果没有则y为NULL
        y <--- left[x]
     else
        y <--- right[x]

     if y ≠  NIL then  //修改孩子节点的父节点
        p[y] <--- p[x]
    
     if p[y] == NIL then
        root[T] <---- y         //删除的刚好是根节点
     else  if left[p[x]] == x then
        left[p[x]] <--- y
     else 
        right[p[x]] <--- y

     if x ≠ m then
        key[m] <----- key[x]  //把x节点的内容copy给m节点，以实现逻辑上删除m节点

     delete x     


C语言的源代码如下，仅做参考：

[cpp]  view plain copy print ?
  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #include<assert.h>  
  4.   
  5. //二叉树节点  
  6. typedef struct node{  
  7.     int data;  
  8.     struct node *left,*right,*parent;  
  9. }bsnode;  
  10.   
  11. //遍历二叉树(中序)  
  12. void print_bstree(bsnode *tree){  
  13.     if(tree!=NULL){  
  14.         print_bstree(tree->left);//递归  
  15.         printf("%d,",tree->data);  
  16.         print_bstree(tree->right);  
  17.     }  
  18. }  
  19.   
  20. //查找元素(非递归)  
  21. bsnode * find(bsnode *tree,int k){  
  22.     while(tree!=NULL && tree->data !=k){  
  23.         if(k < tree->data){  
  24.             tree = tree->left;  
  25.         }else{  
  26.             tree = tree->right;  
  27.         }  
  28.     }  
  29.     return tree;//返回指向data域等于k的节点的指针！  
  30. }  
  31.   
  32. //查找元素(递归)  
  33. bsnode * re_find(bsnode *tree,int k){  
  34.     if(tree==NULL ||  tree->data ==k){  
  35.         return tree;      
  36.     }else if(k < tree->data){  
  37.         return re_find(tree->left,k);  
  38.     }else{  
  39.         return re_find(tree->right,k);  
  40.     }  
  41. }  
  42.   
  43. //求最小值(给定一个二叉查找树的根snode，求这颗树的最小节点)  
  44. bsnode * find_min(bsnode *snode){  
  45.     bsnode *p=NULL;  
  46.     while(snode!=NULL){  
  47.         p=snode;  
  48.         snode=snode->left;  
  49.     }  
  50.     return p;//树的最左子树叶节点  
  51. }  
  52.   
  53. //求最大值  
  54. bsnode * find_max(bsnode *snode){  
  55.     bsnode *p=NULL;  
  56.     while(snode!=NULL){  
  57.         p=snode;  
  58.         snode=snode->right;  
  59.     }  
  60.     return p;  
  61. }  
  62.   
  63. //查找前驱  
  64. bsnode * find_prev(bsnode *m){  
  65.     assert(m!=NULL);  
  66.     if(m->left != NULL){  
  67.         return find_max(m->left);      
  68.     }else{  
  69.         //寻找m的祖先中满足这样关系的点：righ[p[m]] == m  
  70.         bsnode *p = m->parent;  
  71.         bsnode *child = m;  
  72.         while(p!=NULL && p->right != child){  
  73.             child=p;  
  74.             p=child->parent;  
  75.         }  
  76.         return p;  
  77.     }  
  78. }  
  79.   
  80. //查找后继  
  81. bsnode * find_next(bsnode *m){  
  82.     assert(m==NULL);  
  83.     if(m->right !=NULL){  
  84.         return find_min(m->right);  
  85.     }else{  
  86.         bsnode *p=m->parent;  
  87.         bsnode *child=m;  
  88.         while(p!=NULL && p->left != child){  
  89.             child=p;  
  90.             p=p->parent;  
  91.         }  
  92.         return p;  
  93.     }  
  94. }  
  95.   
  96. //插入元素(递归)  
  97. bsnode *re_insert(bsnode *tree,bsnode *newer){  
  98.     if(tree==NULL){  
  99.         tree=newer;  
  100.     }else{  
  101.         if(newer->data < tree->data){  
  102.             tree->left=re_insert(tree->left,newer);  
  103.         }else{  
  104.             tree->right=re_insert(tree->right,newer);  
  105.         }  
  106.     }  
  107.     return tree;  
  108. }  
  109.   
  110. //插入元素(非递归)  
  111. bsnode *insert(bsnode *tree,bsnode *newer){  
  112.     bsnode *root=tree;  
  113.     bsnode *p= NULL;  
  114.     while(root!=NULL){  
  115.         p=root;  
  116.         if(newer->data < root->data){//往左子树  
  117.             root=root->left;  
  118.         }else{  
  119.             root=root->right;  
  120.         }  
  121.     }//p指针就是要插入节点的父亲  
  122.   
  123.     newer->parent = p;//修改parent指针，让其指向父亲  
  124.   
  125.     if(p==NULL){//只有一个节点  
  126.         tree = newer;  
  127.     }else{  
  128.         if(newer->data < p->data){  
  129.             p->left=newer;  
  130.         }else{  
  131.             p->right=newer;  
  132.         }  
  133.     }  
  134.   
  135.     return tree;  
  136. }  
  137.   
  138. //删除元素  
  139. bsnode * delete(bsnode *tree,int k){  
  140.     bsnode *delnode = find(tree,k);  
  141.     if(delnode ==NULL){  
  142.         printf("要删除的节点不存在！请检查\n");  
  143.     }else{  
  144.         bsnode *xnode = NULL;  
  145.         bsnode *ynode = NULL;   
  146.         if(delnode->left == NULL || delnode->right == NULL){  
  147.             xnode = delnode;//delnode有一个孩子或者没有，则xnode表示它本身  
  148.         }else{  
  149.             xnode = find_next(delnode);//delnode有两个孩子，xnode则表示它的后继节点  
  150.         }  
  151.   
  152.         //得到xnode的孩子节点  
  153.         if(xnode->left != NULL){  
  154.             ynode = xnode->left;  
  155.         }else{  
  156.             ynode = xnode->right;  
  157.         }  
  158.   
  159.         if(ynode != NULL){  
  160.             ynode->parent = xnode->parent;  
  161.         }  
  162.   
  163.         if(xnode->parent == NULL){  
  164.             tree = ynode;     
  165.         }else{  
  166.             if(xnode->parent->left == xnode){  
  167.                 xnode->parent->left = ynode;  
  168.             }else{  
  169.                 xnode->parent->right = ynode;  
  170.             }  
  171.         }  
  172.   
  173.         if(xnode != delnode){//两个孩子的情况，得将后继节点的值赋给delnode,以实现逻辑删除  
  174.             delnode->data = xnode->data;  
  175.         }  
  176.   
  177.         //删除掉节点  
  178.         free(xnode);  
  179.     }  
  180.   
  181.     return tree;  
  182. }  
  183.   
  184. int main(){  
  185.     bsnode *tree=NULL;  
  186.     int data[]={10,2,11,3,8,6,1,7};  
  187.     int i;  
  188.     for(i=0;i<sizeof(data)/sizeof(int);i++){  
  189.         bsnode *newer = (bsnode *)malloc(sizeof(bsnode));  
  190.         newer->data=data[i];  
  191.         newer->left=newer->right=newer->parent=NULL;  
  192.         tree = insert(tree,newer);//插入  
  193.     }  
  194.     print_bstree(tree);//中序遍历  
  195.     printf("\n");  
  196.       
  197.     tree = delete(tree,2);//删除节点  
  198.     print_bstree(tree);  
  199.     printf("\n");  
  200.     return 0;  
  201. }  

如果转载，请标明出处 blog.csdn.net/whuslei

二叉堆(Heap)与二叉查找树(Binary Search Tree)的区别
YUBANGSHUANGYUER的博客
05-08 4258
问题描述 通常我们在学习二叉堆和二叉查找树时是很容易混淆的，虽说堆也是一种完全二叉树，但二者差别还是挺大的，本文试做分析。 逻辑结构 二叉堆和二叉查找树都是结点带权重，并在父子结点间满足某种规则的数据结构。 二叉堆是一种完全二叉树，分大根堆、小根堆两种，子结点总是大于或小于父结点。 大根堆，顾名思义，根是最大的，每个子结点都要小于父结点，不区分左右儿子谁大谁小，也不必保证某个“孙子结点”一定要小于另一个“儿子结点”。 小根堆恰恰相反，根是最小的，每个子结点都要大于父结点，不区分左右儿子谁大谁小，也不
二叉树+二叉树搜索树+堆
我是传奇
01-15 176
二叉树 二叉树的几个性质 1在二叉树的第i层最多有2^(i-1)个节点 2深度为k的二叉树最少有k个节点，最多2^k-1个节点 3对于任何一颗非空二叉树，如果其叶子节点数为n0，度为2的非叶子节点个数为n2= n0-1 4具有n个节点的完全二叉树的深度为log(n+1) 5有前序序列和中序序列可以唯一确定一颗二叉树 6如果有n个节点，那么二叉树的不同形态有[1/(n+1)]...
数据结构与算法学习③(二叉树,二叉搜索树,堆)
m0_46690280的博客
11-26 647
数据结构与算法学习③数据结构与算法学习③1、树1.1、定义1.2、相关概念2、二叉树2.1、二叉树概述2.1.1、定义及特点2.1.2、分类 数据结构与算法学习③ 1、树 前面学习的：数组，链表，栈，队列，散列表，集合等均属于线性数据结构。而树及后面要学习的一些数据结构属于非线性数据结构！ 1.1、定义 树在维基百科中的定义为：树（英语：Tree）是一种无向图（undirected graph），其中任意两个顶点间存在唯一一条路径。或者说，只要没有回路的连通图就是树。在计算机科学中，树（英语：tree）是一
二叉堆和二叉查找树
weixin_43598885的博客
01-18 215
二叉堆是由构造完全平衡树和堆次序排序两步组成 二叉堆的操作都是先满足完全平衡树的结构变化，然后处理堆次序
二叉查找树 减治法——C++代码
05-24
二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，它的每个节点都包含一个键（key）、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二叉查找树中，对于任意节点，其左子树中的...
二叉查找树python二叉查找树源码
11-22
二叉查找树（Binary Search Tree，BST），也称为二叉排序树，是一种特殊的二叉树数据结构。它的每个节点都包含一个键（key）、一个关联的值、一个指向左子节点的指针和一个指向右子节点的指针。在二叉查找树中，对于...
最优二叉查找树 动态规划法.cpp.rar
10-14
最优二叉查找树（Optimal Binary Search Tree, OBST）是一种高效的检索数据结构，它根据键值分布的不同，自适应地调整树的形态以达到最小化查找时间的目的。在计算机科学中，动态规划（Dynamic Programming, DP）是...
JS实现二叉查找树的建立以及一些遍历方法实现
10-20
在计算机科学中，二叉查找树（BST）是一种特殊的二叉树结构，它满足所有节点的左子树都小于该节点，所有节点的右子树都大于该节点。这种特性使得二叉查找树在查找、插入和删除元素时可以提供很高的效率。本文将详细...
二叉排序树和堆的区别
TO BE SMART
08-09 7589
1、结构上： 二叉排序树：左子树小于根节点，根节点又小于右子树。 堆（小堆）：根节点小于左右子树，但是左右子树没有大小之分。 2、作用上： 从上面各自的结构上的分析可得：二叉排序树是用来做查找的，而堆是用来做排序的。...
堆和树的区别？应用场景？二叉搜索树是什么？
最新发布
xivictor的博客
10-28 465
通过比较节点的值，可以快速确定需要操作的子树，从而提高了操作的效率。对于任意节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。堆中的每个节点都满足堆属性，即父节点的值要么大于等于（最大堆）或小于等于（最小堆）其子节点的值。树是由节点和边构成的集合，其中一个节点被指定为根节点，其他节点可以分为若干个无序的子树。堆是一个完全二叉树，即除了最后一层外，其他层都是满的，且最后一层的节点从左到右排列。堆常被用于实现优先队列，它可以快速找到最大（或最小）值的节点。
堆和二叉树的区别
luzhensmart的专栏
05-04 5570
以小根堆为例，堆的特点是双亲结点的关键字必然小于等于孩子结点的关键字，而两个孩子结点的关键字没有次序规定， 而二叉排序数中，每个双亲结点的关键字均大于左子树结点的关键字，均小于右子树j结点的关键字，也就是说，每个双亲结点的左右孩子的关键字有次序关系， 这样，当对两种树执行中序遍历后，二叉树会得到一个有序的序列，而堆不一定。 堆 堆是什么？堆是一种特殊的完全二叉树，只不过父亲与儿子节点间有关系...
堆与二叉排序树的区别
进阶的小宋
08-24 1438
学习
二叉树及堆；二叉搜索树
weixin_41012399的博客
07-06 1111
首先明确：完全二叉树；满二叉树；平衡二叉树是根据树的样子不同命名的。而堆；二叉搜索树是根据节点的值大小命名的。 三种特殊二叉树（Binary Tree）的概念： 完全二叉树：除了最高层以外，其余层节点个数都达到最大值，并且最高层节点都优先集中在最左边。 满二叉树：除了最高层有叶子节点，其余层无叶子，并且非叶子节点都有2个子节点。 平衡二叉树：一棵空树或左右两个子树的高度差的绝对值不超过1，并且左右...
二叉树与堆
pigern的博客
04-16 2700
目录树树的定义树的相关概念树的表示树的应用二叉树二叉树的定义二叉树特点二叉树性质二叉树的存储结构堆 树 树的定义 树是一种数据结构，树结构只有一个根节点，除根节点外，其余节点被分成M(M>0) 个互不相交的集合T1,T2,T3,…,Tm. 其中每一个集合Ti(1 < i < m)又是一颗与树结构类似的子树。每个子树的根节点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。 如图是一颗树结构： 由于树结构只有一个前驱，所以树结构不能出现交叉，如下不是一棵树结构 这种结构称为树
二叉树和二叉堆
qq_45980336的博客
08-04 968
一、二叉树 1.基本概念 　　二叉树是一个特殊的树，其中每个结点最多只能有两个子结点，也可以为空树。二叉树每个结点最多两个孩子，也就最多只能有两个子树，分别称为左、右子树，左、右子孩子。 　　一棵树中除了叶子节点外，其余所有结点都有两个孩子，称为满二叉树。而如果由一个满二叉树缺失掉最高层级的最右端部分结点的树，称为完全二叉树。对于完全二叉树，叶子结点只会出现在最高的两个层级，且如果一个结点有左孩子结点，那么它必定有右孩子结点。 2.性质 （1）二叉树的第i层上，最多只能有2^(i-1)次方个结点。 　　因为
二叉树和堆详解（通俗易懂）
weixin_61661271的博客
06-13 3883
树形结构指的是数据元素之间存在着“一对多”的树形关系的数据结构，是一类重要的非线性数据结构，本篇重点讲解它。
详解二叉查找树BST及其遍历算法
二叉查找树（Binary Search Tree，简称BST）是一种重要的数据结构，它支持多种动态集合操作，如查找、插入、删除等。在计算机科学与信息处理领域中，BST是一种广泛应用于各种系统和应用的高效数据结构，特别是在需要...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值