实验三 二叉树的遍历

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

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

3、e *b); /声明求叶子数函数int treedeep(BinTree *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->rch

4、ild =create_tree(); /构造右子树 return p; void main()int 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

5、("n");/后根遍历printf("n后根遍历结果n");postorder(root); printf("n"); printf("n叶子数为：%dn",leafs(root); printf("n树的深度为：%dn",treedeep(root); printf("n交换左右子树后先序遍历序列为n");preorder(swap(root); printf("nn");void preorder(BinTree *t)if(t!=NULL)print

6、f(" %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 postorder(BinTr

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