实验三 +二叉树的遍历(5页).doc

《实验三 +二叉树的遍历(5页).doc》由会员分享，可在线阅读，更多相关《实验三 +二叉树的遍历(5页).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-实验三 二叉树的遍历一、 实验目的1 进一步掌握指针变量的含义。2 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 掌握用指针类型描述、访问和处理二叉树的运算。二、 实验要求1 认真阅读和掌握本实验的参考程序。2 按照对二叉树的操作需要，在创建好二叉树后再通过遍历算法验证创建结果。3 保存程序的运行结果，并结合程序进行分析。三、 实验内容 以下参考程序是按完全二叉树思想将输入的字符串生成二叉树，并通过遍历来验证二叉树创建正确与否，但不能创建非完全二叉树，请认真研究该程序，然后模仿教材例6.4初始化方式创建二叉树:所有的空指针均用#表示，如教材图6-13对应的二叉树，建立时的初始序

2、列为：AB#D#CE#F#。源代码#define max 30#define NULL 0#include #include typedef struct BNode char data;/*数据域 */struct BNode *lchild,*rchild;/指向左右子女 BinTree;void preorder(BinTree *t); /声明先根遍历函数void inorder(BinTree *t); /声明中根遍历函数void postorder(BinTree *t);/声明后根遍历函数int leafs(BinTree *b); /声明求叶子数函数int treedeep(B

3、inTree *p); /声明求树的深度函数BinTree *swap(BinTree *p); /声明交换二叉树的所有结点的左右子树的函数BinTree *create_tree() BinTree *p; char ch; ch=getchar(); if (ch=#) return NULL; else p=(BinTree *)malloc(sizeof(BinTree); /构造新结点 p-data=ch; p-lchild =create_tree(); /构造左子树 p-rchild =create_tree(); /构造右子树 return p; void main()int

4、i,n;char strmax;BinTree *root;/根结点printf(Input :,n);root=create_tree();printf(二叉树已成功创建! 结点序列为：); /先根遍历printf(n先根遍历结果n);preorder(root); printf(n);/中根遍历printf(n中根遍历结果n);inorder(root); printf(n);/后根遍历printf(n后根遍历结果n);postorder(root); printf(n); printf(n叶子数为：%dn,leafs(root); printf(n树的深度为：%dn,treedeep(r

5、oot); printf(n交换左右子树后先序遍历序列为n);preorder(swap(root); printf(nn);void preorder(BinTree *t)if(t!=NULL)printf( %c ,t-data); if(t-lchild) printf(-);preorder(t-lchild); if(t-rchild) printf(-);preorder(t-rchild);void inorder(BinTree *t)if(t!=NULL)inorder(t-lchild);printf( %c ,t-data);inorder(t-rchild);void

6、 postorder(BinTree *t)if(t!=NULL)postorder(t-lchild);postorder(t-rchild);printf( %c ,t-data);int leafs(BinTree *b)/求叶子数 int num1,num2;if(b=NULL) return (0);else if(b-lchild=NULL & b-rchild=NULL) return (1); else num1=leafs(b-lchild); num2=leafs(b-rchild); return(num1+num2); int treedeep(BinTree *p)/

7、求树的深度int ldeep,rdeep,deep;if(p=NULL) deep=0;elseldeep=treedeep(p-lchild);rdeep=treedeep(p-rchild);deep=(ldeeprdeep?ldeep:rdeep)+1; return deep;BinTree *swap(BinTree *p)/交换二叉树的所有结点的左右子树BinTree *stackmax;int k=0;stackk=NULL;if(p!=NULL)stack+k=p-lchild;p-lchild=p-rchild;p-rchild=stackk;p-lchild=swap(p-lchild);p-rchild=swap(p-rchild);return p;-第 5 页-