[数据结构与算法] 【数据结构】树（五）—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构】树（五）—— 二叉排序树（C语言版） -> 正文阅读

[数据结构与算法]【数据结构】树（五）—— 二叉排序树（C语言版）

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

前言

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

一、二叉排序树的定义

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

条件：

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

二、二叉排序树的性质

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

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

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

三、二叉排序树的操作

查找
插入
创建
删除

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

二叉排序树常用存储结构

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

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

二叉排序树的查找

(递归实现)查找"二叉树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;
}

二叉排序树的插入


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);
}

二叉排序树的创建

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;
}

二叉排序树的删除

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

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

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

当二叉排序树形态比较对称(特别地，如二叉排序树的左、右子树的高度差的绝对值不超过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);
}