1、Visual C+ 6.0 调试功能 图解教程 (3)-实例二 树和二叉树 1. 实验目的 1.熟悉二叉树的二叉链表存储结构； 2.掌握构造二叉树的方法； 3.加深对二叉树的遍历的理解。 二 .需求分析 本程序演示用 C+编写 ,完成按先序遍历生成二叉树 ,先序遍历打印输出二叉树 , 后序遍历打印输出二叉树 , 中序遍历打印输出二叉树 , 层序遍历打印输出二叉树 , 先序遍历方法交换左右子树 ,求树的高度 ,求树的叶子结点个数 . 输入值的范围 :建立一棵二叉时 ,要求结点的的左右孩子为空时输入 0 代替 .所有输入值必 须为整形 .输入的结点个数 :若为单边二叉树 (全只有左结点或全只有右结
2、点 )则为任意个数 ;若非单边二叉则要求结点最多的层个数不得超过 MAXSIZE 的值 . 输出形式 :输出时如果结点的左右指针这空则以 “ #“代替输出 . 程序所能完成的功能 :程序能完成按先序遍历生成二叉树 ,先序遍历打印输出二叉树 , 后序遍历打印输出二叉树 , 中序遍历打印输出二叉树 , 层序遍历打印输出二叉树 , 先序遍历方法交换左右子树 ,求树的高度 ,求树的叶子结点个数 .操作 . 测试数据 A 建立二叉树中输入 1230000 生成一棵树 123# B 交换左右子树得到一棵二叉树 1#2#3# C 按层序遍历树得到一棵二叉树 1#2#3# D 求二叉树的高度得到高度 3 E
3、求叶子结点个数得到个数 1 三 .设计概要 (1)为了实现上述程序的功能 ,需要定义二叉树的抽象数据类型 : ADT BiTree is 数据对象： D=ai|ai IntegerSet,i=0,1,2,n,n0 数据关系： R=|ai,ai+1 D 基本操作 : creat() 操作结果 :建立一棵二叉树 preorder() 初始条件 :二叉树 已经存在 操作结果 :先序遍历显示二叉树 preordertswap() 初始条件 : 二叉树已经存在 操作结果 :交换二叉树的左右子树 theight() 初始条件 : 二叉树已经存在 操作结果 :输出二叉树的高度 tleaves() 初始条件
4、: 操作结果 :输出二叉树的叶子结点个数 levelorder() 初始条件 : 二叉树已经存在 操作结果 :层序遍历显示二叉树 ADT BiTree (2) 本程序包含两个类和一个结构体类型 A 基类 :队列类 SeQueue 有 5 个函数 1.构造函数 SeQueue() 2.析构函数 SeQueue() 3.进队函数 AddQ(NodeType x) 4.出队函数 DelQ() 5.判断非空函数 IsEmpty() B 派生类 :二叉树类 BiTree 有 20 个函数 1 主函数 main() 2. 构造函数 BiTree() 3. 析构函数 BiTree() 4. 建立树函数 cr
5、eat0() 5. 先序遍历函数 void preorder() 6. 中序遍历函数 inorder() 7. 后序遍历函数 postorder() 8.层序遍历函数 levelorder() 9. 交换左右子树函数 preordertswap() 10. 求二叉树高度函数 theight() 11. 求二叉树叶子结点个数函数 tleaves() 12. 建立二叉树递归算法函数 *creat() 13. 先序遍历递归算法函数 preorder(NodeType *p) 14. 中序遍历递归算法函数 inorder(NodeType *p) 15. 后序遍历递归算法函数 postorder(No
6、deType *p) 16. 按层遍历算法函数 levelorder(NodeType *p) 17. 先序遍历方法交换左右子树函数 preorderswap(NodeType *p) 18. 求二叉树高度递归算法函数 height(NodeType *p) 19. 求二叉树叶子结点个数的递归算法函数 leaves(NodeType *p) 20. 删除二叉树所有结点函数 destroy(NodeType* 7 using namespace std; / Visual Studio 2008 中要求的 8 9 struct NodeType /定义结点结构体 10 11 ElemType d
7、ata; 12 NodeType *lch,*rch; 13 ; 14 15 /队列 16 class SeQueue /定义队列类 SeQueue 17 18 private: 19 NodeType elemMAXSIZE; /存储队列的数组个数 20 int front,rear; /队头 ,队尾 21 public: 22 SeQueue(); 23 SeQueue(); 24 void AddQ(NodeType x); /入队函数 25 NodeType DelQ(); /出队函数 26 int IsEmpty() /判断队列非空函数 27 28 return front = re
8、ar; 29 30 ; 31 32 /二叉树 33 class BiTree:public SeQueue /定义二叉树类 BiTree 作为队列类 SeQueue 的派生类 34 35 public: 36 BiTree() root = NULL; /构造函数 37 BiTree() destroy(root); /析构函数 38 void preorder() /先序遍历 39 preorder(root); 40 void inorder() /中序遍历 41 inorder(root); 42 void postorder() /后序遍历 43 postorder(root); 44
9、 45 void preordertswap() /交换左右子树 46 preorderswap(root); 47 int theight() /求二叉树高度 48 return height(root); 49 int tleaves() /求二叉树叶子结点个数 50 return leaves( root ); 51 void levelorder() /按层遍历 52 levelorder(root); 53 void creat0(); /建立树函数 54 private: 55 NodeType *root; /数据成员，根结点 56 NodeType *creat(); /建立二
10、叉树递归算法 57 void preorder(NodeType *p); /先序遍历递归算法 58 void inorder(NodeType *p); /中序遍 历递归算法 59 void postorder(NodeType *p); /后序遍历递归算法 60 void levelorder(NodeType *p); /按层遍历算法 61 void preorderswap(NodeType *p); /利用先序遍历方法交换左右子树 62 int height(NodeType *p); /求二叉树高度递归算法 63 int leaves(NodeType *p); /求二叉树叶子结点
11、个数的递归算法 64 void destroy(NodeType* /删除二叉树所有结点 65 ; 66 67 /BiTree.cpp 68 #include “BiTree.h“ 69 70 void BiTree:creat0() /建立树函数， 71 72 cout x; 83 if( x = 0 ) /若左或右孩子为空 ,置当前指针这空 . 84 p = NULL; 85 else 86 p = new NodeType; 87 p-data = x; 88 p-lch = creat(); /递归调用自身 89 p-rch = creat(); 90 91 return p; 92
12、93 94 /先序遍历递归算法 95 void BiTree:preorder(NodeType *p) /先序遍历显示 96 97 if( p != NULL) 98 99 cout data; 100 preorder( p-lch ); /递归调用自身 101 preorder( p-rch ); /递归调用自身 102 103 else 104 cout lch ); /递归调用自身 113 cout data; 114 inorder( p-rch ); /递归调用自身 115 116 else 117 cout lch ); /递归调用自身 127 postorder( p- rc
13、h ); /递归调用自身 128 cout data; 129 130 else 131 cout lch; 139 p-lch = p-rch; 140 p-rch = r; 141 /上面几条语句可以认为对结点的访问（交换左右孩子） 142 /替换了原来的： coutdatalch ); /递归调用自身 144 preorderswap( p-rch ); 145 146 147 void BiTree:destroy(NodeType* 151 destroy( p-rch ); 152 delete p; 153 p = NULL; 154 155 156 int BiTree:hei
14、ght(NodeType *p) /求二叉树高度递归算法 157 158 int hl,hr; 159 if( p != NULL ) 160 161 hl = height( p-lch ); 162 hr = height( p-rch ); 163 return ( hl hr ? hl : hr ) + 1; /当前结点高度是以最大的 (左右 )子树的高度加得到 164 165 166 else 167 return 0; 168 169 170 /求二叉树叶子结点个数的递归算法 171 int BiTree:leaves(NodeType *p) 172 173 if( p = NU
15、LL ) /当前结点是否为空 ,当为空时就没有左右孩子 174 return 0; 175 if( ( p- lch = NULL ) 178 179 return leaves( p- lch ) + leaves( p- rch ); /递归调用自身累加叶子结点个数 180 181 182 /按层遍历算法 183 void BiTree:levelorder(NodeType *p) 184 185 SeQueue q; /初始化一个队列 186 NodeType *t = p; 187 if (p) 188 189 q.AddQ(*p); /根结点非空则入队 190 191 while
16、(!q.IsEmpty() 192 193 t = /队非空则将结点指针出队 194 cout data; /并打印输出结点的数据值 195 if (t-lch) 196 197 q.AddQ(*(t-lch); /存在左孩子则将其进队 198 199 else 200 cout rch) 203 204 q.AddQ(*(t-rch); /存在右孩子则将其进队 205 206 else 207 cout k; 226 switch(k) 227 228 case 1: 229 cout =0 266 return 0; 267 /- 268 269 /Queue.cpp 270 #inclu
17、de “BiTree.h“ 271 SeQueue:SeQueue() /初始化队列 272 273 front=0; 274 rear=0; 275 276 277 SeQueue:SeQueue(); 278 /进队 279 void SeQueue:AddQ(NodeType x) 280 281 if(rear+1) % MAXSIZE=front) 282 cout“QUEUE IS FULLn“; 283 else 284 285 rear=(rear+1) % MAXSIZE; 286 elemrear=x; /将结点指针入队 287 288 289 290 /出队 291 NodeType SeQueue:DelQ() 292 293 NodeType q; 294 NodeType *t = NULL; 295 if(front=rear) 296 297 return *t; /返回空指针 298
