数据结构之二叉树的遍历和线索二叉树程序题

01. 若某非空二叉树的先序序列和后序序列正好相反，则该二叉树的形态是什么？

01. 【解答】

二叉树的先序遍历顺序是 NLR（根-左-右），而后序遍历顺序是 LRN（左-右-根）。要使先序序列与后序序列的反序相同，即满足 \(NLR = NRL\)（后序序列的反序），必须满足左子树或右子树为空。

也就是说，所有的非叶结点只能有一个孩子（要么只有左孩子，要么只有右孩子），这就意味着该二叉树每一层只有一个结点。因此，这棵树的形态是一条“长链”，其高度等于结点的个数。

示例：

以 3 个结点 \(a, b, c\) 为例，假设结点的排列形态如下：

1
2
3
4
5
a
 \
  b
   \
    c

这是一棵形态为“右斜”链状的二叉树，其每个结点只有一个右孩子（或可以是左孩子），每层只有一个结点。

02. 若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？

02.【解答】

二叉树的先序遍历顺序是 NLR（根-左-右），而后序遍历顺序是 LRN（左-右-根）。要使先序序列与后序序列完全相同，即 \(NLR = LRN\)，这意味着左子树 \(L\) 和右子树 \(R\) 都必须为空。

因此，满足这一条件的二叉树只有一个根结点，也就是说，这棵二叉树是一个 只有根结点的树，没有左子树或右子树。

03：编写后序遍历二叉树的非递归算法。

03.【解答】

算法思想： 后序遍历的顺序是：先左子树 -> 再右子树 -> 最后根结点。对于非递归遍历，需要借助栈来记录结点，并且还要额外设置一个辅助指针来追踪最近访问过的结点，以确定是从左子树返回还是从右子树返回。

步骤分析： 1. 从根节点开始，沿着左子树依次将结点压入栈，直到左子树为空。 2. 如果栈顶结点的右子树存在且未被访问过，则转向右子树继续执行步骤1；否则，弹出栈顶结点并访问它，记录为已访问。 3. 重复上述过程，直到栈为空，整个树都被遍历完。

关键点： - 辅助指针 r：用于标记上一次访问的结点，用来判断是从左子树返回还是从右子树返回。 - 栈：用来存储当前访问路径上的结点。 - 需要注意的是，出栈访问完一个结点后，应将 p 置为 NULL，以避免重复处理。

代码实现：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef struct Stack {
    BiTree *data;
    int top;
} Stack;

void InitStack(Stack *s) {
    s->data = (BiTree *)malloc(100 * sizeof(BiTree));  // 假设栈的大小为100
    s->top = -1;
}

int IsEmpty(Stack *s) {
    return s->top == -1;
}

void Push(Stack *s, BiTree node) {
    s->data[++s->top] = node;
}

void Pop(Stack *s, BiTree *node) {
    *node = s->data[s->top--];
}

void GetTop(Stack *s, BiTree *node) {
    *node = s->data[s->top];
}

void visit(char data) {
    printf("%c ", data);  // 输出访问的结点数据
}

void PostOrder(BiTree T) {
    Stack s;
    InitStack(&s);
    BiTree p = T;
    BiTree r = NULL;  // 记录最近访问的结点

    while (p != NULL || !IsEmpty(&s)) {
        // 走到最左边的结点
        if (p != NULL) {
            Push(&s, p);
            p = p->lchild;
        } else {
            // 读取栈顶结点（但不出栈）
            GetTop(&s, &p);
            if (p->rchild != NULL && p->rchild != r) {
                // 如果右子树存在且未被访问过，则转向右子树
                p = p->rchild;
            } else {
                // 否则，弹出栈顶结点并访问
                Pop(&s, &p);
                visit(p->data);
                r = p;  // 记录最近访问的结点
                p = NULL;  // 结点访问完后重置 p
            }
        }
    }
}

算法解释： - 初始化栈和指针，p 指向树的根结点，r 用来记录最近访问的结点。 - 首先沿着左子树一路向下，将所有结点压入栈，直到遇到空结点。 - 当左子树走到底后，检查栈顶元素。如果其右子树存在且未访问过，则转向右子树；否则，访问该结点并从栈中弹出。 - 通过辅助指针 r，避免重复访问结点。 - 最后，输出后序遍历的顺序。

注意： - 每当一个结点访问完后，相当于其子树遍历完，必须将 p 置为 NULL，以防止重复处理。 - 使用 visit 函数来输出结点的值，模拟结点的访问过程。

后序遍历示例输出： 假设给定的二叉树结构如下： 

1
2
3
4
5
    A
   / \
  B   C
 / \
D   E
其后序遍历顺序为：D E B C A

04：试给出二叉树的自下而上、从右到左的层次遍历算法。

04.【解答】

算法思想： 一般的二叉树层次遍历是自上而下、从左到右的，然而在这个问题中，我们需要实现自下而上、从右到左的遍历顺序。为了实现这一目标，可以利用原有的层次遍历算法，通过将每个结点的指针入栈，最后再从栈中依次访问这些结点，即可得到所需的遍历顺序。

具体步骤： 1. 将根结点入队列：首先，检查二叉树是否为空。如果不为空，将根结点入队列。 2. 出队列并遍历元素：从队列中出队一个元素，并访问（遍历）该元素。 3. 将孩子结点入队列： - 依次将出队元素的左孩子和右孩子入队列。注意，左孩子先入队，右孩子后入队，这样在后续的处理时才能实现从右到左的访问顺序。 4. 重复以上过程：如果队列不为空，继续从队列中出队并处理结点，直到队列为空。

最后一步：将所有入栈的结点从栈顶开始依次访问，最终得到自下而上、从右到左的遍历顺序。

代码实现：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef struct Stack {
    BiTree *data;
    int top;
} Stack;

typedef struct Queue {
    BiTree *data;
    int front, rear;
} Queue;

void InitStack(Stack *s) {
    s->data = (BiTree *)malloc(100 * sizeof(BiTree));  // 假设栈的大小为100
    s->top = -1;
}

int IsEmptyStack(Stack *s) {
    return s->top == -1;
}

void Push(Stack *s, BiTree node) {
    s->data[++s->top] = node;
}

void Pop(Stack *s, BiTree *node) {
    *node = s->data[s->top--];
}

void visit(char data) {
    printf("%c ", data);  // 输出访问的结点数据
}

void InitQueue(Queue *q) {
    q->data = (BiTree *)malloc(100 * sizeof(BiTree));  // 假设队列的大小为100
    q->front = 0;
    q->rear = 0;
}

int IsEmptyQueue(Queue *q) {
    return q->front == q->rear;
}

void EnQueue(Queue *q, BiTree node) {
    q->data[q->rear++] = node;  // 入队
}

void DeQueue(Queue *q, BiTree *node) {
    *node = q->data[q->front++];  // 出队
}

