题解——二叉树的基本操作_二叉树输出某点的左右孩子值

题解——二叉树的基本操作

题目链接：传送门

描述

采用括号表示法的字符串创建二叉链表表示的二叉树，实现二叉树的基本运算，如下:

(1)用括号表示法输出二叉树；

(2)输出节点的左、右孩子节点值；

(3)输出二叉树的深度；

(4)输出二叉树的宽度；

(5)输出二叉树的节点个数；

(6)输出二叉树的叶子节点个数；

(7)释放二叉树。

输入

两行数据：
第一行：用括号表示法表示二叉树的字符串；
第二行：要求输出的是括号表示法里的第几个节点的左、右孩子节点值；

输出

按照程序要求输出。
其中：

• 输出节点的左、右孩子节点值；
• 若无，则输出：no leftchild no rightchild

样例输入

A(B(D,E(G,)),C(,F))
2
1
2

样例输出

A(B(D,E(G)),C(,F))
D E
4
3
7
3
1
2
3
4
5
6

提示

参考实验题7.1

题解

基本操作（1）（3）（4）（5）（6）（7）可以在之前的博客里找到解析：数据结构与算法——二叉树

核心难点或许是（2）

输出节点的左、右孩子节点值；

输入的时候，第一行我们输入的是括号表达式，第二行还输入了一个数n，这个数就是在（2）里起作用——输出括号表达式中第n个结点的左右孩子

所以我们要做的就是：

1. 找到第n个结点
2. 输出它的左右孩子

我们可以在创建树的同时，也就是在CreateTree函数里面，做一个计数器，记录当前进入树的结点是第几个进入树的结点，如果当前的结点就是第n个，那我们把它保存起来。最后，再输出它。

按上面的思路，我们：

• 设定一个全局变量n，以确保在主函数输入n后，可以在其他函数里直接访问n的值；
• 定义一个BTNode型的指针变量res，用来存储找到的第n个结点
• 修改CreateTree函数，添加计数器和判断条件：

int n,num=0; //num是计数器，把它也定义为全局变量的好处是，它顺便记录了树的结点个数，这样（5）就可以直接输出num了

BTNode *res=new BTNode(); //用于记录第n个结点

void CreateBTree(BTNode *&bt,char *str){
    stack<BTNode*> st;
    bt=NULL;
    int k;
    BTNode *p=NULL;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        if(str[i]=='('){
            k=1;
            st.push(p);
            continue;
        }
        else if(str[i]==')'){
            st.pop();
            continue;
        }
        else if(str[i]==','){
            k=2;
            continue;
        }
        else{
            p=new BTNode();
            p->data=str[i];
            p->lc=p->rc=NULL;
            if(bt==NULL){
                bt=p;
                num++; //计数器记录
                if(num==n) //判断
                    res=p; //保存
            }
            else{
                if(k==1)
                    st.top()->lc=p;
                else if(k==2)
                    st.top()->rc=p;
                num++; //计数器记录
                if(num==n) //判断
                    res=p; //保存
            }
        }
    }
}
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

需要注意的是，为什么一定要保存起来，而不是找到就输出？

因为刚找到第n个结点的时候，它刚进树，还没有孩子，所以这时候你就算要输出，也没啥好输出的，只能把它存下来，等它有孩子了你再输出。它什么时候有孩子？全创建完了就有孩子了。

完整代码参考：
不可以直接抄啊！

#include <iostream>
#include <stack>
#include <cstring>
#define ElemType char
using namespace std;
struct BTNode{ //"二叉树点"
    ElemType data; //用define把char定义为ElemType
    BTNode *lc,*rc; //lc是"left child"左孩子，rc是"right child"右孩子
};

