变量	类型	说明
Node、BiTNode	结构体	二叉树结点的结构体
*BiTree	二叉树结点指针	二叉树结点的指针
data	可变（由宏定义TElemType确定，示例中为char）	二叉树结点中的数据域
*lchild	二叉树结点指针	结点的左孩子
*rchild	二叉树结点指针	结点的右孩子
TElemType	宏定义	二叉树节点数据域的类型

2.2程序结构的描述

程序主要包含Noah_BiTree.h头文件和main.cpp主文件，其中Noah_BiTree.h是二叉链表数据结构的实现代码头文件，N，main.cpp中主要实现菜单和功能界面的交互以及头文件中函数的调用。其具体结构如下图所示。

3.调试分析

调试功能一：Create a binary tree and show the tree structure

创建二叉树并显示树的结构

测试数据选择:

6423####51##7##
124##5##36##7##
#
1234######

问题及解决方法：

无

调试功能二：Create a binary tree and show show the preoeder, inorder, postorder and levelorder

创建一个二叉树，显示前序、中序后序和层次遍历。

测试数据选择:

6423####51##7##
124##5##36##7##
1234######

问题及解决方法：

无

调试功能三：Create a binary tree and calculate the number of nodes, leaves, height and width

创建一个二叉树，计算节点的数量，叶，高度和宽度

测试数据选择:

6423####51##7##
124##5##36##7##
1234######

问题及解决方法：

无

调试功能四：Create a binary tree, copy it, destory the original one and show the new tree

创建一个二叉树，复制它，销毁原来的树，并显示新的树

测试数据选择:

6423####51##7##
124##5##36##7##
1234######

问题及解决方法：

无

4.算法的时空分析

(1) CreateBiTree_withhint(BiTree &T)

时间复杂度：O(n)

空间复杂度：O(n)

