Visual_C++_6.0调试功能详解(3)
- 格式：pdf
- 大小：918.21 KB
- 文档页数：18
VisualC++6.0调试功能图解教程(3)--实例二树和二叉树
1.实验目的
1.熟悉二叉树的二叉链表存储结构；
2.掌握构造二叉树的方法；
3.加深对二叉树的遍历的理解。
二.需求分析
本程序演示用C++编写,完成按先序遍历生成二叉树,先序遍历打印输出二叉树,后序遍历打印
输出二叉树,中序遍历打印输出二叉树,层序遍历打印输出二叉树,先序遍历方法交换左右子树,求树的高
度,求树的叶子结点个数.
输入值的范围:建立一棵二叉时,要求结点的的左右孩子为空时输入0代替.所有输入值必须为整形.输入的结
点个数:若为单边二叉树(全只有左结点或全只有右结点)则为任意个数;若非单边二叉则要求结点最多的层
个数不得超过MAXSIZE的值.
输出形式:输出时如果结点的左右指针这空则以"#"代替输出.
程序所能完成的功能:程序能完成按先序遍历生成二叉树,先序遍历打印输出二叉树,后序遍历打印输出二
叉树,中序遍历打印输出二叉树,层序遍历打印输出二叉树,先序遍历方法交换左右子树,求树的高度,求树
的叶子结点个数.操作.
测试数据
A建立二叉树中输入1230000生成一棵树123####
B交换左右子树得到一棵二叉树1#2#3##
C按层序遍历树得到一棵二叉树1#2#3##
D求二叉树的高度得到高度3
E求叶子结点个数得到个数1
三.设计概要
(1)为了实现上述程序的功能,需要定义二叉树的抽象数据类型:
ADTBiTreeis{
数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
数据关系：R={|ai,ai+1∈D}
基本操作:
creat()
操作结果:建立一棵二叉树
preorder()
初始条件:二叉树已经存在
操作结果:先序遍历显示二叉树
preordertswap()
初始条件:二叉树已经存在
操作结果:交换二叉树的左右子树
theight()
初始条件:二叉树已经存在
操作结果:输出二叉树的高度
tleaves()初始条件:
操作结果:输出二叉树的叶子结点个数
levelorder()
初始条件:二叉树已经存在
操作结果:层序遍历显示二叉树
}ADTBiTree
(2)本程序包含两个类和一个结构体类型
A基类:队列类SeQueue有5个函数
1.构造函数SeQueue()
2.析构函数~SeQueue()
3.进队函数AddQ(NodeTypex)
4.出队函数DelQ()
5.判断非空函数IsEmpty()
B派生类:二叉树类BiTree有20个函数
1主函数main()
2.构造函数BiTree()
3.析构函数~BiTree()
4.建立树函数creat0()
5.先序遍历函数voidpreorder()
6.中序遍历函数inorder()
7.后序遍历函数postorder()
8.层序遍历函数levelorder()
9.交换左右子树函数preordertswap()
10.求二叉树高度函数theight()
11.求二叉树叶子结点个数函数tleaves()
12.建立二叉树递归算法函数*creat()
13.先序遍历递归算法函数preorder(NodeType*p)
14.中序遍历递归算法函数inorder(NodeType*p)
15.后序遍历递归算法函数postorder(NodeType*p)
16.按层遍历算法函数levelorder(NodeType*p)
17.先序遍历方法交换左右子树函数preorderswap(NodeType*p)
18.求二叉树高度递归算法函数height(NodeType*p)
19.求二叉树叶子结点个数的递归算法函数leaves(NodeType*p)
20.删除二叉树所有结点函数destroy(NodeType*&p)
C结构体类型NodeType
(3)本程序的三个文件
1.头文件BiTree.h
2.源文件Queue.cpp
BiTree.cpp
(4)函数之间的关系
四.详细设计
1//BiTree.h2//#include
3#include//VisualStudio2008中要求的
4#include"stdlib.h"
5#defineMAXSIZE2
6typedefintElemType;
7usingnamespacestd;//VisualStudio2008中要求的
8
9structNodeType//定义结点结构
体
10{
11ElemTypedata;
12NodeType*lch,*rch;
13};
14
15//队列
16classSeQueue//定义队
列类SeQueue
17{
18private:
19NodeTypeelem[MAXSIZE];//存储队列的数组个数
20intfront,rear;//队头,队尾
21public:
22SeQueue();
23~SeQueue();
24voidAddQ(NodeTypex);//入队函数
25NodeTypeDelQ();//出队函数
26intIsEmpty()//判断队列非空函数
27{
28returnfront==rear;
29}
30};
31
32//二叉树
33classBiTree:publicSeQueue//定义二叉树类BiTree作为队
列类SeQueue的派生类
34{
35public:
36BiTree(){root=NULL;}//
构造函数
37~BiTree(){destroy(root);}//析构函数
38voidpreorder()//先序遍历
39{preorder(root);}
40voidinorder()//中序遍
历
41{inorder(root);}
42voidpostorder()//后序遍历
43{postorder(root);}
44
45voidpreordertswap()//交换左右子树
46{preorderswap(root);}
47inttheight()//求二叉
树高度
48{returnheight(root);}
49inttleaves()//求二叉树叶
子结点个数50{returnleaves(root);}
51voidlevelorder()//按层遍历
52{levelorder(root);}
53voidcreat0();//建立树函
数
54private:
55NodeType*root;//数据成员，根结点
56NodeType*creat();//建立二叉树递归
算法
57voidpreorder(NodeType*p);//先序遍历递归算法
58voidinorder(NodeType*p);//中序遍历递归算法
59voidpostorder(NodeType*p);//后序遍历递归算法
60voidlevelorder(NodeType*p);//按层遍历算法
61voidpreorderswap(NodeType*p);//利用先序遍历方法交换
左右子树
62intheight(NodeType*p);//求二叉树高度递归算
法
63intleaves(NodeType*p);//求二叉树叶子结点个数
的递归算法
64voiddestroy(NodeType*&p);//删除二叉树所有结点
65};
66
67//BiTree.cpp
68#include"BiTree.h"
69
70voidBiTree::creat0()//建立树函
数，
71{
72cout<<"请按照树的先序遍历顺序组织数据"<
73cout<<"若结点信息是int，把每个结点的空孩子以输入;"<
74cout<<"一个结点的二叉树，输入：00;"<
75root=creat();//调用私有creat()(工具函数);
76}
77NodeType*BiTree::creat()//递归建立二叉树算法
78{
79NodeType*p;
80ElemTypex;
81cout<<"\n输入数据：";
82cin>>x;
83if(x==0)//若左或右孩子为空,置当前指针这空.
84p=NULL;
85else{
86p=newNodeType;
87p->data=x;
88p->lch=creat();//递归
调用自身
89p->rch=creat();
90}
91returnp;
92}
93
94//先序遍历递归算法
95voidBiTree::preorder(NodeType*p)//先序遍历显示
96{
97if(p!=NULL)
98{
99cout 100preorder(p->lch);//递归调用自身 101preorder(p->rch);//递归调用自身 102} 103else 104cout<<"#"; 105} 106//中序遍历递归算法 107voidBiTree::inorder(NodeType*p)//中序遍历显示 108{ 109 110if(p!=NULL) 111{ 112inorder(p->lch);//递归调用自身 113cout 114inorder(p->rch);//递归调用自身 115} 116else 117cout<<"#"; 118 119} 120//后序遍历递归算法 121voidBiTree::postorder(NodeType*p) 122{ 123if(p!=NULL) 124{ 125 126postorder(p->lch);//递归调用自身 127postorder(p->rch);//递归调用自身 128cout 129}
