Question

数据结构关于遍历二叉树的一道题目 急 急 急 在线等啊

1 从键盘输入二叉树的各结点值，按先序递归方式创建二叉树；
2 分别实现先序、中序、后序递归遍历二叉树；
3 输出二叉树的高度；
4 输出二叉树的按层次遍历序列；
5 输出二叉树的先序非递归遍历下的结点访问次序；
6 以菜单方式运行。
源代码要求有注释说明
采纳后还有追加分数

Answer 1

#include<iostream>
using namespace std;
#include<malloc.h>
#include<stdio.h>
#include<math.h>
#define maxsize 20 //最大结点个数
//#define N 14 //必须输入结点个数(包含虚结点)
#define M 10 //最大深度
typedef struct node{
char data;
int m; //结点的深度
struct node*lchild,*rchild;
}Bitree;
Bitree*Q[maxsize];
Bitree*creatree()
{
char ch;
int front,rear;
// int i=1;
Bitree *T,*s;
T=NULL;
front=1;
rear=0;
cout<<"请输入数据"<<endl;
cin>>ch;
while(ch!='#')
{
// cin>>ch;
s=NULL;
if(ch!='@')
{
s=(Bitree*)malloc(sizeof(Bitree));
s->data =ch;
s->lchild =s->rchild =NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
{
T=s;
T->m=1; //父结点深度为一
}
else{
if(s!=NULL&&Q[front]!=NULL)
if(rear%2==0)
{
Q[front]->lchild =s;
Q[front]->lchild ->m =Q[front]->m+1;
}
else
{
Q[front]->rchild =s;
Q[front]->rchild ->m =Q[front]->m+1;
}

if(rear%2==1)
front++;
}
//i++;
cin>>ch;
}
return T;
}
int countleaf(Bitree* T)
{
if(T==NULL)
return (0);
else if((T->lchild==NULL)&&(T->rchild==NULL))
return (1);
else
return (countleaf(T->lchild)+countleaf(T->rchild));
}
int treedepth(Bitree *T)
{
if(T==NULL)
return (0);
else
{
if(treedepth(T->lchild )>treedepth(T->rchild ))
return(treedepth(T->lchild )+1);
else
return (treedepth(T->rchild )+1);
}
}
void output(Bitree*T) //输出打印二叉数
{
int i;
if(T!=NULL)
{
output(T->rchild ); //右根左遍历二叉数，结果从上到下显示
for(i=1;i<=M;i++)
{
if(i!=T->m)
cout<<" ";
else
cout<<T->data ;
}
cout<<endl;
//cout<<T->data ;
output(T->lchild );
}
}

int menu_select( )
{
int sn;
printf(" 打印二叉树问题\n");
printf("==================\n");
printf(" 1 二叉树的建立\n");
printf(" 2 打印二叉树\n");
printf(" 3 求二叉树叶子结点个数\n");
printf(" 4 求二叉树的深度\n");
printf(" 0 退出系统\n");
printf("==================\n");
printf(" 请 选 择0－4：\n");
for( ; ; )
{
scanf( "%d", &sn);
if( sn <0||sn>4)
printf("\n\t输入错误，重选0－4：\n");
else
break;
}
return sn;
}

int main( )
{
Bitree*T;
for(; ;)
{
switch(menu_select())
{
case 1: T=creatree();
printf("\n");
break;
case 2: cout<<"打印结果："<<endl;
output(T);
printf("\n");
break;
case 3: int i;
i=countleaf(T);
cout<<"所求二叉树叶子结点为"<<i;
cout<<endl;
break;
case 4: int j;
j=treedepth(T);
cout<<"所求二叉树深度为"<<j;
cout<<endl;
break;
case 0:printf("再见");
exit(0);
break;
}
}
return 0;
}

/*void main()
{
Bitree*T;
T=creatree();
cout<<"打印结果："<<endl;
output(T);
}*/

Answer 2

先序遍历
void preorder(Tree T)
{
if (T == NULL)
return;
else
{
printf("%c",T->Element);
preorder(T->Left);
preorder(T->Right);
}
}
后序遍历
void Postorder(Tree T)
{
if (T == NULL)
return;
else
{

preorder(T->Left);
preorder(T->Right);
printf("%c",T->Element);
}
}

Answer 3

//可以啊。如输入ABC###D## 输出CBAD
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef struct BiTNode{
char data;
struct BiTNode *lchild, *rchild;// 左、右孩子指针
}BiTNode, *BiTree;
int CreateBiTree(BiTree &T){
// 按中序输入二叉树中结点的值(一个字符），#字符表示空树
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else {
if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
CreateBiTree(T->lchild);
T->data=ch;// 生成根结点
CreateBiTree(T->rchild);
}
return 0;
}
void InTraverse(BiTree &T)
//中序遍历
{
if(T){ //非空二叉树
InTraverse(T->lchild); //递归遍历左子树
printf("%c",T->data); //访问D
InTraverse(T->rchild); //递归遍历右子树
}
}
int main(){
BiTree T;
CreateBiTree(T);
InTraverse(T);
return 0;
}

Answer 4

下面是二叉树的遍历题，看得部是很不明白，求解题思路，越详细越好！！！我的分不多，拜托各位！！！
32．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定
34．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D ）。
A．acbed B．decab C．deabc D．cedba
35. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：B
A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F
C．E,A,G,C,F,B,D D．上面的都不对