void InvertLevel(BiTree bt) {
    Stack s;
    Queue Q;
    
    if (bt != NULL) {
        InitStack(&s);
        InitQueue(&Q);
        EnQueue(&Q, bt);  // 将根结点入队
        
        // 自上而下层次遍历
        while (!IsEmptyQueue(&Q)) {
            BiTree p;
            DeQueue(&Q, &p);  // 出队
            Push(&s, p);  // 入栈
            
            // 依次将左右孩子入队，左孩子先入，右孩子后入
            if (p->lchild) {
                EnQueue(&Q, p->lchild);  // 若左孩子不空，则入队
            }
            if (p->rchild) {
                EnQueue(&Q, p->rchild);  // 若右孩子不空，则入队
            }
        }
        
        // 自下而上、从右到左的层次遍历
        while (!IsEmptyStack(&s)) {
            BiTree p;
            Pop(&s, &p);  // 从栈中弹出结点
            visit(p->data);  // 访问结点
        }
    }
}

解释：

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含数据和指向左右孩子的指针。
    • Stack 和 Queue 结构体用于实现栈和队列功能，分别用于存储树的结点指针。
  2. 初始化栈和队列：
    • InitStack 和 InitQueue 函数用于初始化栈和队列，分配内存空间。
  3. 层次遍历：
    • 使用队列进行自上而下的层次遍历，将访问到的结点压入栈中。
    • 注意左右孩子入队的顺序：先左后右，以确保后续弹栈时能实现从右到左的访问顺序。
  4. 栈的逆序访问：
    • 一旦完成了队列的遍历，栈中的结点按自下而上的顺序排列，依次弹出并访问。

结果：

通过这个算法，可以实现二叉树的自下而上、从右到左的层次遍历。例如，给定如下的二叉树：

1
2
3
4
5
    A
   / \
  B   C
 / \
D   E

其自下而上、从右到左的层次遍历结果为：D E B C A。

05：假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。

05.【解答】

算法思想： 采用层次遍历的算法，通过记录当前结点所在的层数来计算二叉树的高度。具体思路是设置变量 level 用于记录当前层的层数，设置变量 last 指向当前层的最右结点。每次在遍历出队时，与 last 指针进行比较，如果两者相等，则说明当前层已遍历完成，层数 level 加 1，并更新 last 为下一层的最右结点，直到遍历完成。最终 level 的值即为二叉树的高度。

具体步骤： 1. 初始化：检查树是否为空。如果为空，则高度为 0。 2. 设置变量： - front 和 rear 用于管理队列，分别表示队列的前后指针。 - last 指向当前层的最右结点，初始为 0。 - level 记录当前层数，初始为 0。 3. 将根结点入队：将根结点加入队列。 4. 遍历队列：使用循环遍历队列： - 出队一个结点，访问它。 - 如果该结点的左孩子存在，将左孩子入队。 - 如果该结点的右孩子存在，将右孩子入队。 - 每当出队的结点的索引等于 last 时，说明当前层遍历完毕，层数 level 加 1，并更新 last 为当前队列的尾指针。 5. 返回高度：当队列遍历完成后，返回 level 的值作为二叉树的高度。

代码实现：

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
39
40
41
42
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100  // 假设队列最大容量

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

int Btdepth(BiTree T) {
    // 采用层次遍历的非递归方法求解二叉树的高度
    if (!T) return 0;  // 树空，高度为0
    
    int front = -1, rear = -1;  // 队列指针
    int last = 0;  // last指向当前层的最右结点
    int level = 0;  // 记录层数
    BiTree Q[MaxSize];  // 队列，存储二叉树结点的指针
    
    Q[++rear] = T;  // 将根结点入队
    
    while (front < rear) {  // 队不空，则循环
        BiTree p = Q[++front];  // 队列元素出队，即正在访问的结点
        
        // 左孩子入队
        if (p->lchild) {
            Q[++rear] = p->lchild;
        }
        // 右孩子入队
        if (p->rchild) {
            Q[++rear] = p->rchild;
        }
        
        // 处理该层的最右结点
        if (front == last) {
            level++;  // 层数增1
            last = rear;  // last指向下层
        }
    }
    
    return level;  // 返回树的高度
}

解释：

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含数据和指向左右孩子的指针。
    • 使用数组 Q 来模拟队列，容量为 MaxSize。
  2. 初始化：
    • 首先检查二叉树是否为空，如果为空，则高度为 0。
  3. 层次遍历：
    • 将根结点入队，开始层次遍历。
    • 在遍历过程中，出队结点并访问它，依次将左右孩子入队。
    • 每当出队的结点的索引与 last 相等时，说明当前层已经遍历完毕，更新层数并设置 last 为当前队列的尾指针。
  4. 返回结果：
    • 完成遍历后，返回变量 level 的值作为二叉树的高度。

结果：

这个算法可以高效地计算出二叉树的高度，时间复杂度为 \(O(n)\)，其中 \(n\) 是树中结点的数量，因为每个结点都被访问了一次。对于结构较大的树，采用此非递归方法可以避免函数调用栈的深度限制。

通过这种方法，可以得到二叉树的高度，同时该算法也可以用于求某层的结点个数、每层的结点个数和树的最大宽度等问题，思路类似。

06：设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组 \(A[1..n]\) 和 \(B[1..n]\) 中，试编写算法建立该二叉树的二叉链表。

06.【解答】

算法思想： 由先序序列和中序序列可以唯一确定一棵二叉树。具体步骤如下： 1. 根据先序序列确定树的根结点。 2. 在中序序列中找到根结点，并划分出左、右子树的结点。 3. 根据左、右子树结点在先序序列中的次序确定子树的根结点。 4. 递归建立左子树和右子树，直到每棵子树只有一个结点（即该子树的根结点）。

步骤详解：

  • 根结点：在先序遍历中，第一个结点即为根结点。
  • 划分子树：在中序遍历中，根结点左边的结点属于左子树，右边的结点属于右子树。
  • 递归建立：根据划分得到的左子树和右子树的长度，递归调用建立二叉树的函数。

算法实现如下：

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
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;  // 假设结点的值类型为字符
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

BiTree PreInCreat(ElemType A[], ElemType B[], int l1, int h1, int l2, int h2) {
    // l1, h1 为先序的第一和最后一个结点下标
    // l2, h2 为中序的第一和最后一个结点下标
    
    if (l1 > h1 || l2 > h2) return NULL;  // 如果范围不合法，则返回空

    // 建根结点
    BiTree root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data = A[l1];  // 先序第一个结点为根结点

    // 在中序序列中查找根结点
    int i;
    for (i = l2; i <= h2; i++) {
        if (B[i] == root->data) break;  // 找到根结点在中序中的位置
    }

    // 左子树的长度
    int llen = i - l2;  
    // 右子树的长度
    int rlen = h2 - i;  

    // 递归建立左子树
    if (llen > 0) {
        root->lchild = PreInCreat(A, B, l1 + 1, l1 + llen, l2, i - 1);
    } else {
        root->lchild = NULL;  // 左子树为空
    }

    // 递归建立右子树
    if (rlen > 0) {
        root->rchild = PreInCreat(A, B, h1 - rlen + 1, h1, i + 1, h2);
    } else {
        root->rchild = NULL;  // 右子树为空
    }

    return root;  // 返回根结点指针
}

