数据结构(C++)——二叉树的基本操作——多种遍历，计算各种节点数，交换子树

一个具有操作菜单的二叉树基本操作。

 功能包括：

                1.通过先序法创建二叉树；

                2.然后实现先序、中序、后序和按层遍历二叉树；

                3.实现求二 叉树的总结点数、叶子节点树、单、双分支节点个数；

                4.实现求二 叉树的深度；

                5.交换二叉树的左右子树等。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define TElemType char
4.  
    
5.  
   typedef struct BiTNode
6.  
   {
7.  
   TElemType data;
8.  
   struct BiTNode *lchild,*rchild;
9.  
   } BiTNode,*BiTree;
10.  
     
11.  
    BiTree p;//全局变量，用于函数中的操作
12.  
     
13.  
    void CreateBiTree(BiTree &T)
14.  
    {
15.  
    //先序遍历的顺序建立二叉树
16.  
     
17.  
    char ch;//存入的元素
18.  
    cin>>ch;
19.  
    if(ch=='#') T=NULL;
20.  
    else
21.  
    {
22.  
    T=new BiTNode;
23.  
    T->data=ch;
24.  
    CreateBiTree(T->lchild);
25.  
    CreateBiTree(T->rchild);
26.  
    }
27.  
    }
28.  
     
29.  
    void PreOrderTraverse(BiTree T)
30.  
    {
31.  
    //先序遍历二叉树
32.  
     
33.  
    if(T)
34.  
    {
35.  
    cout<<T->data<<" ";
36.  
    PreOrderTraverse(T->lchild);
37.  
    PreOrderTraverse(T->rchild);
38.  
    }
39.  
    }
40.  
     
41.  
    void InOrderTraverse(BiTree T)
42.  
    {
43.  
    //中序遍历二叉树
44.  
     
45.  
    if(T)
46.  
    {
47.  
    InOrderTraverse(T->lchild);
48.  
    cout<<T->data<<" ";
49.  
    InOrderTraverse(T->rchild);
50.  
    }
51.  
    }
52.  
     
53.  
    void PostOrderTraverse(BiTree T)
54.  
    {
55.  
    //后序遍历二叉树
56.  
     
57.  
    if(T)
58.  
    {
59.  
    PostOrderTraverse(T->lchild);
60.  
    PostOrderTraverse(T->rchild);
61.  
    cout<<T->data<<" ";
62.  
    }
63.  
    }
64.  
     
65.  
    void LevelOrderTraverse(BiTree T)
66.  
    {
67.  
    //按层遍历
68.  
     
69.  
    queue<BiTree> Q;//按层遍历中使用的队列，需加队列头文件
70.  
    if(T)
71.  
    {
72.  
    Q.push(T);//先将根存入队列
73.  
     
74.  
    while(!Q.empty())
75.  
    {
76.  
    p=Q.front();
77.  
    cout<<p->data<<" ";
78.  
    Q.pop();
79.  
    if(p->lchild)
80.  
    Q.push(p->lchild);
81.  
    if(p->rchild)
82.  
    Q.push(p->rchild);
83.  
    }
84.  
    }
85.  
    }
86.  
     
87.  
    void ChangeChild(BiTree &T) //交换左右子树
88.  
    {
89.  
     
90.  
    if(T->lchild&&T->rchild)
91.  
    {
92.  
    p=T->lchild;
93.  
    T->lchild=T->rchild;
94.  
    T->rchild=p;
95.  
    ChangeChild(T->lchild);
96.  
    ChangeChild(T->rchild);
97.  
    }
98.  
    else if(T->lchild)
99.  
    {
100.  
     T->rchild=T->lchild;
101.  
     T->lchild=NULL;
102.  
     ChangeChild(T->rchild);
103.  
     }
104.  
     else if(T->rchild)
105.  
     {
106.  
     T->lchild=T->rchild;
107.  
     T->rchild=NULL;
108.  
     ChangeChild(T->lchild);
109.  
     }
110.  
     }
111.  
      
112.  
     int Depth(BiTree T)
113.  
     {
114.  
     //计算二叉树的深度
115.  
      
116.  
     if(!T)
117.  
     return 0;
118.  
     else
119.  
     return max(Depth(T->lchild),Depth(T->rchild)) 1;
120.  
     }
121.  
      
122.  
     int NodeCount(BiTree T)
