一、实验内容

本实验要求实现以下功能：

  1. 按先序次序建立一颗二叉树，以‘@’表示空。
  2. 中序、后序和层序遍历该二叉树，输出遍历序列。
  3. 求出该二叉树的深度并输出
  4. 求出该二叉树的叶子数目并输出
  5. 判断该二叉树是否是完全二叉树

二、测试数据

输入以下字符串，建立二叉树：ABC@@DE@G@@F@@@
输出中序遍历序列应为：CBEGDFA
输出后序遍历序列应为：CGEFDBA
输出层次遍历序列应为：ABCDEFG
输出二叉树的深度应为：5
输出二叉树的叶子数目应为：3
该二叉树不是完全二叉树

三、解答

graph LR
A((开始)) --> B[输入字符串建立二叉树]
B --> C[创建二叉树]
C --> D[中序遍历序列]
C --> E[后序遍历序列]
C --> F[层序遍历序列]
C --> G[二叉树的深度]
C --> H[二叉树的叶子数目]
C --> I[判断是否完全二叉树]
D --> J((结束))
E --> J
F --> J
G --> J
H --> J
I --> J
J --> K{是否完全二叉树?}
K -- 是 --> L[输出是完全二叉树]
K -- 否 --> M[输出不是完全二叉树]
M --> J

层序遍历

graph LR
A((开始)) --> B[输入字符串]
B --> C[建立二叉树]
C --> D[层序遍历函数调用]
D --> E[创建队列]
E --> F[根节点入队]
F --> G[循环直到队列为空]
G --> H[取出队首节点]
H --> I[输出节点值]
H --> J[将左子节点入队]
H --> K[将右子节点入队]
G --> F
I --> L[判断队列是否为空]
L -- 是 --> M((结束))
L -- 否 --> G

中序遍历

graph LR
A((开始)) --> B[输入字符串]
B --> C[建立二叉树]
C --> D[中序遍历函数调用]
D --> E[递归调用左子节点]
E --> F[输出节点值]
E --> G[递归调用右子节点]
F --> H[判断节点是否为空]
H -- 是 --> I((结束))
H -- 否 --> E

后序遍历

graph LR
A((开始)) --> B[输入字符串]
B --> C[建立二叉树]
C --> D[后序遍历函数调用]
D --> E[递归调用左子节点]
E --> F[递归调用右子节点]
F --> G[输出节点值]
G --> H[判断节点是否为空]
H -- 是 --> I((结束))
H -- 否 --> E
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include<iostream>
#include<queue>
#include <vector>
#include <stdlib.h> 
#define MAXsize 100

using namespace std;

typedef struct BTNode {
    BTNode* lchild;
    BTNode* rchild;
    char val;
    BTNode(char data) :val(data), lchild(nullptr), rchild(nullptr) {};
};

// 按先序次序建立一颗二叉树，以‘@’表示空。
BTNode* CreateTree(string input, int& index) {
    if (index >= input.length() || input[index] == '@') {
        index++;
        return nullptr;
    }
    BTNode* root = new BTNode(input[index]);
    index++;
    root->lchild = CreateTree(input, index);
    root->rchild = CreateTree(input, index);
    return root;
}

// 中序遍历
void InOrder(BTNode* b) {
    if (b != nullptr) {
        InOrder(b->lchild);
        cout << b->val;
        InOrder(b->rchild);
    }
}

// 后序遍历
void PostOrder(BTNode* b) {
    if (b != nullptr) {
        PostOrder(b->lchild);
        PostOrder(b->rchild);
        cout << b->val;
    }
}

// 层序遍历
void LevelOrder(BTNode* b) {
    if (b == nullptr)
        return;
    queue<BTNode*> q;
    q.push(b);
    while (!q.empty()) {
        BTNode* cur = q.front();
        cout << cur->val;
        q.pop();
        if (cur->lchild)
            q.push(cur->lchild);
        if (cur->rchild)
            q.push(cur->rchild);
    }
}

// 求二叉树的深度
int TreeDepth(BTNode* root) {
    if (root == nullptr)
        return 0;
    int leftdepth = TreeDepth(root->lchild);
    int rightdepth = TreeDepth(root->rchild);
    return max(leftdepth, rightdepth) + 1;
}

// 求二叉树的叶子数目
int CountLeaves(BTNode* root) {
    if (root == nullptr)
        return 0;
    else if (root->lchild == nullptr && root->rchild == nullptr)
        return 1;
    return CountLeaves(root->lchild) + CountLeaves(root->rchild);
}

// 判断二叉树是否为完全二叉树
bool IsCompleteBinaryTree(BTNode* root) {
    if (root == nullptr)
        return true;
    queue<BTNode*> q;
    q.push(root);
    bool hasEmpty = false;
    while (!q.empty()) {
        BTNode* node = q.front();
        q.pop();
        if (hasEmpty && (node->lchild || node->rchild))
            return false;
        if (!node->lchild)
            hasEmpty = true;
        else if (hasEmpty)
            return false;
        if (node->lchild)
            q.push(node->lchild);
        if (node->rchild)
            q.push(node->rchild);
    }
    return true;
}

int main() {
    string input = "ABC@@DE@G@@F@@@";
    int index = 0;
    BTNode* root = CreateTree(input, index);

    cout << "中序遍历序列: ";
    InOrder(root);
    cout << endl;

    cout << "后序遍历序列: ";
    PostOrder(root);
    cout << endl;

    cout << "层序遍历序列: ";
    LevelOrder(root);
    cout << endl;

    cout << "二叉树的深度: " << TreeDepth(root) << endl;

    cout << "二叉树的叶子数目: " << CountLeaves(root) << endl;

    bool isComplete = IsCompleteBinaryTree(root);
    if (isComplete)
        cout << "该二叉树是完全二叉树" << endl;
    else
        cout << "该二叉树不是完全二叉树" << endl;
    system("pause");
    return 0;
}