解释：

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含结点的数据和指向左右孩子的指针。
  2. 函数参数：
    • A[] 是先序遍历的数组。
    • B[] 是中序遍历的数组。
    • l1, h1 分别表示先序数组的开始和结束下标。
    • l2, h2 分别表示中序数组的开始和结束下标。
  3. 基础条件：
    • 如果当前子树范围无效（l1 > h1 或 l2 > h2），返回 NULL，表示没有子树。
  4. 建立根结点：
    • 根据先序数组的当前下标创建根结点。
  5. 查找根结点：
    • 在中序数组中找到根结点的位置，以便确定左、右子树的结点。
  6. 递归调用：
    • 使用分割得到的下标递归建立左子树和右子树。

结果：

通过这种方法，可以根据给定的先序和中序遍历序列构建出对应的二叉树。由于先序和中序序列的唯一性，算法的结果是确定的，时间复杂度为 \(O(n^2)\)（在每次查找根结点的过程中遍历中序数组），但可以通过使用哈希表优化到 \(O(n)\)。

07：给定一个二叉树，判断其是否为完全二叉树。

07.【解答】

算法思想： 根据完全二叉树的定义，完全二叉树是指在二叉树的每一层上都被完全填满，除了最后一层的结点外，最后一层的结点都在左边。

判断一个给定的二叉树是否为完全二叉树的算法步骤如下： 1. 采用层次遍历的方式，将所有结点（包括空结点）加入队列。 2. 遇到空结点时，检查其后是否有非空结点。如果有，则该二叉树不是完全二叉树。 3. 如果遍历完成没有发现不符合的条件，则该二叉树是完全二叉树。

算法实现如下：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef struct QueueNode {
    BiTree node;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 初始化队列
void InitQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// 入队
void EnQueue(Queue* q, BiTree node) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    if (q->rear) {
        q->rear->next = newNode;
    } else {
        q->front = newNode;
    }
    q->rear = newNode;
}

// 出队
BiTree DeQueue(Queue* q) {
    if (q->front == NULL) return NULL;
    QueueNode* temp = q->front;
    BiTree node = temp->node;
    q->front = temp->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return node;
}

// 判断队列是否为空
int IsEmpty(Queue* q) {
    return q->front == NULL;
}

// 判断给定二叉树是否为完全二叉树
bool IsComplete(BiTree T) {
    Queue Q;
    InitQueue(&Q);  // 初始化队列

    if (!T) return 1;  // 空树视为完全二叉树

    EnQueue(&Q, T);  // 将根结点入队

    bool isComplete = true;  // 用于标记是否为完全二叉树
    bool end = false;  // 标记是否已遇到空结点

    while (!IsEmpty(&Q)) {
        BiTree p = DeQueue(&Q);  // 出队当前结点

        if (p) {
            if (end) {
                isComplete = false;  // 遇到非空结点，标记为非完全二叉树
                break;
            }
            EnQueue(&Q, p->lchild);  // 左孩子入队
            EnQueue(&Q, p->rchild);  // 右孩子入队
        } else {
            end = true;  // 遇到空结点，之后不能再有非空结点
        }
    }

    return isComplete;  // 返回结果
}

解释：

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含结点的数据和指向左右孩子的指针。
    • QueueNode 用于实现队列，包含指向二叉树结点的指针。
    • Queue 结构体用于管理队列。
  2. 函数说明：
    • InitQueue()：初始化队列。
    • EnQueue()：将结点入队。
    • DeQueue()：将队头结点出队。
    • IsEmpty()：判断队列是否为空。
  3. 判断逻辑：
    • 如果树为空，返回 true，认为空树是完全二叉树。
    • 使用一个标志 end，初始为 false，用于表示是否遇到了空结点。
    • 在遍历中：
      • 若当前结点非空且 end 标志已被设置，则树不是完全二叉树。
      • 如果当前结点为空，则将 end 设置为 true，后续结点都不能是非空结点。
  4. 复杂度：
    • 时间复杂度为 \(O(n)\)，因为每个结点只被访问一次。
    • 空间复杂度为 \(O(n)\)，由于使用了队列来存储结点。

08：计算一棵给定二叉树中的所有双分支结点个数。

08.【解答】

算法思想： 双分支结点是指一个结点的左子树和右子树都不为空的结点。为了计算双分支结点的个数，可以使用递归的方法来遍历整棵二叉树，并在遍历过程中判断每个结点是否为双分支结点。

递归模型：

设函数 \(f(b)\) 表示二叉树 \(b\) 中的双分支结点个数。

  1. 如果 \(b\) 为空（即树为空），返回 0。
  2. 如果 \(b\) 是双分支结点（即 \(b\) 的左孩子和右孩子均不为空），返回 \(f(b->lchild) + f(b->rchild) + 1\)。
  3. 否则，返回 \(f(b->lchild) + f(b->rchild)\)（即 \(b\) 不是双分支结点）。

算法实现如下：

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

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 计算双分支结点个数的递归函数
int DSonNodes(BiTree b) {
    if (b == NULL) {
        return 0;  // 空树，双分支结点数为 0
    } else if (b->lchild != NULL && b->rchild != NULL) {
        // 结点是双分支结点
        return DSonNodes(b->lchild) + DSonNodes(b->rchild) + 1;
    } else {
        // 结点是单分支结点或叶子结点
        return DSonNodes(b->lchild) + DSonNodes(b->rchild);
    }
}

解释：

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含结点的数据和指向左右孩子的指针。
  2. 函数说明：
    • DSonNodes(BiTree b)：计算以结点 \(b\) 为根的子树中的双分支结点个数。
      • 若当前结点为空，返回 0。
      • 若当前结点是双分支结点，递归计算其左右子树的双分支结点个数，并加 1。
      • 否则，递归计算左右子树的双分支结点个数。
  3. 复杂度：
    • 时间复杂度为 \(O(n)\)，因为每个结点只被访问一次。
    • 空间复杂度为 \(O(h)\)，其中 \(h\) 为树的高度，用于递归调用的栈空间。

09：编写一个函数，将树B（采用链式结构存储的二叉树）中所有结点的左、右子树进行交换。

09.【解答】

算法思想： 采用递归算法实现交换二叉树的左、右子树。我们可以使用后序遍历的思想来进行交换操作，即在递归遍历到结点时，首先交换其左右子树，然后再进行左、右孩子的交换。具体步骤如下：

  1. 递归到当前结点的左孩子和右孩子。
  2. 交换当前结点的左右子树。
  3. 当结点为空时，递归结束。

算法实现如下：

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
39
40
#include <stdio.h>
#include <stdlib.h>

// 二叉树结点定义
typedef struct BiTNode {
    int data;  // 结点数据
    struct BiTNode *lchild;  // 左孩子
    struct BiTNode *rchild;  // 右孩子
} BiTNode, *BiTree;

// 交换二叉树的左、右子树
void swap(BiTree b) {
    if (b == NULL) {
        return;  // 递归结束条件
    }

    // 先递归交换左、右子树
    swap(b->lchild);
    swap(b->rchild);

    // 交换当前结点的左、右孩子
    BiTree temp = b->lchild;  // 暂存左子树
    b->lchild = b->rchild;     // 将右子树赋给左子树
    b->rchild = temp;          // 将暂存的左子树赋给右子树
}

