距离上次更新已经过去 660 天,文章内容可能与实际操作有一定出入

遍历二叉树中进行的一些操作

  • 创建二叉树
  • 先序遍历二叉树
  • 计算树高
  • 计算树叶数
  • 计算结点数
  • 计算分支点个数
  • 二叉树拷贝
  • 二叉树左右子树交换

操作使用C++版的数据结构完成

cpp
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
234
235
236
237
238
239
240
241
242
243
244
245
/*****************************  
 @author: YuZhangWang  
 @date: 2022/8/4 23:37:36 
 @link: https://yuzhang.wang
******************************/  
  
#include<iostream>  
  
using namespace std;  
  
typedef struct bitnode  
{  
    char data;  
    bitnode *lchild, *rchild;  
} bitnode;  
  
class bitt  
{  
    bitnode *bt;  
  
    void create(bitnode *&t);//创建二叉树  
    void preorder(bitnode *t);//先序历遍  
    int high(bitnode *t);//计算树高  
    int countleaf(bitnode *t);//计算树叶数  
    int countnode(bitnode *t); //计算结点数  
    int countpartnode(bitnode *t);//计算分支点个数  
    void copy(bitnode *&t, bitnode *&s);//二叉树拷贝  
    void changebit(bitnode *&t);//二叉树左右子树交换  
public:  
    void createtree();//创建二叉树  
    void preordertree();//先序历遍  
    int hightree();//计算树高  
    int countleaftree();//计算树叶数  
    int countnodetree();//计算结点数  
    int countpartnodetree();//计算分支点个数  
    void copytree();//二叉树拷贝  
    void changebittree();//二叉树左右子树交换  
};  
  
void bitt::create(bitnode *&t)  
{  
    char ch;  
    cin >> ch;  
    if (ch == '.')  
    {  
        t = NULL;  
    }  
    else  
    {  
        t = new bitnode;  
        t->data = ch;  
        create(t->lchild);  
        create(t->rchild);  
    }  
}  
  
void bitt::createtree()  
{  
    bitnode *t;  
    create(t);  
    bt = t;  
}  
  
void bitt::preorder(bitnode *t)  
{  
    if (t)  
    {  
        cout << t->data;  
        preorder(t->lchild);  
        preorder(t->rchild);  
    }  
}  
  
void bitt::preordertree()  
{  
    bitnode *t = bt;  
    preorder(t);  
}  
  
int bitt::high(bitnode *t)  
{  
    if (t == NULL)  
    {  
        return 0;  
    }  
    else  
    {  
        int m = 1 + high(t->lchild);  
        int n = 1 + high(t->rchild);  
        if (m >= n)  
        {  
            return m;  
        }  
        else  
        {  
            return n;  
        }  
    }  
}  
  
int bitt::hightree()  
{  
    bitnode *t = bt;  
    return high(t);  
}  
  
int bitt::countleaf(bitnode *t)  
{  
    if (t == NULL)  
    {  
        return 0;  
    }  
    else  
    {  
        int m = countleaf(t->lchild);  
        int n = countleaf(t->rchild);  
        if (m + n == 0)  
        {  
            return 1;  
        }  
        else  
        {  
            return m + n;  
        }  
    }  
}  
  
int bitt::countleaftree()  
{  
    bitnode *t = bt;  
    return countleaf(t);  
}  
  
int bitt::countnode(bitnode *t)  
{  
    if (t)  
    {  
        int m = countnode(t->lchild);  
        int n = countnode(t->rchild);  
        return 1 + m + n;  
    }  
    else  
    {  
        return 0;  
    }  
}  
  
int bitt::countnodetree()  
{  
    bitnode *t = bt;  
    return countnode(t);  
}  
  
int bitt::countpartnode(bitnode *t)  
{  
    if (t && (t->lchild || t->rchild))  
    {  
        int m = countpartnode(t->lchild);  
        int n = countpartnode(t->rchild);  
        return 1 + m + n;  
    }  
    else  
    {  
        return 0;  
    }  
}  
  
int bitt::countpartnodetree()  
{  
    bitnode *t = bt;  
    return countpartnode(t);  
}  
  
void bitt::copy(bitnode *&t, bitnode *&s)  
{  
    if (t == NULL)  
    {  
        s = NULL;  
    }  
    else  
    {  
        s = t;  
        copy(t->lchild, s->lchild);  
        copy(t->rchild, s->rchild);  
    }  
}  
  
void bitt::copytree()  
{  
    bitnode *t = bt;  
    bitnode *s;  
    copy(t, s);  
    if (s)  
    {  
        cout << s->data;  
        preorder(s->lchild);  
        preorder(s->rchild);  
    }  
}  
  
void bitt::changebit(bitnode *&t)  
{  
    bitnode *temp = new bitnode;  
    if (t)  
    {  
        temp = t->lchild;  
        t->lchild = t->rchild;  
        t->rchild = temp;  
        changebit(t->lchild);  
        changebit(t->rchild);  
    }  
}  
  
void bitt::changebittree()  
{  
    bitnode *t = bt;  
    changebit(t);  
    bt = t;  
}  
  
int main()  
{  
    bitt tt;  
    cout << "请输入需要形成的二叉树:" << endl;  
    tt.createtree();  
    cout << "该二叉树先序历遍结果为:" << endl;  
    tt.preordertree();  
    cout << endl;  
    cout << "该二叉树树高为:" << endl;  
    cout << tt.hightree() << endl;  
    cout << "该二叉树树叶数为:" << endl;  
    cout << tt.countleaftree() << endl;  
    cout << "该二叉树结点数为:" << endl;  
    cout << tt.countnodetree() << endl;  
    cout << "该二叉树分支点数为:" << endl;  
    cout << tt.countpartnodetree() << endl;  
    cout << "该二叉树拷贝结果为:" << endl;  
    tt.copytree();  
    cout << endl;  
    cout << "该二叉树左右子树交换结果为:" << endl;  
    tt.changebittree();  
    tt.preordertree();  
    cout << endl;  
    return 0;  
}