(2) preorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(3) inorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(4) postorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(5) levelorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(6) NumofNode (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) BiHight (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) Numofleaves (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) BiWidth (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) CopyBitree (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) DestroyBiTree (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

5.测试结果及分析

测试功能一：Create a binary tree and show the tree structure

测试用例	结果	分析
6423####51##7##		√
124##5##36##7##		√
#		√
1234######		√

调试功能二：Create a binary tree and show show the preoeder, inorder, postorder and levelorder

测试用例	结果	分析
6423####51##7##		√
124##5##36##7##		√
1234######		√

测试功能三：Create a binary tree and calculate the number of nodes, leaves, height and width

测试用例	结果	分析
6423####51##7##		√
124##5##36##7##		√
1234######		√

调试功能四：Create a binary tree, copy it, destory the original one and show the new tree

测试用例	结果	分析
6423####51##7##		√
124##5##36##7##		√
1234######		√

6.实验体会和收获

掌握二叉树的递归特性
掌握二叉树的常用存储结构----二叉链表
掌握二叉树的创建、遍历等基本运算
了解递归函数的执行过程，学会编写递归程序

代码

Noah_BiTree.h


1.	#ifndef __NOAH_BITREE_H__  
2.	#define __NOAH_BITREE_H__  
3.	#include <stdlib.h>  
4.	#include <iostream>  
5.	#include <cstring>  
6.	#include <queue>  
7.	#include <string>  
8.	#include <iostream>  
9.	using namespace std;  
10.	#define TElemType char  
11.	/* 
12.	1.  对于创建的二叉树为空的情况，要能程序要能正常运行并识别。（5分） 
13.	2.  对于空树，其他功能要可以识别、输出相应信息，并且程序不能异常终止。（5分） 
14.	*/  
15.	typedef struct Node  
16.	{  
17.	    TElemType data;  
18.	    struct Node *lchild,*rchild;//左右孩子指针  
19.	}BiTNode,*BiTree;  
20.	  
21.	void CreateBiTree_Preorder(BiTree &T){  
22.	    //使用先序遍历的输入创建一个二叉树，例如6423####51##7##  
23.	    char x;  
24.	    cin>>x;  
25.	    if(x==' '||x=='#'){  
26.	        T = NULL;  
27.	    }  
28.	    else {  
29.	        T = (BiTree)malloc(sizeof(BiTNode));  
30.	        if(x !='#')  
31.	            T->data = (TElemType)x;  
32.	        CreateBiTree_Preorder(T->lchild);  
33.	        CreateBiTree_Preorder(T->rchild);  
34.	    }  
35.	}  
36.	  
37.	void CreateBiTree_withhint(BiTree &T){  
38.	    //向屏幕输出初始化二叉树的提示信息，调用CreateBiTree_Preorder()  
39.	    cout<<"Please input a preorder sequence of a binary tree(example:6423####51##7##):"<<endl;  
40.	    CreateBiTree_Preorder(T);  
41.	    if(T==NULL) cout<<"Input is an empty BiTree."<<endl;  
42.	}  
43.	  
44.	int isBiTreeEmpty(BiTree T){  
45.	    //判断二叉树是否为空，为空返回1，不为空返回0  
46.	    if((T->data == NULL && T->lchild && T->rchild)||T==NULL)  
47.	        return 1;  
48.	    else  
49.	        return 0;  
50.	}  
51.	  
52.	void preorder(BiTree T){  
53.	    //使用先序遍历输出二叉树  
54.	    if(T){  
55.	        cout<<T->data;  
56.	        preorder(T->lchild);  
57.	        preorder(T->rchild);  
58.	    }  
59.	    else  
60.	        return;  
61.	        //cout<<"Empty BiTree."<<endl;  
62.	}  
63.	  
64.	void inorder(BiTree T){  
65.	    //使用中序遍历输出二叉树  
66.	    if(T){  
67.	        inorder(T->lchild);  
68.	        cout<<T->data;  
69.	        inorder(T->rchild);  
70.	    }  
71.	}  
72.	  
73.	void postorder(BiTree T){  
74.	    //使用后序遍历输出二叉树  
75.	    if(T){  
76.	        postorder(T->lchild);  
77.	        postorder(T->rchild);  
78.	        cout<<T->data;  
79.	    }  
80.	}  
81.	  
82.	void leverorder(BiTree T){  
83.	    //使用层次遍历输出二叉树  
84.	    if(T){  
85.	        queue<BiTree> q;  
86.	        q.push(T);  
87.	        while(!q.empty()){//当队列非空时，还有没有遍历的parent结点  
88.	            BiTree temp = q.front();  
89.	            q.pop();  
90.	            cout<<temp->data;  
91.	            if(temp->lchild!=NULL) q.push(temp->lchild);  
92.	            if(temp->rchild!=NULL) q.push(temp->rchild);  
93.	        }  
94.	    }  
95.	}  
96.	  
97.	int NumofNode(BiTree T){  
98.	    //返回二叉树节点数  
99.	    if(!T) return 0;  
100.	    else return 1 + NumofNode(T->lchild) + NumofNode(T->rchild);  
101.	}  
102.	  
103.	int Numofleaves(BiTree T){  
104.	    //返回二叉树叶子数  
105.	    int num = 0;  
106.	    if(!T) return 0;  
107.	    else{  
108.	        if(T->lchild!=NULL) num = num + Numofleaves(T->lchild);  
109.	        if(T->rchild!=NULL) num = num + Numofleaves(T->rchild);  
110.	        if(T->lchild==NULL && T->rchild==NULL) return 1;  
111.	    }  
112.	    return num;  
113.	}  
114.	  
115.	int BiHight(BiTree T){  
116.	    //返回二叉树高度  
117.	    if(!T) return 0;  
118.	    else{  
119.	        int lefthight = BiHight(T->lchild);  
120.	        int righthight = BiHight(T->rchild);  
121.	        return (lefthight>=righthight)?lefthight+1:righthight+1;  
122.	    }  
123.	}  
124.	  
125.	int BiWidth(BiTree T){  
126.	    //返回二叉树宽度  
127.	    if (isBiTreeEmpty(T)) {  
128.	        return 0;  
129.	    }  
130.	    queue<BiTree> q;  
131.	    int maxWidth = 1;  
132.	    q.push(T);  
133.	  
134.	    while (1) {  
135.	        int len = q.size();  
136.	        if (!len) {  
137.	            break;  
138.	        }  
139.	        while (len--) {  
140.	  
141.	            BiTree temp = q.front();  
142.	            q.pop();  
143.	            if (temp->lchild) {  
144.	                q.push(temp->lchild);  
145.	            }  
146.	            if (temp->rchild) {  
147.	                q.push(temp->rchild);  
148.	            }  
149.	        }  
150.	        maxWidth = max(maxWidth, (int) q.size());  
151.	    }  
152.	    return maxWidth;  
153.	}  
154.	  
155.	void CopyBitree(BiTree source,BiTree &target){  
156.	    //将source中的二叉树复制给target，原二叉树和复制的二叉树之间销毁操作不能互相影响  
157.	    if(!source){  
158.	        target = NULL;  
159.	        return;  
160.	    }  
161.	  
162.	    else{  
163.	        target = (BiTNode *)malloc(sizeof(BiTNode));  
164.	        target->data = (TElemType)source->data;  
165.	        CopyBitree(source->lchild,target->lchild);  
166.	        CopyBitree(source->rchild,target->rchild);  
167.	    }  
168.	}  
169.	  
170.	  
171.	void DestroyBiTree(BiTree &T){  
172.	    //销毁二叉树并释放内存  
173.	    if(isBiTreeEmpty(T)){  
174.	        cout<<"DestroyBiTree succeed."<<endl;  
175.	        return;  
176.	    }  
177.	    else{  
178.	        if(T->lchild!=NULL) DestroyBiTree(T->lchild);  
179.	        if(T->rchild!=NULL) DestroyBiTree(T->rchild);  
180.	        free(T);  
181.	        T = NULL;  
182.	    }  
183.	}  
184.	  
185.	void DisplayBitree_control(BiTree n, bool left, string const& indent){  
186.	    //DisplayBitree()函数的中间控制函数  
187.	    if (n->rchild)  
188.	    {  
189.	        DisplayBitree_control(n->rchild, false, indent + (left ? "|     " : "      "));  
190.	    }  
191.	    cout << indent;  
192.	    cout << (left ? '\\' : '/');  
193.	    cout << "-----";  
194.	    cout << n->data << endl;  
195.	    if (n->lchild)  
196.	    {  
197.	        DisplayBitree_control(n->lchild, true, indent + (left ? "      " : "|     "));  
198.	    }  
199.	}  
200.	void DisplayBitree(BiTree root){  
201.	    //以树形结构形式输出二叉树  
202.	    if(!root){  
203.	        cout<<"An empty tree."<<endl;  
204.	        return;  
205.	    }  
206.	    if (root->rchild)  
207.	    {  
208.	        DisplayBitree_control(root->rchild, false, "");  
209.	    }  
210.	    cout << root->data << endl;  
211.	    if (root->lchild)  
212.	    {  
213.	        DisplayBitree_control(root->lchild, true, "");  
214.	    }  
215.	}  
216.	#endif

main.cpp


1.	#include <stdio.h>  
2.	#include <string.h>  
3.	#include <stdlib.h>  
4.	#include <iostream>  
5.	using namespace std;  
6.	#include "Noah_BiTree.h"  
7.	void Menue_gui();  
8.	void func1();  
9.	void func2();  
10.	void func3();  
11.	void func4();  
12.	  
13.	int main()  
14.	{  
15.	    while(1){  
16.	        Menue_gui();  
17.	        int func;  
18.	        scanf("%d",&func);  
19.	        switch(func){  
20.	            case 0:  
21.	                exit(0);  
22.	            case 1:  
23.	                func1();break;  
24.	            case 2:  
25.	                func2();break;  
26.	            case 3:  
27.	                func3();break;  
28.	            case 4:  
29.	                func4();break;  
30.	            default:  
31.	                printf("Input error! Please try again!");  
32.	        }  
33.	        printf("\n");  
34.	        system("pause");  
35.	    }  
36.	    return 0;  
37.	}  
38.	  
39.	//主界面  
40.	void Menue_gui(){  
41.	    system("cls");  
42.	    printf("**********************************Binary Tree calcuator**************************************\n");  
43.	    printf("*********************************************************************************************\n");  
44.	    printf("Menue:\n");  
45.	    printf("\nExit this program------------------------------------------------------------------0.\n");  
46.	    printf("\nCreate a binary tree and show the tree structure-----------------------------------1.\n");  
47.	    printf("\nCreate a binary tree and show show the preoeder, inorder, postorder and levelorder-2.\n");  
48.	    printf("\nCreate a binary tree and calculate the number of nodes, leaves, height and width---3.\n");  
49.	    printf("\nCreate a binary tree, copy it, destory the original one and show the new tree------4.\n");  
50.	    printf("\n**********************************************************************************************\n");  
51.	    printf("Choose the function you want to use(input number):\n");  
52.	}  
53.	  
54.	void func1(){  
55.	    system("cls");  
56.	    printf("-----ENTER FUNCTION : Create a binary tree and show the tree structure--1.-----\n");  
57.	    BiTree T1;  
58.	    CreateBiTree_withhint(T1);  
59.	    DisplayBitree(T1);  
60.	}  
61.	void func2(){  
62.	    system("cls");  
63.	    printf("-----ENTER FUNCTION : Create a binary tree and show show the preoeder, inorder, postorder and levelorder--2.-----\n");  
64.	    BiTree T1;  
65.	    CreateBiTree_withhint(T1);  
66.	    cout<<endl<<"The tree form of the Binary Tree is:"<<endl;  
67.	    DisplayBitree(T1);  
68.	    cout<<endl<<"The preorder of the Binary Tree is:"<<endl;  
69.	    preorder(T1);  
70.	    cout<<endl<<"The inorder of the Binary Tree is:"<<endl;  
71.	    inorder(T1);  
72.	    cout<<endl<<"The postorder of the Binary Tree is:"<<endl;  
73.	    postorder(T1);  
74.	    cout<<endl<<"The levelorder of the Binary Tree is:"<<endl;  
75.	    leverorder(T1);  
76.	}  
77.	void func3(){  
78.	    system("cls");  
79.	    printf("-----ENTER FUNCTION : Create a binary tree and calculate the number of nodes, leaves, height and width--3.-----\n");  
80.	    BiTree T1;  
81.	    CreateBiTree_withhint(T1);  
82.	    cout<<endl<<"The tree form of the Binary Tree is:"<<endl;  
83.	    DisplayBitree(T1);  
84.	    cout<<endl<<"The number of nodes is:"<<NumofNode(T1)<<endl;  
85.	    cout<<endl<<"The number of leaves is:"<<Numofleaves(T1)<<endl;  
86.	    cout<<endl<<"The height is:"<<BiHight(T1)<<endl;  
87.	    cout<<endl<<"The width is:"<<BiWidth(T1)<<endl;  
88.	}  
89.	void func4(){  
90.	    system("cls");  
91.	    printf("-----ENTER FUNCTION : Create a binary tree, copy it, destory the original one and show the new tree--4.-----\n");  
92.	    BiTree T1;  
93.	    CreateBiTree_withhint(T1);  
94.	    cout<<endl<<"The tree form of the [ORIGINAL] Binary Tree is:"<<endl;  
95.	    DisplayBitree(T1);  
96.	    BiTree T2;  
97.	    CopyBitree(T1,T2);//复制T1到T2  
98.	    DestroyBiTree(T1);//销毁T1  
99.	    cout<<endl<<"After destroy, the tree form of the [ORIGINAL] Binary Tree is:"<<endl;  
100.	    DisplayBitree(T1);  
101.	    cout<<endl<<"The tree form of the [NEW] Binary Tree is:"<<endl;  
102.	    DisplayBitree(T2);  
103.	}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/621985