// 示例：创建一个简单的二叉树并交换其左右子树
void printTree(BiTree b, int level) {
    if (b == NULL) {
        return;
    }
    printTree(b->rchild, level + 1);  // 先打印右子树
    for (int i = 0; i < level; i++) {
        printf("    ");  // 缩进表示树的层级
    }
    printf("%d\n", b->data);  // 打印当前结点
    printTree(b->lchild, level + 1);  // 后打印左子树
}


解释：

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含结点的数据和指向左右孩子的指针。
  2. 函数说明：
    • swap(BiTree b)：递归交换以结点 \(b\) 为根的子树的左、右子树。
      • 若当前结点为空，返回。
      • 先递归交换左子树和右子树。
      • 使用一个临时指针存储左子树，然后进行左右孩子的交换。
  3. 打印函数：
    • printTree(BiTree b, int level)：用于以层次结构的形式打印二叉树。
  4. 复杂度：
    • 时间复杂度为 \(O(n)\)，因为每个结点只被访问一次。
    • 空间复杂度为 \(O(h)\)，其中 \(h\) 为树的高度，用于递归调用的栈空间。

10：假设二叉树采用链式结构存储，设计一个算法，求先序遍历序列中第 $ k $ 个结点的值（$ 1 k $ 二叉树中结点个数）。

10.【解答】

算法思想： 1. 使用全局变量 $ i $ 来跟踪当前访问的结点的顺序。 2. 利用先序遍历的特性：首先访问根结点，然后是左子树，最后是右子树。 3. 当访问到第 $ k $ 个结点时，返回该结点的值。 4. 当二叉树为空时，返回特殊字符 '#' 表示结点不存在。

递归模型

设函数 PreNode(b, k) 为在二叉树 b 中查找第 $ k $ 个先序遍历结点的值： - 当 $ b $ 为空时，返回特殊字符 '#'。 - 当 $ i = k $ 时，返回结点值 $ b->data $。 - 否则，递归访问左子树和右子树。

算法实现

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 struct BiTNode {
    int data;  // 结点数据
    struct BiTNode *lchild;  // 左孩子
    struct BiTNode *rchild;  // 右孩子
} BiTNode, *BiTree;

// 遍历序号的全局变量
int i = 1;

// 查找二叉树先序遍历序列中第k个结点的值
char PreNode(BiTree b, int k) {
    if (b == NULL) {
        return '#';  // 空结点，则返回特殊字符
    }
    
    // 检查当前结点是否为第k个结点
    if (i == k) {
        return b->data;  // 找到第k个结点，返回结点值
    }
    
    i++;  // 访问下一个结点

    // 在左子树中查找
    char ch = PreNode(b->lchild, k);
    if (ch != '#') {
        return ch;  // 在左子树中找到，返回该值
    }
    
    // 在右子树中查找
    return PreNode(b->rchild, k);  // 在右子树中查找
}


解释：

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含数据和指向左右孩子的指针。
  2. 函数说明：
    • PreNode(BiTree b, int k)：递归查找二叉树 b 中第 $ k $ 个先序遍历结点的值。
      • 如果当前结点为空，返回特殊字符 '#'。
      • 如果当前结点是第 $ k $ 个结点，返回结点值。
      • 否则，递归访问左子树和右子树，返回找到的值。
  3. 复杂度：
    • 时间复杂度为 $ O(n) $，每个结点都可能被访问一次。
    • 空间复杂度为 $ O(h) $，其中 $ h $ 为树的高度，主要用于递归调用的栈空间。

11：已知二叉树以链式结构存储，编写算法完成：对于树中每个元素值为 $ x $ 的结点，删去以 $ x $ 为根的子树，并释放相应的空间。

11.【解答】

算法思想： 1. 后序遍历：要删除以 $ x $ 为根的子树，首先需要删除其左右子树，然后才能删除根结点本身。 2. 层次遍历：通过层次遍历（广度优先遍历）来找到每个结点的父结点，以便在删除子树时可以将父结点的指针置为 NULL。

主要步骤

  1. 定义函数 DeleteXTree(BiTree &bt) 用于递归删除以 $ bt $ 为根的子树。
  2. 定义函数 Search(BiTree bt, ElemType x) 用于遍历树，查找值为 $ x $ 的结点，并调用 DeleteXTree 删除其子树。
  3. 使用队列来实现层次遍历。

算法实现

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
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <stdlib.h>

// 二叉树结点定义
typedef struct BiTNode {
    int data;  // 结点数据
    struct BiTNode *lchild;  // 左孩子
    struct BiTNode *rchild;  // 右孩子
} BiTNode, *BiTree;

// 删除以bt为根的子树
void DeleteXTree(BiTree &bt) {
    if (bt) {
        DeleteXTree(bt->lchild);  // 删除左子树
        DeleteXTree(bt->rchild);  // 删除右子树
        free(bt);  // 释放当前结点
        bt = NULL; // 将当前结点指针置为空
    }
}

// 在二叉树上查找所有以x为元素值的结点，并删除以其为根的子树
void Search(BiTree bt, int x) {
    if (bt == NULL) return;

    // 使用队列进行层次遍历
    BiTree *queue = (BiTree *)malloc(sizeof(BiTree) * 100); // 假设队列最大容量为100
    int front = 0, rear = 0;
    
    queue[rear++] = bt;  // 入队根结点
    
    while (front < rear) {
        BiTree p = queue[front++];  // 出队
        if (p->data == x) {
            DeleteXTree(p);  // 删除以p为根的子树
            continue; // 由于已经删除，当前循环跳过
        }
        
        if (p->lchild) {
            queue[rear++] = p->lchild;  // 左子树入队
        }
        
        if (p->rchild) {
            queue[rear++] = p->rchild;  // 右子树入队
        }
    }
    
    free(queue);  // 释放队列内存
}


解释：

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含结点的数据和指向左右孩子的指针。
  2. 函数说明：
    • DeleteXTree(BiTree &bt)：递归删除以 $ bt $ 为根的子树。
      • 先删除左子树，再删除右子树，最后释放当前结点的内存，并将指针置为 NULL。
    • Search(BiTree bt, int x)：层次遍历二叉树，查找值为 $ x $ 的结点，并删除以其为根的子树。
      • 使用队列实现层次遍历，找到每个结点的父结点，并在找到匹配值时调用 DeleteXTree。
  3. 复杂度：
    • 时间复杂度为 $ O(n) $，每个结点最多被访问一次。
    • 空间复杂度为 $ O(w) $，其中 $ w $ 是树的最大宽度，主要用于队列存储。

12：在二叉树中查找值为 $ x $ 的结点，编写算法（用 C 语言）打印值为 $ x $ 的结点的所有祖先，假设值为 $ x $ 的结点不多于一个。

12.【解答】

算法思想

采用非递归的后序遍历，通过使用一个栈来模拟递归过程。当找到值为 $ x $ 的结点时，栈中的所有元素都为该结点的祖先。通过逆序遍历栈来打印这些祖先结点的值。

