程序员经验分享-hwhale

【数据结构】树（五）—— 二叉排序树（C语言版）

2023-10-26

前言

二叉排序树(Binary Sort Tree,BST)又称为二叉查找树、二叉搜索树。与树型查找有关的结构有二叉排序树，平衡二叉树，红黑树，B树，键树等。
其具有动态性。

一、二叉排序树的定义

二叉排序树有两种类型：
(1) 空树；
(2) 满足下列条件的树:

条件：

  1. 如果它的左子树不为空，那么左子树上的所有结点的值均小于它的根结点的值；
  2. 如果它的右子树不为空，那么右子树上的左右结点的值均大于它的根结点的值；
  3. 根结点的左子树和右子树又是二叉排序树。

二、二叉排序树的性质

处上述定义中的特点外，二叉排序树还有下述常用性质:

  1. 中序遍历二叉排序树便可得到一个有序序列；
  2. 一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程；
  3. 二叉排序树是一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字值等于给定值的结点是再进行插入；
  4. 插入的结点一定是一个新添加的叶结点，且是查找失败时查找路径上访问的最后一个结点的左孩子或者右孩子；
  5. 二叉排序树通常采用二叉链表作为存储结构。

注：由三、四两点性质可知，二叉排序树（二叉搜索树）的创建与插入操作关联极大，故编写代码时应有所思考二者之间的关联

三、二叉排序树的操作

  • 查找
  • 插入
  • 创建
  • 删除

注： 下述代码部分来源于王道408数据结构，部分为自己补充

1. 二叉排序树常用存储结构

二叉排序树通常采用二叉链表作为存储结构

/* 二叉排序树的节点结构定义 */
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BSTNode, *BiTree;

2. 二叉排序树的查找

(递归实现)查找"二叉树T"中键值为 key 的节点
BSTNode* bstree_search(BSTree T, ElemType key)
{
    if (x==NULL || T->data == key)
        return x;
    if (key < T->key)
        return bstree_search(T->left, key);
    else
        return bstree_search(T->right, key);
}
(非递归实现)查找"二叉树T"中键值为 key 的节点
BSTNode* iterative_bstree_search(BSTree T, ElemType key)
{
    while ((T!=NULL) && (T->data!=key))
    {
        if (key < T->data)
            T = T->left;
        else
            T = T->right;
    }
    return T;
}

3. 二叉排序树的插入


