二叉搜索树（1）图形分析和C语言实现

更多: 数据结构和算法系列目录

（01）. 二叉树的图形分析与C语言实现（一）

（02）. 二进制搜索树的C ++实现（2）

（03）. 二进制搜索树的Java实现（3）

1. 树的定义

树是一种数据结构，它是由n（n> = 1）个有限节点组成的一组层次关系.

它被称为“树”，因为它看起来像一棵倒立的树，也就是说，它的根朝上，而叶子朝下. 具有以下特点:

（01）每个节点有零个或多个子节点；

（02）没有父节点的节点称为根节点；

（03）每个非根节点只有一个父节点；

（04）除了根节点之外，每个子节点都可以分为多个不相交的子树.

2. 树木的基本术语

如果节点具有子树，则该节点称为子树根的“父级”，而子树的根就是该节点的“子级”. 具有相同父代的节点是彼此的“兄弟”. 节点的所有子树中的任何节点都是该节点的后代. 从根节点到节点的路径上的所有节点都是该节点的祖先.

节点的度数: 节点拥有的子树的数量.

离开: 零度的节点.

分支节点: 度数不为零的节点.

树的程度: 树中节点的最大程度.

级别: 根节点的级别为1，其余节点的级别等于该节点的父节点的级别加1.

树的高度: 树中节点的最大级别.

无序树: 如果树中节点的子树之间的顺序不重要，则可以交换位置.

有序树: 如果树中节点的子树之间的顺序很重要，则不能交换位置.

森林: 由0棵或更多棵不连贯的树木组成. 在森林中添加根，森林变成一棵树. 删除根，树变成森林.

1. 二叉树的定义

二叉树是每个节点最多具有两个子树的树结构. 它具有五种基本形式: 二叉树可以是一个空集；二叉树可以是一个空集. 根可以有一个空的左或右子树；或左右子树都为空.

2. 二叉树的性质

二叉树具有以下属性: TODO（上标和下标）

属性1: 二叉树的第i层上的节点数最多为2 {i-1}（i≥1）.

属性2: 深度为k的二叉树最多具有2 {k} -1个节点（k≥1）.

属性3: 具有n个节点的二叉树的高度至少为log2（n + 1）.

属性4: 在任何二叉树中，如果终端节点数为n0，度数为2的节点数为n2，则n0 = n2 + 1.

2.1属性1: 二叉树的第i层上的节点数最多为2 {i-1}（i≥1）

证明: 以下使用“数学归纳法”进行证明.

（01）当i = 1时，第i层中的节点数为2 {i-1} = 2 {0} = 1. 因为级别1上只有一个根节点，所以命题是正确的.

（02）假设当i> 1时，第i层中的节点数为2 {i-1}. 这是从（01）推断出来的！

基于此假设，可以推断出“第（i + 1）层中的节点数为2 {i}”.

由于二叉树的每个节点最多具有两个子节点，因此“第（i + 1）层上的节点数”最多是“第i层上的节点数的两倍”. 也就是说，第（i + 1）层上的最大节点数= 2×2 {i-1} = 2 {i}.

因此假设成立二叉排序树 c，原始命题得到证明！

2.2属性2: 深度为k的二叉树最多具有2 {k} -1个节点（k≥1）

证明: 在具有相同深度的二叉树中，当每层包含最大数量的节点时，树中的节点数量最大. 根据“属性1”，深度为k的二叉树的节点数最多为:

20 + 21 +…+ 2k-1 = 2k-1

因此，最初的命题得到了证明！

2.3属性3: 具有n个节点的二叉树的高度至少为log2（n + 1）

证明: 根据“属性2”，高度为h的二叉树最多具有2 {h} –1个节点. 相反，包含n个节点的二叉树的高度至少为log2（n + 1）.

2.4属性4: 在任何二叉树中，如果终端节点的数量为n0，度数为2的节点的数量为n2，则n0 = n2 + 1

证明: 由于二叉树中所有节点的度不大于2，所以节点总数（表示为n）=“ 0度节点数（n0）” +“ 1度节点数（n1） “ +” 2度节点（n2）“. 这样就得到了等式1.

（等式1）n = n0 + n1 + n2

