二叉树遍历

Question

建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
[测试数据]
ABCффDEфGффFффф（其中ф表示空格字符）
则输出结果为 先序：ABCDEGF
中序：CBEGDFA
后序：CGBFDBA
满意追加分数以示感激。
一楼大侠，我想问你的结点个数怎么是0个啊？并且输入没有结束的时候啊？怎么回事。究竟怎么输入啊？

Answer 1

0是初始节点数
输入时请一次性输完ABCффDEфGффFффф在按ENTER键 不要输入一个按一下

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())==' ')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree root;
int i,depth;
printf("NodeNum:%d\n",NodeNum);
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do { //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //先判断节点数是否已有。不用再先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5:
if(!NodeNum)
TreeDepth(root);
printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}

Answer 2

我这个程序建的二叉树是二叉搜索树
#include <iostream>
using namespace std;
struct tree
{
int a;tree*lchild,*rchild;
};
class bindarytree
{
private:tree*root;
public:void create();/*构造函数*/
int math(tree*p);/*二叉树叶节点数*/
tree *getroot ();/*返回二叉树根节点指针*/
int high(tree*p);/*二叉树高度*/
void preorder(tree*p);/*前序遍历二叉树*/
void inorder(tree*p);/*中序遍历二叉树*/
void postorder(tree*p);/*后续遍历二叉树*/
friend void visit(tree*p);/*输出节点的纸*/
};
void bindarytree::create()
{
tree*p,*q;
p=new struct tree;
cin>>p->a;
p->lchild=NULL;p->rchild=NULL;
root=p;
do
{
q=new struct tree;
cin>>q->a;
q->lchild=NULL;q->rchild=NULL;
if(q->a==0)
return;
else
{
p=root;
do
{
if(p->a>=q->a&&p->lchild!=NULL)
p=p->lchild;
if(p->a<q->a&&p->rchild!=NULL)
p=p->rchild;
if(p->a>=q->a&&p->lchild==NULL)
p->lchild=q;
if(p->a<q->a&&p->rchild==NULL)
p->rchild=q;
}while(p->lchild!=q&&p->rchild!=q);
}
}while(1);
}
int bindarytree::math(tree*p)
{
if(p==NULL)
return 0;
if(p->lchild==NULL&&p->rchild==NULL)
return 1;
else return(math(p->lchild)+math(p->rchild));
}

tree * bindarytree::getroot()
{
return root ;
}
int bindarytree::high(tree*p)
{
if(p==NULL)
return 0;
if(p->lchild==NULL&&p->rchild==NULL)
return 1;
else return((high(p->lchild)+1)>(high(p->rchild)+1)?(high(p->lchild)+1):(high(p->rchild)+1));
}
void bindarytree::inorder(tree *p)
{
if(p!=NULL)
{
inorder(p->lchild);
visit(p);
inorder(p->rchild);
}
}
void bindarytree::preorder(tree*p)
{
if(p!=NULL)
{ visit(p);
preorder(p->lchild);
preorder(p->rchild);
}
}
void bindarytree::postorder(tree*p)
{
if(p!=NULL)
{
postorder(p->lchild);
postorder(p->rchild);
visit(p);
}
}
void visit(tree*p)
{
if(p!=NULL)
cout<<p->a<<endl;
}
void main()
{
tree*root;int b,c;
bindarytree a;
a.create() ;
root=a.getroot();
b=a.math(root);
root=a.getroot();
c=a.high(root);
cout<<"叶节点个数"<<b<<endl;
cout<<"树高读"<<c<<endl;
cout<<"前序周游"<<endl;
a.preorder(root);
cout<<"中续周游"<<endl;
a.inorder(root);
cout<<"后续周游"<<endl;
a.postorder(root);
}