树 超基础二叉树知识

编写一个程序,实现二叉树的基本运算,具体要求如下:

  1. 括号表示法读入数据
  2. 括号表示法输出该树
  3. 输入一个结点的值,输出该结点的左,右孩子的值(要能测试错误数据)
  4. 输出该二叉树的高度
  5. 输出该二叉树结点的个数
  6. 输出该二叉树双分支结点的个数
  7. 输出该二叉树单分支结点的个数
  8. 输出该二叉树叶子结点的个数
  9. 输出该二叉树的宽度(宽度为每层结点数的最大值)
  10. 任意给定该二叉树的两个结点,输出它们的最近的公共祖先
  11. 销毁该二叉树

运行结果:



-1.变量定义

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
const int MaxSize = 50;

typedef char ElementType; //typedef用来给数据类型char起别名(ElementType)
typedef struct bitnode
{
ElementType data;
struct bitnode *left, *right;
} bitnode, *bitree; //bitree为指向bitnode这种自定义数据的指针

0. 括号表示法读入数据

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
//----------------------------------------------------
//根据嵌套括号表示法的字符串生成链式存储的二叉树
void CreateTree(bitree &b, char str[]){
char ch;
bitree stack[MaxSize], p; //stack[MaxSize]为指针数组,其每一个元素都为指向bitnode这种结构的指针,p为临时指针
int top = -1, k = 0, j = 0; //top为栈顶指针、k决定谁是左、右孩子、j为str指针

while ((ch = str[j++]) != '\0'){
switch (ch)
{
case '(':
top++;
stack[top] = p; //根结点入栈
k = 1; //1为左孩子
break;
case ',':
k = 2; //2为右孩子
break;
case ')':
top--; //根结点出栈
break;
default:
p = (bitree)malloc(sizeof(bitnode));
p->data = ch;
p->left = p->right = NULL;

switch (k)
{
case 1:
stack[top]->left = p; //根结点的左孩子
break;
case 2:
stack[top]->right = p; //根结点的右孩子
break;
default: // k 初始化为0
b = p; //树为空时
break;
}
}
}
}

1. 括号表示法输出该树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//----------------------------------------------------
// 1,括号表示法输出该树。
void PrinTree(bitree b){
if (b){
cout << b->data; //访问根结点
if (b->left != NULL || b->right != NULL){
cout << "("; // 先输出左括号
PrinTree(b->left); //递归处理左子树
if (b->right != NULL) //不判断直接输出会导致输出结果不符
cout << ",";
PrinTree(b->right); //递归处理右子树
cout << ")"; //输出右括号
}
}
}

2. 输入一个结点的值,输出该结点的左,右孩子的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//----------------------------------------------------
// 2,输入一个结点的值,输出该结点的左,右孩子的值。(要能测试错误数据)
bool getValue(bitree b, ElementType value){
if (b == NULL)//找不到就false
return false;
if (b->data == value){//找到输出
if (b->left)
cout << "左孩子结点:" << b->left->data;
else
cout << " 无左孩子结点";
if (b->right)
cout << " 右孩子结点:" << b->right->data;
else
cout << " 无右孩子结点";
cout << "\n";
return true;//标记找到了
}
//如果找到了就不用再递归了。而且继续递归会导致最后可能return false
if(getValue(b->left, value))return true;
if(getValue(b->right, value))return true;
}

3. 输出该二叉树的高度

1
2
3
4
5
6
//----------------------------------------------------
//3,输出该二叉树的高度。
int getDeep(bitree b){
if(b==NULL)return 0;
return max(getDeep(b->left),getDeep(b->right))+1;//左子树右子树哪边深
}

4. 输出该二叉树结点的个数

1
2
3
4
5
6
//----------------------------------------------------
// 4,输出该二叉树结点的个数。
int getNums(bitree b){
if(b==NULL)return 0;
return getNums(b->left)+getNums(b->right)+1;//左子树+右子树+1
}

5. 输出该二叉树双分支结点的个数

1
2
3
4
5
6
7
8
9
//----------------------------------------------------
// 5,输出该二叉树双分支结点的个数。
int get2BranchNums(bitree b){
if (b == NULL||(b->left==NULL&&b->right==NULL))//由于是双分支结点,左右儿子均不能为NULL
return 0;
if(b->left&&b->right)//是双分支结点
return 1+get2BranchNums(b->left)+get2BranchNums(b->right);//继续递归
return get2BranchNums(b->left)+get2BranchNums(b->right);//递归
}

6. 输出该二叉树单分支结点的个数