int BST_Insert(Bitree &T, ElemType k)
{
    if (T==NULL)
    {
        T = (Bitree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if (k == T->data)//存在相同关键字的结点，则插入失败
        return 0;
    else if (k < T->data) // 插入到 T 的右子树
        return BST_Insert(T->lchild, k);
    else                    // 插入到 T 的左子树
        return BST_Insert(T->rchild, k);
}

4. 二叉排序树的创建

在这里插入图片描述

Bitree create_BST(ElemType str[], int n)//n 为结点数
{
    Bitree T = (Bitree)malloc(sizeof(BSTNode)); // 建立二叉排序树的头结点
    T = NULL; //先将指针设为空；
    int i = 1;
    while(i<n)
    {
        BST_Insert(T, str[i]);
        i ++;
    }
    return T;
}

5. 二叉排序树的删除

  1. 若被删除的结点是叶子结点，直接删除即可；
  2. 若被删除的结点只有左子树或者右子树，则让该结点的子树成为该结点父结点的子树，即替代被删除结点的位置；
  3. 若被删除的结点有左子树和右子树，则让该结点的直接后继（或者直接前驱）替代，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转换成了第一或第二种情况；

下面主要介绍被删除的结点有左子树和右子树的情况，分为两种方式前驱替代和后继替代

（一）使用后继结点替代

如下图，当删除 结点“50” 时， 使用后继结点替代，为满足二叉排序树的特点，需要找其右子树中的最小值，使用右子树中结点值最小的结点（下图中的结点“60”）进行替代，删除原来子树的结点“60”相当于情况一或情况二。

在这里插入图片描述

在这里插入图片描述

直接后继插入：
在这里插入图片描述

（二）使用前驱结点替代

同理，使用后继结点替代，相当于找 结点“50” 的左子树中的结点值最大的结点“30”，效果如下。

在这里插入图片描述

总结：

  1. 使用删除结点Z 的后继结点：Z 的右子树中最左下结点（该结点一定没有左子树）；结点被替代后用右子树替代即可

  2. 使用删除结点Z 的前驱结点：Z 的左子树中最右下结点（该结点一定没有右子树）：结点被替代后用左子树替代即可

上述二种叙述不记忆，其实相当于对树进行中序遍历，采用被删除结点的前驱结点或者后继结点进行替代。

四、二叉树的查找性能分析

二叉排序树的查找效率，主要取决于树的高度

最好的情况：与折半查找类似，查找过程中和关键字比较的次数不超过树的深度。

当二叉排序树形态比较对称(特别地，如二叉排序树的左、右子树的高度差的绝对值不超过1，即平衡二叉树)，此时与折半查找相似，时间复杂度为O(log2n)，

最坏情况：即输入序列为有序数列时，二叉排序树是一颗单树(只有左子树或只有右子树)，树的深度为n，其平均查找长度为(n + 1) / 2，时间复杂度为O(n)，等同于顺序查找。

因此，如果希望对一个集合按二叉排序树查找，最好是要对排序树进行一些必要的优化，如下：

加权平衡树(WBT)
AVL树 (平衡二叉树)
红黑树
Treap(Tree+Heap)

这些均可以使查找树的高度为 ：O(log（n）)。

五、应用区分：（与二分查找的应用区分）

就维护表的有序性而言，二叉排序树无序移动结点，只需要修改指针即可完成插入和删除操作，平均执行时间为O(log2n)。

二分查找的对象是 有序顺序表，若完成插入和删除操作结点的操作，所花的代价是O(n)。

结论：

当有序表是静态查找表，宜用顺序表作为其存储结构，采用二分查找实现其查找操作；

当有序表为动态查找表时，应选择二叉排序树作为其逻辑结构

六、二叉排序树的构造树结构分析

使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关。即使查找表中各数据元素完全相同，但是不同的排列顺序，构建出的二叉排序树大不相同。

例如：查找表 {45，24，53，12，37，93} 和表 {12，24，37，45，53，93} 各自构建的二叉排序树图下图所示：

在这里插入图片描述

七、完整可运行代码

注： 上述代码来源于书中，并结合自己的习惯进行了相应修改，由于时间关系，并不能补充完整。从网上甄选出下述较好的代码。
链接：
https://zhuanlan.zhihu.com/p/84109536

bstree.h

#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_
typedef int Type;
typedef struct BSTreeNode{
    Type   key;                    // 关键字(键值)
 struct BSTreeNode *left;    // 左孩子
 struct BSTreeNode *right;    // 右孩子
 struct BSTreeNode *parent;    // 父结点
}Node, *BSTree;
// 前序遍历"二叉树"
void preorder_bstree(BSTree tree);
// 中序遍历"二叉树"
void inorder_bstree(BSTree tree);
// 后序遍历"二叉树"
void postorder_bstree(BSTree tree);
// (递归实现)查找"二叉树x"中键值为key的节点
Node* bstree_search(BSTree x, Type key);
// (非递归实现)查找"二叉树x"中键值为key的节点
Node* iterative_bstree_search(BSTree x, Type key);
// 查找最小结点：返回tree为根结点的二叉树的最小结点。
Node* bstree_minimum(BSTree tree);
// 查找最大结点：返回tree为根结点的二叉树的最大结点。
Node* bstree_maximum(BSTree tree);
// 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
Node* bstree_successor(Node *x);
// 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
Node* bstree_predecessor(Node *x);
// 将结点插入到二叉树中，并返回根节点
Node* insert_bstree(BSTree tree, Type key);
// 删除结点(key为节点的值)，并返回根节点
Node* delete_bstree(BSTree tree, Type key);
// 销毁二叉树
void destroy_bstree(BSTree tree);
// 打印二叉树
void print_bstree(BSTree tree, Type key, int direction);
#endif

bstree.c

#include <stdio.h>
#include <stdlib.h>
#include "bstree.h"
/*
 * 前序遍历"二叉树"
 */
void preorder_bstree(BSTree tree)
{
 if(tree != NULL)
 {
 printf("%d ", tree->key);
 preorder_bstree(tree->left);
 preorder_bstree(tree->right);
 }
}
/*
 * 中序遍历"二叉树"
 */
void inorder_bstree(BSTree tree)
{
 if(tree != NULL)
 {
 inorder_bstree(tree->left);
 printf("%d ", tree->key);
 inorder_bstree(tree->right);
 }
}
/*
 * 后序遍历"二叉树"
 */
void postorder_bstree(BSTree tree)
{
 if(tree != NULL)
 {
 postorder_bstree(tree->left);
 postorder_bstree(tree->right);
 printf("%d ", tree->key);
 }
}
/*
 * (递归实现)查找"二叉树x"中键值为key的节点
 */
Node* bstree_search(BSTree x, Type key)
{
 if (x==NULL || x->key==key)
 return x;
 if (key < x->key)
 return bstree_search(x->left, key);
 else
 return bstree_search(x->right, key);
}
/*
 * (非递归实现)查找"二叉树x"中键值为key的节点
 */
Node* iterative_bstree_search(BSTree x, Type key)
{
 while ((x!=NULL) && (x->key!=key))
 {
 if (key < x->key)
            x = x->left;
 else
            x = x->right;
 }
 return x;
}
/* 
 * 查找最小结点：返回tree为根结点的二叉树的最小结点。
 */
Node* bstree_minimum(BSTree tree)
{
 if (tree == NULL)
 return NULL;
 while(tree->left != NULL)
        tree = tree->left;
 return tree;
}
/* 
 * 查找最大结点：返回tree为根结点的二叉树的最大结点。
 */
Node* bstree_maximum(BSTree tree)
{
 if (tree == NULL)
 return NULL;
 while(tree->right != NULL)
        tree = tree->right;
 return tree;
}
/* 
 * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
 */
Node* bstree_successor(Node *x)
{
  // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
 if (x->right != NULL)
 return bstree_minimum(x->right);
  // 如果x没有右孩子。则x有以下两种可能：
  // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
  // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
    Node* y = x->parent;
 while ((y!=NULL) && (x==y->right))
 {
        x = y;
        y = y->parent;
 }
 return y;
}
/* 
 * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
 */
Node* bstree_predecessor(Node *x)
{
  // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
 if (x->left != NULL)
 return bstree_maximum(x->left);
  // 如果x没有左孩子。则x有以下两种可能：
  // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
  // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
    Node* y = x->parent;
 while ((y!=NULL) && (x==y->left))
 {
        x = y;
        y = y->parent;
 }
 return y;
}
/*
 * 创建并返回二叉树结点。
 *
 * 参数说明：
 *     key 是键值。
 *     parent 是父结点。
 *     left 是左孩子。
 *     right 是右孩子。
 */
static Node* create_bstree_node(Type key, Node *parent, Node *left, Node* right)
{
    Node* p;
 if ((p = (Node *)malloc(sizeof(Node))) == NULL)
 return NULL;
    p->key = key;
    p->left = left;
    p->right = right;
    p->parent = parent;
 return p;
}
/* 
 * 将结点插入到二叉树中
 *
 * 参数说明：
 *     tree 二叉树的根结点
 *     z 插入的结点
 * 返回值：
 *     根节点
 */
static Node* bstree_insert(BSTree tree, Node *z)
{
    Node *y = NULL;
    Node *x = tree;
  // 查找z的插入位置
 while (x != NULL)
 {
        y = x;
 if (z->key < x->key)
            x = x->left;
 else
            x = x->right;
 }
    z->parent = y;
 if (y==NULL)
        tree = z;
 else if (z->key < y->key)
        y->left = z;
 else
        y->right = z;
 return tree;
}
/* 
 * 新建结点(key)，并将其插入到二叉树中
 *
 * 参数说明：
 *     tree 二叉树的根结点
 *     key 插入结点的键值
 * 返回值：
 *     根节点
 */
Node* insert_bstree(BSTree tree, Type key)
{
    Node *z;    // 新建结点
  // 如果新建结点失败，则返回。
 if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)
 return tree;
 return bstree_insert(tree, z);
}
/* 
 * 删除结点(z)，并返回根节点
 *
 * 参数说明：
 *     tree 二叉树的根结点
 *     z 删除的结点
 * 返回值：
 *     根节点
 */
static Node* bstree_delete(BSTree tree, Node *z)
{
    Node *x=NULL;
    Node *y=NULL;
 if ((z->left == NULL) || (z->right == NULL) )
        y = z;
 else
        y = bstree_successor(z);
 if (y->left != NULL)
        x = y->left;
 else
        x = y->right;
 if (x != NULL)
        x->parent = y->parent;
 if (y->parent == NULL)
        tree = x;
 else if (y == y->parent->left)
        y->parent->left = x;
 else
        y->parent->right = x;
 if (y != z) 
        z->key = y->key;
 if (y!=NULL)
 free(y);
 return tree;
}
/* 
 * 删除结点(key为节点的键值)，并返回根节点
 *
 * 参数说明：
 *     tree 二叉树的根结点
 *     z 删除的结点
 * 返回值：
 *     根节点
 */
Node* delete_bstree(BSTree tree, Type key)
{
    Node *z, *node; 
 if ((z = bstree_search(tree, key)) != NULL)
        tree = bstree_delete(tree, z);
 return tree;
}
/*
 * 销毁二叉树
 */
void destroy_bstree(BSTree tree)
{
 if (tree==NULL)
 return ;
 if (tree->left != NULL)
 destroy_bstree(tree->left);
 if (tree->right != NULL)
 destroy_bstree(tree->right);
 free(tree);
}
/*
 * 打印"二叉树"
 *
 * tree       -- 二叉树的节点
 * key        -- 节点的键值 
 * direction  --  0，表示该节点是根节点;
 *               -1，表示该节点是它的父结点的左孩子;
 *                1，表示该节点是它的父结点的右孩子。
 */
void print_bstree(BSTree tree, Type key, int direction)
{
 if(tree != NULL)
 {
 if(direction==0)  // tree是根节点
 printf("%2d is root\n", tree->key);
 else  // tree是分支节点
 printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");
 print_bstree(tree->left, tree->key, -1);
 print_bstree(tree->right,tree->key,  1);
 }
}

main.c

#include <stdio.h>
#include "bstree.h"
static int arr[]= {1,5,4,3,2,6};
#define TBL_SIZE(a) ( (sizeof(a)) / (sizeof(a[0])) )
void main()
{
 int i, ilen;
    BSTree root=NULL;
 printf("== 依次添加: ");
    ilen = TBL_SIZE(arr);
 for(i=0; i<ilen; i++)
 {
 printf("%d ", arr[i]);
        root = insert_bstree(root, arr[i]);
 }
 printf("\n== 前序遍历: ");
 preorder_bstree(root);
 printf("\n== 中序遍历: ");
 inorder_bstree(root);
 printf("\n== 后序遍历: ");
 postorder_bstree(root);
 printf("\n");
 printf("== 最小值: %d\n", bstree_minimum(root)->key);
 printf("== 最大值: %d\n", bstree_maximum(root)->key);
 printf("== 树的详细信息: \n");
 print_bstree(root, root->key, 0);
 printf("\n== 删除根节点: %d", arr[3]);
    root = delete_bstree(root, arr[3]);
 printf("\n== 中序遍历: ");
 inorder_bstree(root);
 printf("\n");
  // 销毁二叉树
 destroy_bstree(root);
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法与数据结构

数据结构

二叉排序树

c语言

【数据结构】树（五）—— 二叉排序树（C语言版） 的相关文章

随机推荐

  • Linux系统基础操作命令

    目录 一 基本使用 1 编辑Linux命令行的辅助操作 2 常用的基础命令 1 切换用户 su 2 pwd 查看当前工作目录 3 cd 切换工作目录 4 cp 复制 5 mkdir 创建目录 6 touch 创建文件 7 创建链接文件ln

  • 《网络安全工程师笔记》 第十一章：WEB服务器和FTP服务器

    注 本笔记来自温晓飞老师的网络安全课程 第十一章 WEB服务器和FTP服务器 第一章 虚拟化架构与系统部署 第二章 IP地址详解 第三章 进制转换 第四章 DOS基本命令与批处理 第五章 用户与组管理 第六章 服务器远程管理 第七章 NTF

  • java基础6

    packagecom edu 01 public class Student 私有化成员变量 private String name private int age set get方法 public voidsetName String n

  • [基础数据结构] 判断是否为完全二叉搜索树

    对二叉搜索树的定义是 一棵深度为k的有n个结点的二叉树 对树中的结点按从上至下 从左到右的顺序进行编号 如果编号为i 1 i n 1 i n 1 i n 的结点与满二叉树中编号为i的结点在二叉树中的位置相同 则这棵二叉树称为

  • UI设计都有哪些设计原则，分享三个给你

    是什么使一个好UI设计容易阅读 是什么让用户轻松浏览 设计师如何创造一个闪亮的UI 任何软件产品的关键部分都是用户界面 好的UI设计 用户甚至会忽略它 如果做得不好 就会成为用户使用产品的绊脚石 为了更有效地设计能够满足用户使用的设计UI

  • 【原理篇】再次带你进入多线程的世界

    1 Java内存模型基础知识 1 1并发编程模型的两个关键问题 线程间如何通信 即 线程之间以何种机制来交换信息 线程间如何同步 即 线程以何种机制来控制不同线程间操作发 的相对顺序 有两种并发模型可以解决这两个问题 消息传递并发模型 共享

  • scala的基础语法之变量

    1 类介绍 我们在new scala类的时候 这里分为Class和Object两大类 idea2019 1版本 其他新版本应该是四种 case Class和case Object 不过没关系 这里想要使用case的直接在前面写case即可

  • 任正非谈成功秘诀：28年只对准一个城墙口冲锋

    文 记者 赵东辉 李斌 刘诗平 蔡国兆 彭勇 何雨欣 任正非和华为公司 堪称当代商业史上的传奇 1987年 年满43岁的任正非和5个同伴集资2 1万元成立华为公司 利用两台万用表加一台示波器 在深圳的一个 烂棚棚 里起家创业 28年后 华为

  • 穿越火线排位赛显示该服务器,CF新段位S7枪王排位调整 排位分数和地图

    CF新段位S7枪王排位调整 排位分数和地图 本次体验服客户端正式更新同时S7枪王排位赛页开启了 本期枪王排位针对地图 段位分数和奖励上进行调整 不同段位分数和地图加成都不同 枪王排位第五赛季开始及优化丢掉大脑再丢烦恼 冲啥大冲啥小 冲啥都有

  • 【无标题】PAT作业1001 害死人不偿命的（3n+1)猜想

    题目要求简要概述 输入一个小于1000的正整数 如果该正整数为奇数 进行2 n的运算 如果为偶数 进行 3n 1 2的运算 反复进行计算 直至n 1后 输出运算的次数 解题方法 1 定义两个整形变量 分别用于输入n 记录运算次数 int n

  • 将压缩包里的图片显示到页面上示例

    在做项目的时候有个这样的需求 需要把压缩包里的图片预览显示出来 梳理一下就以下三步 下载压缩包 解压出文件 组成可用的图片URL 显示到图片标签上 实现这个功能过程还是走了些弯路的 也遇到一些坑 这里就不多废话了 直接上代码 希望能帮助各位

  • SVPWM所需要掌握的一些定理

    1 正弦定理 2 伏秒平衡 不懂 伏秒平衡 又称伏秒平衡 是指开关电源稳定工作状态下 加在电感两端的电压乘以导通时间等于关断时刻电感两端电压乘以关断时间 或指在稳态工作的开关电源中电感两端的正伏秒值等于负伏秒值 在SVPWM中 磁链等于电压

  • ORB-SLAM2第二节---双目地图初始化

    比起单目初始化 而双目实现地图的初始化非常简单 只需要一帧 左右目图像 即可完成初始化 行特征点统计 考虑用图像金字塔尺度作为偏移量 在当前点上下正负偏移量 r 内的纵坐标值都认为是匹配点可能存在的行数 之所以这样做 是因为极线矫正后仍然存

  • 创建steam账户反复人机验证_您必须先通过人机验证才能创建steam帐户怎么办

    展开全部 在注册steam帐户遇到提示必须通过人机验证才能创建62616964757a686964616fe4b893e5b19e31333433643062提示时 勾选注册页面中的进行人机验证 在人机身份验证界面中点击需要的图片并按照步骤

  • socket接收报错

    首先是没得到正确错误号 是因为windows平台WSAGetLastError得过之后就没了 所以需要int变量保存一下 发现错误号后知道是最后一个参数没有初始化复制 bzero buf sizeof buf bzero cli adr s

  • PostgreSQL 多表关联删除

    用PostgreSQL数据库删除某个表数据 student 需要关联多个表 如classroom 作为条件 以下语句走不通 delete s from student s classroom c where s cid c id and s

  • JPA基本数据类型映射

    Employ author Administrator Entity Table name T EMPLOY SequenceGenerator name SEQ sequenceName SEQ SYS FUNC MENU initial

  • 利用MATLAB编写一段表格数据处理并作图

    使用MATLAB处理表格数据并作图可以使用以下步骤 读入表格数据 使用readtable或者xlsread函数读入Excel或者其他格式的表格数据 数据预处理 使用MATLAB的数组运算和统计函数对读入的数据进行预处理 包括清洗缺失值 去除

  • hadoopRPC的使用

    1模拟namenode的查询元数据 public interface ClientNamenodeProtocol public static final long versionID 1L 会读取这个版本号 但可以和客户端的不一样 没有校

  • 【数据结构】树（五）—— 二叉排序树（C语言版）

    数据结构 二叉排序树 C语言版 前言 一 二叉排序树的定义 二 二叉排序树的性质 三 二叉排序树的操作 1 二叉排序树常用存储结构 2 二叉排序树的查找 递归实现 查找 二叉树T 中键值为 key 的节点 非递归实现 查找 二叉树T 中键值

热门标签