int n,num=0; //第n个结点，num是计数器
BTNode *res=new BTNode(); //用于记录第n个结点
void CreateBTree(BTNode *&bt,char *str){
    stack<BTNode*> st; //STL的栈，类型为BTNode的指针
    bt=NULL; //根结点初始化为空
    int k; //用k记录左右儿子，1为左，2为右
    BTNode *p=NULL; //用p存储读取到的字符
    int len=strlen(str); //字符串str的长度为len
    for(int i=0;i<len;i++){
        if(str[i]=='('){
            k=1; //k计为左儿子
            st.push(p); //入栈
            continue;
        }
        else if(str[i]==')'){
            st.pop(); //出栈
            continue; //继续往后看
        }
        else if(str[i]==','){
            k=2; //k计为右儿子
            continue;
        }
        else{
            p=new BTNode(); //为p申请空间
            p->data=str[i]; //赋值
            p->lc=p->rc=NULL;
            if(bt==NULL){ //如果bt为空，代表p为最开始的根结点
                bt=p;
                num++;
                if(num==n)
                    res=p;
            }
            else{
                if(k==1) //之前读取到左括号，说明p是左孩子
                    st.top()->lc=p;
                else if(k==2) //之前读取到逗号，说明p是右孩子
                    st.top()->rc=p;
                num++;
                if(num==n)
                    res=p;
            }
        }
    }
}

void DispBTree(BTNode *bt){ //输出
    if(bt!=NULL){
        cout<<bt->data;
        if(bt->lc!=NULL|| bt->rc != NULL)
        {
            cout<<'(';
            DispBTree(bt->lc);
            if(bt->rc != NULL)
                cout<<',';
            DispBTree(bt->rc);
            cout<<')';
        }
    }
}

int BTHeight(BTNode *bt){ //求高度
    int lch, rch; //左子树深度lch和右子树深度rch
    if(bt==NULL) return 0; //如果是空的，就说明没有长度，返回0
    else{
        lch=BTHeight(bt->lc); //左子树的深度
        rch=BTHeight(bt->rc); //右子树的深度
        if(lch>rch)return lch+1;
        else return rch+1;
    }
}

int Count[10010];
void WidConut(BTNode *bt, int dep){  //宽度
    if(bt==NULL)
        return ;
    Count[dep]++;
    dep++;
    WidConut(bt->lc,dep);
    WidConut(bt->rc,dep);
}

int NodeCount(BTNode *bt){ //求结点个数
    int num1,num2;
    if(bt==NULL)
        return 0;
    else{
        num1=NodeCount(bt->lc); //左子树的结点个数
        num2=NodeCount(bt->rc); //右子树的结点个数
        return num1+num2+1;
    }
}

int LeafCount(BTNode *bt){ //求叶子结点个数
    int num1,num2;
    if(bt==NULL)
        return 0;
    else if(bt->lc==NULL&&bt->rc==NULL)
        return 1;
    else{
        num1=LeafCount(bt->lc); //左子树的叶子结点
        num2=LeafCount(bt->rc); //右子树的叶子结点
        return num1+num2;
    }
}

void DestoryBTree(BTNode *&bt){ //释放
    if(bt!=NULL){ //bt只要不是NULL，就把它的孩子叫来
        DestoryBTree(bt->lc); //让它叫左孩子
        DestoryBTree(bt->rc); //让它叫右孩子
        delete bt; //嫩死它
    }
}

int main()
{
    BTNode *bt;
    char str[1000];
    cin>>str;
    cin>>n;
    CreateBTree(bt,str);
    DispBTree(bt);
    cout<<endl;
    if(res->lc!=NULL)
        cout<<res->lc->data<<" ";
    else cout<<"no leftchild ";
    if(res->rc!=NULL)
        cout<<res->rc->data<<endl;
    else cout<<"no rightchild"<<endl;
    cout<<BTHeight(bt)<<endl;
    WidConut(bt,0);
    
    int wid=0;
    for(int i=0;Count[i]!=0;i++)
        wid=max(wid,Count[i]);
    cout<<wid<<endl;
    cout<<NodeCount(bt)<<endl;
    //cout<<"num="<<num<<endl; //"输出长度"可以直接用num，去掉注视符号试试
    cout<<LeafCount(bt);
    DestoryBTree(bt);
    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