1
2
3
4
5
6
7
8
9
//----------------------------------------------------
// 6,输出该二叉树单分支结点的个数。
int get1BranchNums(bitree b){
if (b == NULL||(b->left==NULL&&b->right==NULL))//题目要求是单分治结点
return 0;
if((b->left||b->right)&&!(b->left&&b->right))//找到了
return 1+get1BranchNums(b->left)+get1BranchNums(b->right);
return get1BranchNums(b->left)+get1BranchNums(b->right);
}

7. 输出该二叉树叶子结点的个数

1
2
3
4
5
6
7
//----------------------------------------------------
// 7,输出该二叉树叶子结点的个数。
int getLeafNodes(bitree b){
if(b==NULL)return 0;
if(b->right==NULL&&b->left==NULL)return 1;//叶子节点没有孩子
return getLeafNodes(b->left)+getLeafNodes(b->right);//左子树叶子结点个数+右子树叶子节点个数
}

8. 输出该二叉树的宽度(宽度为每层结点数的最大值)

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
//----------------------------------------------------
// 8,输出该二叉树的宽度。(宽度为每层结点数的最大值)
int getWidth(bitree b){//需要用队列
int tmpWidth=0,maxWidth=1;
if(b==NULL)return 0;
queue<bitnode*> q;
q.push(b);//入队
while(q.size()){
tmpWidth = q.size();
//若每一层的宽度大于maxWidth,则重新赋值
maxWidth = max(tmpWidth,maxWidth);//更新maxWidth
//注意这里循环的次数是width,出队的仅仅是每一层的元素
for (int i = 0; i < tmpWidth; i++) {
bitnode *nodeTemp = q.front();
q.pop();
//左右子树不为空则入队
if (nodeTemp->left != NULL) {
q.push(nodeTemp->left);
}
if(nodeTemp->right != NULL) {
q.push(nodeTemp->right);
}
}
}
return maxWidth;//返回求得的最大宽度
}

9. 任意给定该二叉树的两个结点,输出它们的最近的公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//----------------------------------------------------
// 9,任意给定该二叉树的两个结点,输出它们的最近的公共祖先。
bitnode* findLCA(bitree root, ElementType n1, ElementType n2){
if (root == NULL) return NULL;
// 此处默认输入数据合法!!!
if (root->data == n1 || root->data == n2)
return root;
//递归寻找
bitnode* left_lca = findLCA(root->left, n1, n2);
bitnode* right_lca = findLCA(root->right, n1, n2);
// 如果两个结果都非NULL ,则两个点分别在左右儿子树上
if (left_lca && right_lca) return root;
// 否则检查左子树或右子树是否为最近公共祖先
return (left_lca != NULL)? left_lca: right_lca;
}

10. 销毁该二叉树

