数据结构之查找树题解

问题01

给定一棵二叉排序树，按先序遍历得到的序列为 \((50, 38, 30, 45, 40, 48, 70, 60, 75, 80)\)。试画出该二叉排序树，并求出等概率下查找成功和查找失败的平均查找长度。

解答

image-20241011194459832

查找成功的平均查找长度为 ASL=(1*1+2*2+3*4+4*3)/10=2.9

图中的方块结点为虚构的查找失败结点，其查找路径为从根结点到其父结点(圆形结点)的结点序列，故对应的查找失败平均长度为:

ASL=(3*5 + 4*6)/11=39/11

问题02

按照序列 \((40, 72, 38, 35, 67, 51, 90, 8, 55, 21)\) 建立一棵二叉排序树，并求出在等概率的情况下，查找成功的平均查找长度。

解答

image-20241011194756217

平均査找长度为\(ASL=(1+2*2+3*3+4*2+5*2)/10=3.2。\)

问题03

依次将节点 \((34, 23, 15, 98, 115, 28, 107)\) 插入初始状态为空的平衡二叉排序树，使得在每次插入后保持该树仍然是平衡二叉树。请依次画出每次插入后所形成的平衡二叉排序树。

第一步:插入结点 34,23,15 后，需要根结点 34 的子树做 LL 调整。

image-20241011194856226

第二步:插入结点 98,115后，需要根结点34的子树做RR调整，

image-20241011194937245

第三步:插入结点28后，需要根结点23的子树做RL调整

image-20241011195027321

第四步:插入结点107后，需要根结点98的子树做RL调整。

image-20241011195129909

问题04

给定一个关键字集合 \(\{25, 18, 34, 9, 14, 27, 42, 51, 38\}\)，假定查找各关键字的概率相同，请画出其最佳二叉排序树。

答案

最佳二叉排序树的构造过程如下：

  1. 对关键字进行排序： 将关键字按值从小到大排序，得到 \(\{9, 14, 18, 25, 27, 34, 38, 42, 51\}\)。

  2. 构造最佳二叉排序树： 选择中间的元素作为根节点，仿照折半查找的判定树的构造方法构造二叉排序树。

image-20241011195315601

问题05

画出一个二叉树，使得它既满足大根堆的要求又满足二叉排序树的要求。

答案

以下是一个同时满足大根堆和二叉排序树的二叉树示例：

1
2
3
  5
 /
3

解释

  1. 大根堆的要求：
    • 根节点的关键字值（5）大于等于左子节点的关键字值（3），满足大根堆的性质。
  2. 二叉排序树的要求：
    • 根节点的关键字值（5）大于左子节点的关键字值（3），同时没有右子节点，因此也符合二叉排序树的性质。

特点分析

  • 这种树的结构可以看作是一棵左斜单支树（左子树不为空，右子树为空）。
  • 此外，单个节点的二叉树（如只包含一个节点的情况）也是满足题意的，但在此我们选择了包含两个节点的树结构，以体现出二叉排序树与大根堆之间的关系。
  • 实际上，除了这种简单结构，若想构造更复杂的树满足这两种性质，可以使用完全二叉树的概念来添加更多节点，但在特定条件下，保持堆和排序树的性质，节点的值必须符合相应的大小关系。

问题06

编写一个算法，判断给定的二叉树是否是二叉排序树。

答案

以下是判断给定的二叉树是否是二叉排序树的算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct BiTNode {
    KeyType data;               // 节点存储的数据
    struct BiTNode *lchild;    // 左子树指针
    struct BiTNode *rchild;    // 右子树指针
} BiTNode, *BiTree;

// 全局变量，保存当前结点中序前驱的值
KeyType predt = -32767;

int JudgeBST(BiTree bt) {
    int b1, b2;

    // 空树是二叉排序树
    if (bt == NULL) {
        return 1; // 返回1表示是二叉排序树
    }

    // 判断左子树是否是二叉排序树
    b1 = JudgeBST(bt->lchild);
    if (b1 == 0 || predt >= bt->data) {
        // 若左子树返回值为0或前驱大于等于当前结点，则不是二叉排序树
        return 0;
    }

    // 保存当前结点的关键字
    predt = bt->data;

    // 判断右子树是否是二叉排序树
    b2 = JudgeBST(bt->rchild);
    
    return b2; // 返回右子树的结果
}

解释

  1. 中序遍历性质：
    • 对于二叉排序树，其所有节点的中序遍历序列应该是一个递增的有序序列。因此，通过中序遍历，可以有效地判断一棵二叉树是否是二叉排序树。
  2. 算法思路：
    • 使用递归进行中序遍历，比较当前节点的值与前驱节点的值。
    • 初始化全局变量 predt 为一个较小的值（如 -32767），用于保存前驱节点的值。
    • 对于每个节点，首先递归判断其左子树。
    • 在判断完左子树后，检查当前节点的值是否大于前驱值。
    • 更新前驱值为当前节点的值后，递归判断右子树。
  3. 返回值：
    • 若任一节点不符合排序规则，则返回 0，表示该树不是二叉排序树；若全部符合，则返回 1，表示该树是二叉排序树。

问题07

设计一个算法，求出指定节点在给定二叉排序树中的层次。

答案

以下是求指定节点在二叉排序树中层次的算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct BiTNode {
    KeyType data;               // 节点存储的数据
    struct BiTNode *lchild;    // 左子树指针
    struct BiTNode *rchild;    // 右子树指针
} BiTNode, *BiTree;