主要步骤

  1. 定义一个栈结构，用于存储遍历的结点和访问标记。
  2. 使用循环和条件判断进行非递归后序遍历。
  3. 当找到值为 $ x $ 的结点时，打印栈中的所有结点。

算法实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h>

// 二叉树结点定义
typedef struct BiTNode {
    int data;  // 结点数据
    struct BiTNode *lchild;  // 左孩子
    struct BiTNode *rchild;  // 右孩子
} BiTNode, *BiTree;

// 栈结构
typedef struct {
    BiTree t;  // 指向二叉树结点的指针
    int tag;   // 标记，0表示左子女被访问，1表示右子女被访问
} Stack;

// 查找值为x的结点，并打印其所有祖先
void Search(BiTree bt, int x) {
    Stack *s = (Stack *)malloc(sizeof(Stack) * 100); // 栈容量足够大
    int top = -1;  // 栈顶指针

    while (bt != NULL || top >= 0) {
        // 遍历左分支
        while (bt != NULL) {
            s[++top].t = bt;  // 结点入栈
            s[top].tag = 0;   // 标记为访问左子树
            bt = bt->lchild;  // 沿左分支向下
        }
        
        // 访问栈顶结点
        if (top >= 0) {
            bt = s[top].t;  // 取出栈顶结点
            
            // 检查当前结点的值是否为x
            if (bt->data == x) {
                printf("所查结点的所有祖先结点的值为:\n");
                for (int i = 0; i < top; i++) {
                    printf("%d ", s[i].t->data); // 打印祖先结点的值
                }
                free(s);  // 释放栈内存
                exit(0);  // 找到后退出
            }
            
            // 处理右子树
            if (s[top].tag == 0) {
                s[top].tag = 1;  // 将当前结点标记为已访问左子树
                bt = bt->rchild;  // 访问右子树
            } else {
                top--;  // 左右子树都已访问，出栈
                bt = NULL;  // 继续处理下一个结点
            }
        }
    }
    
    printf("未找到值为 %d 的结点。\n", x); // 未找到值为x的结点
    free(s);  // 释放栈内存
}

解释

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含结点的数据和指向左右孩子的指针。
    • Stack 结构体用于存储栈中的结点和访问状态。
  2. 函数说明：
    • Search(BiTree bt, int x)：在二叉树中查找值为 $ x $ 的结点，并打印其所有祖先。
      • 使用一个栈来模拟后序遍历。通过 tag 标记判断当前结点是否已经访问过左子树。
      • 当找到值为 $ x $ 的结点时，打印栈中所有结点的值。
  3. 复杂度：
    • 时间复杂度为 $ O(n) $，其中 $ n $ 是树中结点的数量。
    • 空间复杂度为 $ O(h) $，其中 $ h $ 是树的高度（栈的最大深度）。

解答：

算法思想

使用非递归的后序遍历，利用栈来保存二叉树的结点。当遍历到某个结点时，栈中的所有元素均为该结点的祖先。在找到结点 P 后，将栈中的内容复制到一个辅助栈中。继续遍历到结点 Q 时，从栈顶开始逐个与辅助栈的元素进行匹配，首次匹配的元素就是 P 和 Q 的最近公共祖先。

算法实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>

// 二叉树结点定义
typedef struct BiTNode {
    int data;  // 结点数据
    struct BiTNode *lchild;  // 左孩子
    struct BiTNode *rchild;  // 右孩子
} BiTNode, *BiTree;

// 栈结构
typedef struct {
    BiTree t;  // 指向二叉树结点的指针
    int tag;   // 标记，0表示左子女已被访问，1表示右子女已被访问
} Stack;

// 查找p和q的最近公共祖先
BiTree Ancestor(BiTree ROOT, BiTNode *p, BiTNode *q) {
    Stack s[100], s1[100]; // 栈，容量足够大
    int top = -1;          // 栈顶指针
    int top1 = -1;         // 辅助栈的栈顶指针
    BiTree bt = ROOT;

    // 遍历二叉树
    while (bt != NULL || top >= 0) {
        while (bt != NULL) {
            s[++top].t = bt; // 结点入栈
            s[top].tag = 0;  // 标记为访问左子树
            bt = bt->lchild; // 沿左分支向下
        }

        // 处理栈顶结点
        if (top >= 0) {
            bt = s[top].t; // 取出栈顶结点

            // 假定p在q的左侧，遇到p时，栈中元素均为p的祖先
            if (s[top].t == p) {
                for (int i = 0; i <= top; i++) {
                    s1[++top1] = s[i]; // 将栈s的元素转入辅助栈s1保存
                }
                // 找到q结点
                while (top >= 0) {
                    if (s[top].t == q) {
                        for (int i = top; i >= 0; i--) { // 遍历栈s
                            for (int j = top1; j >= 0; j--) { // 遍历辅助栈s1
                                if (s1[j].t == s[i].t) {
                                    return s[i].t; // p和q的最近公共祖先已找到
                                }
                            }
                        }
                    }
                    top--; // 退栈
                }
            } else {
                // 处理右子树
                if (s[top].tag == 0) {
                    s[top].tag = 1; // 标记为右子树已被访问
                    bt = s[top].t->rchild; // 访问右子树
                } else {
                    top--; // 退栈
                    bt = NULL; // 继续处理下一个结点
                }
            }
        }
    }

    return NULL; // p和q无公共祖先
}

解释

  1. 数据结构：
    • BiTNode 结构体表示二叉树的结点，包含结点的数据和指向左右孩子的指针。
    • Stack 结构体用于存储栈中的结点和访问状态。
  2. 函数说明：
    • Ancestor(BiTree ROOT, BiTNode *p, BiTNode *q)：在二叉树中查找 p 和 q 的最近公共祖先。
      • 使用一个栈来模拟后序遍历。通过 tag 标记判断当前结点是否已经访问过左子树。
      • 当找到结点 P 时，复制栈内容到辅助栈 s1。继续遍历到结点 Q，进行匹配。
  3. 复杂度：
    • 时间复杂度为 $ O(n) $，其中 $ n $ 是树中结点的数量。
    • 空间复杂度为 $ O(h) $，其中 $ h $ 是树的高度（栈的最大深度）。

14.要设计一个算法来求非空二叉树的宽度（即具有结点数最多的那一层的结点个数），我们可以采用层次遍历的方法。下面是算法的实现思路和详细步骤：

算法思路

  1. 层次遍历：使用队列进行层次遍历。每次出队一个节点时，检查其左右子节点，并将它们入队。同时记录每个节点的层次。

  2. 层次统计：使用一个数组或变量来统计每一层的节点数，遍历结束后，找到节点数最多的层。

数据结构

我们需要一个队列来存储节点及其层次信息。队列可以用数组实现，包含以下两个属性： - data: 存储队列中的节点指针。 - level: 存储对应节点的层次。

算法实现

下面是求非空二叉树宽度的算法实现代码：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100 // 定义队列的最大容量

typedef struct BiTNode {
    struct BiTNode *lchild, *rchild;
    int data; // 这里假设节点包含一个整数数据
} BiTNode, *BiTree;