1
2
3
4
5
6
7
8
9
10
11
//----------------------------------------------------
//10,销毁该二叉树
bitree FreeTree(bitree b){
if (b != NULL){
FreeTree(b->left); //递归释放左子树
FreeTree(b->right); //递归释放右子树
free(b); //释放根结点
b = NULL; //释放指向根结点的指针
}
return b; //return NULL;
}
  1. 主函数
    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
    int main(){
    // char str[] = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    char str[] = "A(B(D(,G),),C(E,F))";
    bitree root = NULL; //不要忘记初始化
    ElementType tmp,tmp1,tmp2;
    int t1,t2;
    CreateTree(root, str);

    cout << "字符串:" << str << "\n";
    cout << "1,括号表示法输出该树:";
    PrinTree(root);
    cout << "\n";

    cout << "2,输入一个结点的值,输出该结点的左,右孩子的值\n";
    cin >> tmp;
    if (!getValue(root, tmp))
    cout << "查找失败!\n";
    cout<<"3,输出该二叉树的高度: ";
    cout<<getDeep(root)<<"\n";

    cout<<"4,输出该二叉树结点的个数: ";
    cout<<getNums(root)<<"\n";

    cout<<"5,输出该二叉树双分支结点的个数: ";
    cout<<get2BranchNums(root)<<"\n";

    cout<<"6,输出该二叉树单分支结点的个数: ";
    cout<<get1BranchNums(root)<<"\n";

    cout<<"7,输出该二叉树叶子结点的个数: ";
    cout<<getLeafNodes(root)<<"\n";

    cout<<"8,输出该二叉树的宽度: ";
    cout<<getWidth(root)<<"\n";

    cout<<"9,给定该二叉树的两个结点,输出它们的最近的公共祖先: \n";
    cout<<"请输入您所需要查找的两个结点:";
    cin>>tmp1>>tmp2;
    bitnode* tmpnode = findLCA(root,tmp1,tmp2);
    if(tmpnode==NULL){
    cout<<"结点: "<<tmp1<<" 和 "<<tmp2<<" 没有公共结点\n";
    }else{
    cout<<"结点: "<<tmp1<<" 和 "<<tmp2<<" 的最近公共结点为:"<<tmpnode->data<<"\n";
    }

    cout<<"10,销毁该二叉树\n";
    root = FreeTree(root);
    if (root == NULL)
    cout << "二叉树销毁成功" << "\n";

    return 0;
    }

    完整代码

    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
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    #include <bits/stdc++.h>
    using namespace std;
    const int MaxSize = 50;

    typedef char ElementType; //typedef用来给数据类型char起别名(ElementType)
    typedef struct bitnode
    {
    ElementType data;
    struct bitnode *left, *right;
    } bitnode, *bitree; //bitree为指向bitnode这种自定义数据的指针

    //----------------------------------------------------
    //根据嵌套括号表示法的字符串生成链式存储的二叉树
    void CreateTree(bitree &b, char str[]){
    char ch;
    bitree stack[MaxSize], p; //stack[MaxSize]为指针数组,其每一个元素都为指向bitnode这种结构的指针,p为临时指针
    int top = -1, k = 0, j = 0; //top为栈顶指针、k决定谁是左、右孩子、j为str指针

    while ((ch = str[j++]) != '\0'){
    switch (ch)
    {
    case '(':
    top++;
    stack[top] = p; //根结点入栈
    k = 1; //1为左孩子
    break;
    case ',':
    k = 2; //2为右孩子
    break;
    case ')':
    top--; //根结点出栈
    break;
    default:
    p = (bitree)malloc(sizeof(bitnode));
    p->data = ch;
    p->left = p->right = NULL;

    switch (k)
    {
    case 1:
    stack[top]->left = p; //根结点的左孩子
    break;
    case 2:
    stack[top]->right = p; //根结点的右孩子
    break;
    default: // k 初始化为0
    b = p; //树为空时
    break;
    }
    }
    }
    }

    //----------------------------------------------------
    // 1,括号表示法输出该树。
    void PrinTree(bitree b){
    if (b){
    cout << b->data; //访问根结点
    if (b->left != NULL || b->right != NULL){
    cout << "("; // 先输出左括号
    PrinTree(b->left); //递归处理左子树
    if (b->right != NULL) //不判断直接输出会导致输出结果不符
    cout << ",";
    PrinTree(b->right); //递归处理右子树
    cout << ")"; //输出右括号
    }
    }
    }

    //----------------------------------------------------
    // 2,输入一个结点的值,输出该结点的左,右孩子的值。(要能测试错误数据)
    bool getValue(bitree b, ElementType value){
    if (b == NULL)//找不到就false
    return false;
    if (b->data == value){//找到输出
    if (b->left)
    cout << "左孩子结点:" << b->left->data;
    else
    cout << " 无左孩子结点";
    if (b->right)
    cout << " 右孩子结点:" << b->right->data;
    else
    cout << " 无右孩子结点";
    cout << "\n";
    return true;//标记找到了
    }
    //如果找到了就不用再递归了。而且继续递归会导致最后可能return false
    if(getValue(b->left, value))return true;
    if(getValue(b->right, value))return true;
    }
    //----------------------------------------------------
    //3,输出该二叉树的高度。
    int getDeep(bitree b){
    if(b==NULL)return 0;
    return max(getDeep(b->left),getDeep(b->right))+1;//左子树右子树哪边深
    }
    //----------------------------------------------------
    // 4,输出该二叉树结点的个数。
    int getNums(bitree b){
    if(b==NULL)return 0;
    return getNums(b->left)+getNums(b->right)+1;//左子树+右子树+1
    }
    //----------------------------------------------------
    // 5,输出该二叉树双分支结点的个数。
    int get2BranchNums(bitree b){
    if (b == NULL||(b->left==NULL&&b->right==NULL))//由于是双分支结点,左右儿子均不能为NULL
    return 0;
    if(b->left&&b->right)//是双分支结点
    return 1+get2BranchNums(b->left)+get2BranchNums(b->right);//继续递归
    return get2BranchNums(b->left)+get2BranchNums(b->right);//递归
    }
    //----------------------------------------------------
    // 6,输出该二叉树单分支结点的个数。
    int get1BranchNums(bitree b){
    if (b == NULL||(b->left==NULL&&b->right==NULL))//题目要求是单分治结点
    return 0;
    if((b->left||b->right)&&!(b->left&&b->right))//找到了
    return 1+get1BranchNums(b->left)+get1BranchNums(b->right);
    return get1BranchNums(b->left)+get1BranchNums(b->right);
    }
    //----------------------------------------------------
    // 7,输出该二叉树叶子结点的个数。
    int getLeafNodes(bitree b){
    if(b==NULL)return 0;
    if(b->right==NULL&&b->left==NULL)return 1;//叶子节点没有孩子
    return getLeafNodes(b->left)+getLeafNodes(b->right);//左子树叶子结点个数+右子树叶子节点个数
    }
    //----------------------------------------------------
    // 8,输出该二叉树的宽度。(宽度为每层结点数的最大值)
    int getWidth(bitree b){//需要用队列
    int tmpWidth=0,maxWidth=1;
    if(b==NULL)return 0;
    queue<bitnode*> q;
    q.push(b);//入队
    while(q.size()){
    tmpWidth = q.size();
    //若每一层的宽度大于maxWidth,则重新赋值
    maxWidth = max(tmpWidth,maxWidth);//更新maxWidth
    //注意这里循环的次数是width,出队的仅仅是每一层的元素
    for (int i = 0; i < tmpWidth; i++) {
    bitnode *nodeTemp = q.front();
    q.pop();
    //左右子树不为空则入队
    if (nodeTemp->left != NULL) {
    q.push(nodeTemp->left);
    }
    if(nodeTemp->right != NULL) {
    q.push(nodeTemp->right);
    }
    }
    }
    return maxWidth;//返回求得的最大宽度
    }
    //----------------------------------------------------
    // 9,任意给定该二叉树的两个结点,输出它们的最近的公共祖先。
    bitnode* findLCA(bitree root, ElementType n1, ElementType n2){
    if (root == NULL) return NULL;
    // 此处默认输入数据合法!!!
    if (root->data == n1 || root->data == n2)
    return root;
    //递归寻找
    bitnode* left_lca = findLCA(root->left, n1, n2);
    bitnode* right_lca = findLCA(root->right, n1, n2);
    // 如果两个结果都非NULL ,则两个点分别在左右儿子树上
    if (left_lca && right_lca) return root;
    // 否则检查左子树或右子树是否为最近公共祖先
    return (left_lca != NULL)? left_lca: right_lca;
    }

    //----------------------------------------------------
    //10,销毁该二叉树
    bitree FreeTree(bitree b){
    if (b != NULL){
    FreeTree(b->left); //递归释放左子树
    FreeTree(b->right); //递归释放右子树
    free(b); //释放根结点
    b = NULL; //释放指向根结点的指针
    }
    return b; //return NULL;
    }

    int main(){
    // char str[] = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    char str[] = "A(B(D(,G),),C(E,F))";
    bitree root = NULL; //不要忘记初始化
    ElementType tmp,tmp1,tmp2;
    int t1,t2;
    CreateTree(root, str);

    cout << "字符串:" << str << "\n";
    cout << "1,括号表示法输出该树:";
    PrinTree(root);
    cout << "\n";

    cout << "2,输入一个结点的值,输出该结点的左,右孩子的值\n";
    cin >> tmp;
    if (!getValue(root, tmp))
    cout << "查找失败!\n";
    cout<<"3,输出该二叉树的高度: ";
    cout<<getDeep(root)<<"\n";

    cout<<"4,输出该二叉树结点的个数: ";
    cout<<getNums(root)<<"\n";

    cout<<"5,输出该二叉树双分支结点的个数: ";
    cout<<get2BranchNums(root)<<"\n";

    cout<<"6,输出该二叉树单分支结点的个数: ";
    cout<<get1BranchNums(root)<<"\n";

    cout<<"7,输出该二叉树叶子结点的个数: ";
    cout<<getLeafNodes(root)<<"\n";

    cout<<"8,输出该二叉树的宽度: ";
    cout<<getWidth(root)<<"\n";

    cout<<"9,给定该二叉树的两个结点,输出它们的最近的公共祖先: \n";
    cout<<"请输入您所需要查找的两个结点:";
    cin>>tmp1>>tmp2;
    bitnode* tmpnode = findLCA(root,tmp1,tmp2);
    if(tmpnode==NULL){
    cout<<"结点: "<<tmp1<<" 和 "<<tmp2<<" 没有公共结点\n";
    }else{
    cout<<"结点: "<<tmp1<<" 和 "<<tmp2<<" 的最近公共结点为:"<<tmpnode->data<<"\n";
    }

    cout<<"10,销毁该二叉树\n";
    root = FreeTree(root);
    if (root == NULL)
    cout << "二叉树销毁成功" << "\n";

    return 0;
    }