int level(BiTree bt, BiTNode *p) {
    // 统计查找次数
    int n = 0;  // 初始化层次计数
    BiTree t = bt;  // 从根节点开始查找

    if (bt == NULL) {
        return -1;  // 树为空，返回 -1 表示找不到
    }

    while (t != NULL) {
        n++;  // 每次查找增加层次数
        if (p->data == t->data) {
            return n;  // 找到节点，返回层次
        }
        if (p->data < t->data) {
            t = t->lchild;  // 在左子树中查找
        } else {
            t = t->rchild;  // 在右子树中查找
        }
    }
    
    return -1;  // 未找到，返回 -1
}

问题08

编写一个算法，利用二叉树遍历的思想判断一个二叉树是否是平衡二叉树。

答案

以下是判断二叉树是否为平衡二叉树的算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef int KeyType;

typedef struct BiTNode {
    KeyType data;               // 节点存储的数据
    struct BiTNode *lchild;    // 左子树指针
    struct BiTNode *rchild;    // 右子树指针
} BiTNode, *BiTree;

void JudgeAVL(BiTree bt, int *balance, int *h) {
    int bl = 0, br = 0;  // 左右子树的平衡标记
    int hl = 0, hr = 0;  // 左右子树的高度

    // 空树，高度为0
    if (bt == NULL) {
        *h = 0;
        *balance = 1;  // 平衡
        return;
    }
    
    // 递归判断左子树
    JudgeAVL(bt->lchild, &bl, &hl);
    // 递归判断右子树
    JudgeAVL(bt->rchild, &br, &hr);

    // 当前节点的高度
    *h = (hl > hr ? hl : hr) + 1;

    // 判断平衡条件
    if (abs(hl - hr) < 2) {
        *balance = bl && br;  // 左右子树都平衡
    } else {
        *balance = 0;  // 不平衡
    }
}

问题09

设计一个算法，求出给定二叉排序树中最小和最大的关键字。

答案

以下是求取二叉排序树中最小和最大关键字的算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct BSTNode {
    KeyType data;                 // 关键字
    struct BSTNode *lchild;      // 左子树指针
    struct BSTNode *rchild;      // 右子树指针
} BSTNode, *BiTree;

// 求取二叉排序树中的最小关键字
KeyType MinKey(BiTree bt) {
    while (bt->lchild != NULL) {
        bt = bt->lchild;  // 逐步向左子树移动
    }
    return bt->data;  // 返回最小关键字
}

// 求取二叉排序树中的最大关键字
KeyType MaxKey(BiTree bt) {
    while (bt->rchild != NULL) {
        bt = bt->rchild;  // 逐步向右子树移动
    }
    return bt->data;  // 返回最大关键字
}

问题10

设计一个算法，从大到小输出二叉排序树中所有值不小于 $ k $ 的关键字。

答案

以下是从大到小输出二叉排序树中所有值不小于 $ k $ 的关键字的算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct BSTNode {
    KeyType data;                 // 关键字
    struct BSTNode *lchild;      // 左子树指针
    struct BSTNode *rchild;      // 右子树指针
} BSTNode, *BiTree;

// 从大到小输出所有值不小于 k 的关键字
void OutPut(BSTNode *bt, KeyType k) {
    if (bt == NULL) {
        return;  // 如果当前节点为空，直接返回
    }
    
    // 递归输出右子树
    if (bt->rchild != NULL) {
        OutPut(bt->rchild, k);
    }

    // 只输出大于等于 k 的节点值
    if (bt->data >= k) {
        printf("%d ", bt->data);
    }

    // 递归输出左子树
    if (bt->lchild != NULL) {
        OutPut(bt->lchild, k);
    }
}
  1. 算法思想：
    • 利用二叉排序树的性质，节点的值分布情况使得右子树的所有节点值均大于根节点的值，而左子树的所有节点值均小于根节点的值。
    • 因此，为了从大到小输出值不小于 $ k $ 的关键字，首先遍历右子树，再访问根节点，最后遍历左子树。

问题11

编写一个递归算法，在一棵有 $ n $ 个节点的、随机建立起来的二叉排序树上查找第 $ k $ ( $ 1 k < n $ ) 小的元素，并返回指向该节点的指针。要求算法的平均时间复杂度为 $ O(n) $。二叉排序树的每个节点中除 data, lchild, rchild 等数据成员外，增加一个 count 成员，保存以该节点为根的子树上的节点个数。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct BSTNode {
    KeyType data;                // 关键字
    struct BSTNode *lchild;     // 左子树指针
    struct BSTNode *rchild;     // 右子树指针
    int count;                  // 以该节点为根的子树节点个数
} BSTNode, *BiTree;

// 在以 t 为根的子树上寻找第 k 小的元素，返回其所在节点的指针
BSTNode *SearchSmall(BSTNode *t, int k) {
    // 检查输入的 k 是否合理
    if (t == NULL || k < 1 || k > t->count) {
        return NULL;  // 返回空指针
    }
    
    // 处理当前节点的情况
    if (t->lchild == NULL) {  // 左子树为空
        if (k == 1) {
            return t;  // 当前节点就是第 k 小的元素
        } else {
            return SearchSmall(t->rchild, k - 1);  // 继续在右子树中查找
        }
    } else {
        // 处理左子树不为空的情况
        if (t->lchild->count == k - 1) {
            return t;  // 当前节点就是第 k 小的元素
        } else if (t->lchild->count > k - 1) {
            return SearchSmall(t->lchild, k);  // 在左子树中查找
        } else {
            return SearchSmall(t->rchild, k - (t->lchild->count + 1));  // 在右子树中查找
        }
    }
}