123.  
     {
124.  
     //计算二叉树节点数
125.  
      
126.  
     if(!T)
127.  
     return 0;
128.  
     else
129.  
     return NodeCount(T->lchild) NodeCount(T->rchild) 1;
130.  
     }
131.  
      
132.  
     int LeafCount(BiTree T)
133.  
     {
134.  
     //计算二叉树叶子节点数
135.  
      
136.  
     if(T->lchild&&T->rchild)
137.  
     return LeafCount(T->lchild) LeafCount(T->rchild);
138.  
     else if(T->lchild)
139.  
     {
140.  
     return LeafCount(T->lchild);
141.  
     }
142.  
     else if(T->rchild)
143.  
     {
144.  
     return LeafCount(T->rchild);
145.  
     }
146.  
     else
147.  
     return 1;
148.  
     }
149.  
      
150.  
     int SingleCount(BiTree T)
151.  
     {
152.  
     //计算单分支节点个数
153.  
      
154.  
     if(T->lchild&&T->rchild)
155.  
     return SingleCount(T->lchild) SingleCount(T->rchild);
156.  
     else if(T->lchild)
157.  
     {
158.  
     return SingleCount(T->lchild) 1;
159.  
     }
160.  
     else if(T->rchild)
161.  
     {
162.  
     return SingleCount(T->rchild) 1;
163.  
     }
164.  
     else
165.  
     return 0;
166.  
     }
167.  
      
168.  
     int BothCount(BiTree T)
169.  
     {
170.  
     //计算双分支节点个数
171.  
      
172.  
     if(T->lchild&&T->rchild)
173.  
     return BothCount(T->lchild) BothCount(T->rchild) 1;
174.  
     else if(T->lchild)
175.  
     {
176.  
     return BothCount(T->lchild);
177.  
     }
178.  
     else if(T->rchild)
179.  
     {
180.  
     return BothCount(T->rchild);
181.  
     }
182.  
     else
183.  
     return 0;
184.  
     }
185.  
      
186.  
     int main()
187.  
     {
188.  
     BiTree T;
189.  
     while(true)
190.  
     {
191.  
     system("cls");
192.  
     cout<<"--二叉树的基本操作--"<<endl;
193.  
     cout<<" 1.先序创建二叉树"<<endl;
194.  
     cout<<" 2.先序遍历二叉树"<<endl;
195.  
     cout<<" 3.中序遍历二叉树"<<endl;
196.  
     cout<<" 4.后序遍历二叉树"<<endl;
197.  
     cout<<" 5.按层遍历二叉树"<<endl;
198.  
     cout<<" 6.二叉树总节点数"<<endl;
199.  
     cout<<" 7.叶子节点数"<<endl;
200.  
     cout<<" 8.单分支节点个数"<<endl;
201.  
     cout<<" 9.双分支节点个数"<<endl;
202.  
     cout<<" a.二叉树深度"<<endl;
203.  
     cout<<" b.交换左右子树"<<endl;
204.  
     cout<<" c.退出"<<endl;
205.  
     cout<<"请输入选择：";
206.  
     char choice;
207.  
     cin>>choice;
208.  
     switch(choice)
209.  
     {
210.  
     case '1':
211.  
     CreateBiTree(T);
212.  
     break;
213.  
     case '2':
214.  
     PreOrderTraverse(T);
215.  
     break;
216.  
     case '3':
217.  
     InOrderTraverse(T);
218.  
     break;
219.  
     case '4':
220.  
     PostOrderTraverse(T);
221.  
     break;
222.  
     case '5':
223.  
     LevelOrderTraverse(T);
224.  
     break;
225.  
     case '6':
226.  
     cout<<NodeCount(T);
227.  
     break;
228.  
     case '7':
229.  
     cout<<LeafCount(T);
230.  
     break;
231.  
     case '8':
232.  
     cout<<SingleCount(T);
233.  
     break;
234.  
     case '9':
235.  
     cout<<BothCount(T);
236.  
     break;
237.  
     case 'a':
238.  
     cout<<Depth(T);
239.  
     break;
240.  
     case 'b':
241.  
     ChangeChild(T);
242.  
     break;
243.  
     case 'c':
244.  
     exit(0);
245.  
     default:
246.  
     cout<<"请输入正确选项!"<<endl;
247.  
     break;
248.  
     }
249.  
     cout<<endl;
250.  
     system("pause");
251.  
     }
252.  
      
253.  
     }

这篇好文章是转载于：学新通技术网