typedef struct {
    BiTree data[MaxSize]; // 保存队列中的节点指针
    int front, rear; // 队列的头和尾
    int level[MaxSize]; // 保存 data 中相同下标节点的层次
} Qu;

// 初始化队列
void InitQueue(Qu *q) {
    q->front = q->rear = -1; // 队列为空
}

// 入队
void Enqueue(Qu *q, BiTree node, int lvl) {
    if (q->rear < MaxSize - 1) { // 确保队列未满
        q->rear++;
        q->data[q->rear] = node; // 入队节点
        q->level[q->rear] = lvl; // 入队节点的层次
    }
}

// 出队
BiTree Dequeue(Qu *q, int *lvl) {
    if (q->front < q->rear) { // 队列非空
        q->front++;
        *lvl = q->level[q->front];
        return q->data[q->front]; // 返回出队的节点
    }
    return NULL; // 队列空
}

// 计算二叉树宽度
int BTwidth(BiTree b) {
    Qu queue;
    InitQueue(&queue);
    int max = 0; // 存储最大宽度
    int levelCount[MaxSize] = {0}; // 统计各层的节点数

    if (b != NULL) {
        Enqueue(&queue, b, 1); // 根节点入队，层次为1
    }

    while (queue.front < queue.rear) { // 遍历队列
        int currentLevel = 1;
        int n = 0; // 当前层节点计数
        
        while (queue.front < queue.rear) { // 统计当前层节点数
            BiTree p = Dequeue(&queue, &currentLevel); // 出队
            if (p != NULL) {
                n++; // 当前层节点数加一
                if (p->lchild != NULL) {
                    Enqueue(&queue, p->lchild, currentLevel + 1); // 左孩子入队
                }
                if (p->rchild != NULL) {
                    Enqueue(&queue, p->rchild, currentLevel + 1); // 右孩子入队
                }
            }
            if (queue.front < queue.rear && queue.level[queue.front + 1] != currentLevel) {
                break; // 当前层遍历完成
            }
        }
        
        // 更新最大宽度
        if (n > max) {
            max = n;
        }
    }
    
    return max; // 返回二叉树的宽度
}

代码解释

  1. 队列结构：Qu结构体用于实现队列，包含节点指针数组data和层次数组level。

  2. 初始化和基本操作：实现了入队（Enqueue）和出队（Dequeue）操作。

  3. 计算宽度：BTwidth函数实现层次遍历，统计每层的节点数量并更新最大宽度。

  4. 示例主函数：示例中构建了一棵二叉树并调用BTwidth函数来输出其宽度。

注意事项

  • 队列的实现采用非环形方式以避免出队后节点信息丢失。
  • 程序应确保在使用后释放分配的内存以避免内存泄漏。

15.要设计一个算法，将满二叉树的先序遍历序列转换为后序遍历序列，我们可以利用满二叉树的特点进行递归转换。下面是详细的算法说明和实现。

问题描述

在满二叉树中： - 每个节点都有两个子节点（左子树和右子树）。 - 左子树和右子树的节点数相等。

给定满二叉树的先序序列 $ $，我们需要生成其后序序列 $ $。

递归算法

  1. 递归模型：利用递归函数 PreToPost(pre, l1, h1, post, l2, h2) 来实现转换。

    • $ l1 $ 和 $ h1 $ 是先序序列的索引范围，表示当前处理的子树在先序序列中的位置。
    • $ l2 $ 和 $ h2 $ 是后序序列的索引范围，表示当前处理的子树在后序序列中的位置。
    • 先序序列的第一个元素 $ [l1] $ 是当前子树的根节点，应该放在后序序列的最后。

  2. 递归终止条件：如果 $ h1 < l1 $，表示当前子树没有节点，直接返回。

  3. 计算子树的大小：

    • 满二叉树的节点数是 $ 2^k - 1 $，其中 $ k $ 是树的深度。
    • 通过 $ = $ 计算左子树和右子树的大小。

  4. 递归调用：

    • 将左子树的先序序列转换为后序序列。
    • 将右子树的先序序列转换为后序序列。
    • 将根节点放入后序序列的最后。

代码实现

以下是完整的 C 语言代码实现：

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
#include <stdio.h>
#include <string.h>

#define MaxSize 100
typedef char ElemType;

// 将先序序列转换为后序序列
void PreToPost(ElemType pre[], int l1, int h1, ElemType post[], int l2, int h2) {
    if (h1 < l1) {
        return; // 递归终止条件
    }
    
    // 将先序序列的第一个元素放入后序序列的最后
    post[h2] = pre[l1];

    // 计算左子树的大小
    int half = (h1 - l1) / 2;

    // 转换左子树
    PreToPost(pre, l1 + 1, l1 + half, post, l2, l2 + half - 1);
    
    // 转换右子树
    PreToPost(pre, l1 + half + 1, h1, post, l2 + half, h2 - 1);
}

代码解释

  1. 数据定义：
    • ElemType 是节点类型，这里定义为字符。
    • MaxSize 是存储后序序列的最大大小。
  2. 递归函数 PreToPost：
    • 输入参数：pre[] 是先序序列，post[] 是后序序列，l1, h1 和 l2, h2 分别表示先序序列和后序序列的索引范围。
    • 通过递归将先序序列的左子树和右子树转换为后序序列，最后将根节点放入后序序列的最后。
  3. 主函数 main：
    • 初始化先序序列并调用 PreToPost 函数。
    • 输出转换后的后序序列。

示例运行结果

对于先序序列 "ABCDEFG"，运行结果将是： 

1
后序序列: CDBFGEA

16.我们需要将二叉树的所有叶节点按从左到右的顺序连接成一个单链表。二叉树采用链表存储方式，叶节点的右指针域用于存放链表指针，链表的头指针为 head。

算法思想

  1. 中序遍历：我们选择中序遍历来访问二叉树的叶节点。中序遍历会首先遍历左子树，然后访问当前节点，最后遍历右子树。

  2. 前驱指针：使用一个前驱节点指针 pre 来指向当前正在处理的叶节点。初始时，pre 为空，表示尚未连接任何叶节点。

  3. 连接叶节点：

    • 当遍历到一个叶节点时，判断 pre 是否为空：
      • 如果为空，表示这是第一个叶节点，将 head 指向这个节点。
      • 如果不为空，将 pre 的右指针指向当前叶节点。
    • 更新 pre 为当前叶节点。

  4. 结束处理：最后一个叶节点的右指针指向 NULL，表示链表的结束。

代码实现

以下是 C 语言的完整实现：

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
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>

typedef struct BiTreeNode {
    char data;
    struct BiTreeNode* lchild;
    struct BiTreeNode* rchild;
} BiTreeNode, *BiTree;

typedef struct LinkedListNode {
    char data;
    struct LinkedListNode* rchild; // 用于连接叶节点的右指针
} LinkedListNode, *LinkedList;

// 全局变量
LinkedList head = NULL;  // 链表头指针
LinkedList pre = NULL;   // 前驱指针

