数据结构实验---二叉树基本操作.doc

文档介绍：/*实验要求：
1．按先序序列构造一棵二叉链表表示的二叉树T；
2．对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列；
3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列；
4．求二叉树的深度/结点数目/叶结点数目；
5．将二叉树每个结点的左右子树交换位置；
6. 设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，
接下来按双序遍历它的右子树）；
7. 计算二叉树最大宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）；
8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点。*/
#include<>
#include<>
#include<>
#define Maxsize 30
typedef struct node{
char data;
struct node *rchild;
struct node *lchild;
}BTnode;
//求宽度时所用
typedef struct qnode{
int floor; //表示层次
BTnode *p;
}queue;
BTnode *CreatBTree(){//先序法创建二叉树
char ch;
BTnode *b;
scanf("%c",&ch);
if(ch=='#')
return NULL;
else{
b=(BTnode*)malloc(sizeof(BTnode));
b->data=ch;
b->lchild=CreatBTree();
b->rchild=CreatBTree();
return b;
}
}
//先序遍历
void preorder(BTnode *&b){
if(b!=NULL){
printf("%c",b->data);
preorder(b->lchild);
preorder(b->rchild);
}
}
void PreOrder(BTnode *&b){
BTnode *s[Maxsize];
int top=-1;
BTnode *p;
if(!b)
return;
else
p=b;
while(p||top!=-1) {
while(p){ //一直将左结点入栈
printf("%c",b->data);
s[++top]=p;
p=p->lchild;
}
if(top!=-1){ //栈不为空就出栈，
p=s[top--];
p=p->rchild; //即使p为null也没有关系，直接回溯到上一个左结点
}
}
}
//中序遍历
void middleorder(BTnode *&b){
if(b!=NULL){
middleorder(b->lchild);
printf("%c",b->data);
middleorder(b->rchild);
}
}
void Middleorder(BTnode *&b){
BTnode *s[Maxsize];
int top=-1;
BTnode *p;
if(!b)
return;
else
p=b;
while(p||top!=-1){
while(p){
s[++top]=p;
p=p->lchild;
}
if(top>-1){
prin