另一方面，0度节点没有子节点，1度节点有一个孩子，而2度节点有两个孩子，因此二叉树中的子节点总数为: n1 + 2n2. 此外，只有根不是任何节点的子代. 因此，二叉树中的节点总数可以表示为公式2.

（等式2）n = n1 + 2n2 + 1

根据（等式1）和（等式2）计算: n0 ＝ n2 + 1. 原来的命题被证明了！

3. 完整的二叉树，完整的二叉树和二叉搜索树

3.1完整的二叉树

定义: 高度为h且由2 {h} –1个节点组成的二叉树称为完整二叉树.

3.2完整的二叉树

定义: 在二叉树中，只有最下面两层的节点的度数可以小于2，最下面一层的叶节点集中在左侧的几个位置. 这样的二叉树称为完整二叉树.

特征: 叶节点只能出现在最下层和下一个较低层中，最低的叶节点集中在树的左侧. 显然，完整的二叉树必须是完整的二叉树，完整的二叉树可能不是完整的二叉树.

3.3二进制搜索树

定义: 二进制搜索树，也称为二进制搜索树. 令x为二叉查找树中的一个节点二叉排序树 c，该x节点包含密钥key，并且节点x的密钥值记录为key [x]. 如果y是x的左子树中的节点，则key [y] <= key [x];如果y是x的右子树中的一个节点，则key [y]> = key [x].

在二进制搜索树中:

（01）如果任何节点的左子树都不为空，则左子树上所有节点的值都小于其根节点的值；

（02）任何节点的右子树都不为空，则右子树上所有节点的值大于其根节点的值；

（03）任何节点的左和右子树也是二叉搜索树.

（04）没有重复的节点.

在实际应用中，经常使用二进制搜索树. 接下来，以C语言实现二进制搜索树.

1. 节点定义

1.1节点定义

typedef int Type;
typedef struct BSTreeNode{
    Type   key;                    // 关键字(键值)
    struct BSTreeNode *left;    // 左孩子
    struct BSTreeNode *right;    // 右孩子
    struct BSTreeNode *parent;    // 父结点
}Node, *BSTree;

二进制搜索树的节点中包含的基本信息:

（01）键-这是用于对二叉搜索树的节点进行排序的键.

（02）left-指向当前节点的左子节点.

（03）right-指向当前节点的右子节点.

（04）parent-指向当前节点的父节点.

1.2创建节点

创建节点的代码

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

2个遍历

在这里，我们解释三种方法: 前遍历，中阶遍历和后遍历.

2.1遍历

如果二叉树不为空，请执行以下操作:

（01）访问根节点；

（02）首先遍历左侧子树；

（03）首先遍历右侧子树.

预订遍历代码

void preorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        printf("%d ", tree->key);
        preorder_bstree(tree->left);
        preorder_bstree(tree->right);
    }
}

2.2有序遍历

如果二叉树不为空，请执行以下操作:

（01）左子树的有序遍历；

（02）访问根节点；

（03）以中间顺序遍历右侧子树.

序列遍历代码

void inorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        inorder_bstree(tree->left);
        printf("%d ", tree->key);
        inorder_bstree(tree->right);
    }
}

2.3后遍历

如果二叉树不为空，请执行以下操作:

（01）依次遍历左侧子树；

（02）依次遍历右侧子树；

（03）访问根节点.

后遍历代码

void postorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        postorder_bstree(tree->left);
        postorder_bstree(tree->right);
        printf("%d ", tree->key);
    }
}

通过示例介绍以下遍历方法.

对于上面的二叉树，

（01）遍历结果: 3 1 2 5 4 6

（02）有序遍历结果: 1 2 3 4 5 6

（03）后遍历结果: 2 1 4 6 5 3

3. 查找

递归版本的代码

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

该代码的非递归版本

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

4. 最大值和最小值

找到最大值的代码

Node* bstree_maximum(BSTree tree)
{
    if (tree == NULL)
        return NULL;
    while(tree->right != NULL)
        tree = tree->right;
    return tree;
}

找到最小值的代码

Node* bstree_minimum(BSTree tree)
{
    if (tree == NULL)
        return NULL;
    while(tree->left != NULL)
        tree = tree->left;
    return tree;
}

5. 前辈和后继者

节点的前身: 它是该节点左子树中最大的节点.

节点的后代: 是节点右子树中的最小节点.

查找前任节点的代码

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

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-240760-1.html