// 中序遍历函数
void InOrder(BiTree bt) {
    if (bt) {
        // 遍历左子树
        InOrder(bt->lchild);
        
        // 处理当前节点
        if (bt->lchild == NULL && bt->rchild == NULL) { // 叶节点
            if (pre == NULL) {
                head = (LinkedList)malloc(sizeof(LinkedListNode));
                head->data = bt->data; // 赋值叶节点数据
                head->rchild = NULL;
                pre = head; // 更新前驱指针
            } else {
                pre->rchild = (LinkedList)malloc(sizeof(LinkedListNode));
                pre->rchild->data = bt->data; // 赋值叶节点数据
                pre->rchild->rchild = NULL;
                pre = pre->rchild; // 更新前驱指针
            }
        }

        // 遍历右子树
        InOrder(bt->rchild);
    }
}


代码解释

  1. 数据结构定义：
    • BiTreeNode 表示二叉树节点，包含数据和左右子节点指针。
    • LinkedListNode 表示链表节点，包含数据和右指针（用于连接）。
  2. 全局变量：
    • head 是链表头指针。
    • pre 是前驱指针。
  3. 中序遍历函数 InOrder：
    • 遍历二叉树，处理叶节点并将其添加到链表中。
    • 对于每个叶节点，更新 head 和 pre 指针以构建链表。
  4. 主函数 main：
    • 创建一个示例二叉树。
    • 调用 InOrder 函数生成叶节点链表。
    • 输出链表的内容。

示例运行结果

对于构建的示例二叉树，输出的叶节点链表将是： 

1
叶节点链表: D E F G

复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数，因为每个节点被访问一次。
  • 空间复杂度：O(n)，用于存储链表和递归调用栈的空间。

17.设计一个算法判断两棵二叉树是否相似。

相似的定义如下： - 两棵二叉树 \(T_1\) 和 \(T_2\) 都为空的二叉树，或都只有一个根节点； - \(T_1\) 的左子树与 \(T_2\) 的左子树相似，且 \(T_1\) 的右子树与 \(T_2\) 的右子树相似。

算法思想

我们可以使用递归的方式来判断两棵二叉树是否相似。具体步骤如下：

  1. 基准情况：
    • 如果两棵树都为空，返回相似（返回1）。
    • 如果其中一棵树为空而另一棵树不为空，返回不相似（返回0）。
  2. 递归比较：
    • 如果两棵树都不为空，递归判断它们的左子树和右子树是否相似：
      • 调用 similar(T1->lchild, T2->lchild) 检查左子树。
      • 调用 similar(T1->rchild, T2->rchild) 检查右子树。
  3. 返回结果：
    • 返回左子树和右子树的相似性结果的逻辑与（AND）值。

代码实现

以下是 C 语言的完整实现代码：

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 struct BiTreeNode {
    char data;
    struct BiTreeNode* lchild;
    struct BiTreeNode* rchild;
} BiTreeNode, *BiTree;

// 判断两棵二叉树是否相似的函数
int similar(BiTree T1, BiTree T2) {
    // 两树皆空
    if (T1 == NULL && T2 == NULL) {
        return 1; // 相似
    }
    // 只有一棵树为空
    else if (T1 == NULL || T2 == NULL) {
        return 0; // 不相似
    } else {
        // 递归判断左子树和右子树
        int leftS = similar(T1->lchild, T2->lchild);
        int rightS = similar(T1->rchild, T2->rchild);
        return leftS && rightS; // 返回相似性
    }
}

代码解释

  1. 数据结构定义：
    • BiTreeNode 表示二叉树节点，包含数据和左右子节点指针。
  2. 相似性判断函数 similar：
    • 首先判断两棵树是否都为空。
    • 然后判断其中一棵树是否为空。
    • 递归调用检查左子树和右子树的相似性，最终返回它们的逻辑与值。
  3. 主函数 main：
    • 创建两棵示例二叉树 tree1 和 tree2。
    • 调用 similar 函数判断它们是否相似，并输出结果。

示例运行结果

对于上面创建的示例二叉树，输出将是： 

1
两棵二叉树相似

复杂度分析

  • 时间复杂度：O(n)，其中 n 是较小树的节点数，因为每个节点最多被访问一次。
  • 空间复杂度：O(h)，其中 h 是树的高度，主要用于递归调用的栈空间。

18.在中序线索二叉树中，设计一个算法查找指定结点在后序遍历中的前驱结点。后序遍历的前驱结点是指在后序序列中紧接在该结点之前的结点。

算法思想

  1. 判断右子女：
    • 如果结点 $ p $ 有右子女（即 $ p $ 的右线索为 0），则 $ p $ 的右子女是其后序前驱。
  2. 判断左子女：
    • 如果结点 $ p $ 只有左子女（即 $ p $ 的右线索为 1，且左线索为 0），则 $ p $ 的左子女是其后序前驱。
  3. 无子女情况：
    • 如果结点 $ p $ 既没有左子女也没有右子女，则需要向上查找。我们沿着左线索查找 $ p $ 的祖先，直到找到一个祖先有左子女的结点，该左子女即为 $ p $ 的后序前驱。
    • 特殊情况：如果 $ p $ 是中序遍历的第一个结点，则 $ p $ 在中序和后序遍历下均无前驱。

代码实现

以下是 C 语言的完整实现代码：

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
39
40
41
42
43
44
#include <stdio.h>
#include <stdlib.h>

typedef struct BiThrTreeNode {
    char data;
    struct BiThrTreeNode* lchild; // 左子女指针
    struct BiThrTreeNode* rchild; // 右子女指针
    int ltag; // 左线索标志，0表示有左子女，1表示左线索
    int rtag; // 右线索标志，0表示有右子女，1表示右线索
} BiThrTreeNode, *BiThrTree;

// 查找后序前驱结点的函数
BiThrTree InPostPre(BiThrTree tBiThrTree p) {
    BiThrTree q = NULL; // 初始化前驱结点指针

    // 若结点p有右子女，则右子女是其后序前驱
    if (p->rtag == 0) {
        q = p->rchild; // 找到右子女
    } 
    // 若结点p没有右子女，但有左子女，则左子女是其后序前驱
    else if (p->ltag == 0) {
        q = p->lchild; // 找到左子女
    } 
    // 若结点p无左子女和右子女
    else if (p->lchild == NULL) {
        // p是中序序列第一结点，无后序前驱
        q = NULL; 
    } else {
        // 顺左线索向上找p的祖先，若存在，再找祖先的左子女
        while (p->ltag == 1 && p->lchild != NULL) {
            p = p->lchild; // 沿左线索向上查找
        }
        // 若找到的祖先有左子女，则该左子女是p的后序前驱
        if (p->ltag == 0) {
            q = p->lchild; // 找到祖先的左子女
        } else {
            // 仅有单支树(p是叶子)，已到根结点，p无后序前驱
            q = NULL;
        }
    }
    return q; // 返回后序前驱结点
}


代码解释

  1. 数据结构定义：
    • BiThrTreeNode 表示中序线索二叉树的节点，包含数据和左右子节点指针，以及左右线索标志。
  2. 查找后序前驱的函数 InPostPre：
    • 首先判断结点 $ p $ 是否有右子女。
    • 如果没有右子女，接着判断是否有左子女。
    • 如果都没有，判断 $ p $ 是否是中序序列的第一个结点。
    • 若以上条件都不满足，向上查找祖先的左子女。
  3. 主函数 main：
    • 构造一棵简单的中序线索二叉树。
    • 调用 InPostPre 函数查找结点 $ C $ 的后序前驱，并输出结果。

示例运行结果

对于上面构造的示例树，输出将是： 

1
结点C的后序前驱是：A

复杂度分析

  • 时间复杂度：O(h)，其中 h 是树的高度，主要取决于沿着线索查找的路径长度。
  • 空间复杂度：O(1)，不使用额外的存储空间。

19.2014统考真题：二叉树的带权路径长度 (WPL) 是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结构如下：

1
2
3
4
5
typedef struct node {
    struct node *left;  // 指向左子树
    int weight;         // 叶结点的权值
    struct node *right; // 指向右子树
} BiTree;

设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法，要求：

  1. 给出算法的基本设计思想。
  2. 使用 C 或 C++ 语言，给出二叉树结点的数据类型定义。
  3. 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

1) 算法的基本设计思想

二叉树的带权路径长度 (WPL) 是所有叶结点的带权路径长度之和。带权路径长度是指每个叶结点的权值乘以其到根结点的路径长度。

为了求得 WPL，可以采用递归遍历的方法，遍历整棵树并对每个叶结点进行处理。具体步骤如下：

  • 定义一个递归函数，接收当前节点和当前深度作为参数。
  • 如果当前节点是叶结点，则将其权值乘以当前深度，并累加到 WPL 中。
  • 如果当前节点不是叶结点，则递归遍历其左子树和右子树，深度加一。

1. 基于先序遍历的算法

以下是基于先序遍历的 WPL 计算算法：

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>

// 二叉树节点的定义
typedef struct BiTreeNode {
    struct BiTreeNode* left;   // 指向左子树
    struct BiTreeNode* right;  // 指向右子树
    int weight;                // 叶结点的权值
} BiTreeNode, *BiTree;

// 计算 WPL 的主函数
int WPL(BiTree root) {
    return wplPreOrder(root, 0); // 从根节点开始遍历，深度初始化为 0
}

// 递归实现先序遍历计算 WPL
int wplPreOrder(BiTree root, int depth) {
    static int wpl = 0; // 静态变量存储 WPL
    if (root == NULL) // 如果当前结点为空，则返回
        return wpl;

    // 如果是叶节点，累加 WPL
    if (root->left == NULL && root->right == NULL) {
        wpl += depth * root->weight;
    }
    
    // 递归遍历左子树
    if (root->left != NULL) {
        wplPreOrder(root->left, depth + 1);
    }
    
    // 递归遍历右子树
    if (root->right != NULL) {
        wplPreOrder(root->right, depth + 1);
    }
    
    return wpl; // 返回 WPL
}

2. 基于层次遍历的算法

以下是基于层次遍历的 WPL 计算算法：

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
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#define MaxSize 100 // 定义队列的最大容量

// 二叉树节点的定义
typedef struct BiTreeNode {
    struct BiTreeNode* left;   // 指向左子树
    struct BiTreeNode* right;  // 指向右子树
    int weight;                // 叶结点的权值
} BiTreeNode, *BiTree;

// 层次遍历计算 WPL
int WPL_LevelOrder(BiTree root) {
    if (root == NULL) return 0; // 如果根节点为空，返回 0

    BiTree q[MaxSize]; // 队列数组
    int head = 0, tail = 0; // 队列的头指针和尾指针
    int wpl = 0; // 存储 WPL
    int depth = 0; // 存储当前深度

    // 将根节点入队
    q[tail++] = root; 

    // 循环遍历队列
    while (head < tail) {
        int levelSize = tail - head; // 当前层的节点数量
        for (int i = 0; i < levelSize; i++) {
            BiTree t = q[head++]; // 取出队列头元素
            
            // 如果是叶节点，统计 WPL
            if (t->left == NULL && t->right == NULL) {
                wpl += depth * t->weight;
            }

            // 如果左子树存在，将左子树入队
            if (t->left != NULL) {
                q[tail++] = t->left;
            }

            // 如果右子树存在，将右子树入队
            if (t->right != NULL) {
                q[tail++] = t->right;
            }
        }
        depth++; // 深度加 1
    }
    
    return wpl; // 返回 WPL
}

20.【2017统考真题】：请设计一个算法，将给定的表达式树（即二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两表达式树作为算法的输入时，输出的等价中缀表达式分别为 $ (a+b)(c(-d)) $ 和 $ (a*b)+(-(c-d)) $。

二叉树节点定义如下：

1
2
3
4
typedef struct node {
    char data[10]; // 存储操作数或操作符
    struct node *left, *right; // 指向左右子树
} BTree;

要求： 1. 给出算法的基本设计思想。 2. 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

一、算法的基本设计思想

要将表达式树转换为等价的中缀表达式，需要基于中序遍历的策略，并在适当的位置加上括号。基本步骤如下：

  1. 中序遍历：按照中序遍历的顺序访问树的结点，从而形成一个表达式的线性表示。

  2. 括号处理：

    • 当遍历到一个分支结点（操作符）时，若其有子树，则在输出该操作符前后添加括号，以确保操作符的计算顺序符合优先级。
    • 叶结点（操作数）直接输出，不需要添加括号。

  3. 控制深度：通过深度参数控制何时添加括号。根结点和叶结点不需要添加括号，而内部结点需要根据其子树的存在情况决定。

二、算法实现

以下是使用 C 语言实现的算法，包含二叉树结点的定义和转换为中缀表达式的函数：

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
39
40
41
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    char data[10];             // 存储操作数或操作符
    struct node *left;        // 指向左子树
    struct node *right;       // 指向右子树
} BTree;

// 将表达式树转换为中缀表达式的主函数
void BTreeToE(BTree *root) {
    BTreeToExp(root, 1); // 根的高度为 1
}

// 递归实现中序遍历生成中缀表达式
void BTreeToExp(BTree *root, int deep) {
    // 空结点返回
    if (root == NULL) return;

    // 如果是叶结点，直接输出操作数
    if (root->left == NULL && root->right == NULL) {
        printf("%s", root->data);
    } else {
        // 如果有子表达式，则加左括号
        if (deep > 1) printf("(");

        // 递归遍历左子树
        BTreeToExp(root->left, deep + 1);

        // 输出操作符
        printf("%s", root->data);

        // 递归遍历右子树
        BTreeToExp(root->right, deep + 1);

        // 如果有子表达式，则加右括号
        if (deep > 1) printf(")");
    }
}


代码说明

  1. 结点定义：BTree 结构体包含操作数/操作符及其左右子树的指针。

  2. BTreeToE 函数：主函数，负责初始化调用中序遍历的递归函数 BTreeToExp。

  3. BTreeToExp 函数：

    • 递归遍历树的结点。
    • 如果当前结点是叶结点（无子树），直接输出操作数。
    • 如果是分支结点，则在遍历左子树前加左括号，在遍历右子树后加右括号，确保操作符的优先级被正确反映。