高分求二叉树的建立例题，以及三种遍历

【【求】】二叉树的三种遍历举例!!!~

前序遍历:1 2 4 8 9 10 11 5 3 6 7 (规律：根在前；子树在根后且左子树比右子树靠前)；

中序遍历:8 4 10 9 11 2 5 1 6 3 7 (规律：根在中；左子树在跟左边，右子树在根右边)；

后序遍历:8 10 11 9 4 5 2 6 7 3 1 (规律：根在后；子树在根前且左子树比右子树靠前)；

其它例子：
前序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA


前序遍历:1 2 4 3 5 7 6
中序遍历:2 4 1 5 7 3 6
后序遍历:4 2 7 5 6 3 1

做类似的题目，你可以先由两个遍历画出二叉树。通过形象的二叉树来写出另一个遍历，写的方法如上（递归）。画出二叉树的方法如下：

已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。

已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。

我上机报告的代码和截图

#include<iostream>

using namespace std;

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status;

typedef char BiElemType;

// 二叉树的数据结构定义

typedef struct BiNode

{

    BiElemType data;

 BiNode *lchild,*rchild;

}BiNode,*BiTree; 

//构造一棵二叉树，并且按照前序遍历的方式赋值

Status CreateBiTree(BiTree &T)

{

   BiElemType ch;

   cin>>ch;

   if(ch=='#')T=NULL;

   else 

   {

    if(!(T=(BiNode *)malloc(sizeof(BiNode))))exit(OVERFLOW);

    T->data=ch;

       CreateBiTree(T->lchild);

       CreateBiTree(T->rchild);

   }

   return OK;

}

//先序遍历

Status preorder(BiTree T)

{

   if(T)

   {

       if(cout<<T->data<<' ')

     if(preorder(T->lchild))

      if(preorder(T->rchild))return OK;

    return ERROR;

   }

   else return OK;

}

//中序遍历

Status inorder(BiTree T)

{

   if(T)

   {

     if(inorder(T->lchild))

  if(cout<<T->data<<' ')

   if(inorder(T->rchild))return OK;

    return ERROR;

   }

   else return OK;

}

//后序遍历

Status postorder(BiTree T)

{

   if(T)

   {

     if(postorder(T->lchild))

  if(postorder(T->rchild))

    if(cout<<T->data<<' ')return OK;

    return ERROR;

   }

   else return OK;

}

int main()

{

    BiTree BiT;

 cout<<"以先序顺序输入二叉树的数据，以#表示空节点："<<endl;

 CreateBiTree(BiT);

    cout<<"以中序遍历输出：";

    inorder(BiT);

 cout<<endl;

    cout<<"以先序遍历输出：";

    preorder(BiT);

 cout<<endl;

    cout<<"以后序遍历输出：";

    postorder(BiT);

 cout<<endl;

    return 0;

}

/* bu用递归法输出中序和后续*/
#include "stdio.h"
#include "stdlib.h"
#define A 25
typedef struct Btree
{ char data;
struct Btree *lchild,*rchild;
}*tree,t2ree;
t2ree *creat()
{ tree t;
char ch;
scanf("%c",&ch);
if(ch=='#')
t=NULL;
else
{ t=(t2ree *)malloc(sizeof(t2ree));
t->data=ch;
t->lchild=creat();/* 开始格式不正确啊 ，就是我用了这个creat(r->rchild),所以对导致
指针乱算*/
t->rchild=creat();
}
return t;
}
/*显示用先序遍历*/
void preorder(tree t)
{ t2ree *s[A] ;
int top=0;
do
{ while(t!=NULL)
{ printf("%c",t->data);
if(t->rchild!=NULL)
s[top++]=t->rchild ; /*是右子树的地址*/
t=t->lchild; /* 再就是这个地方我加了一个{}结果导致了错误*/
}
if(top>=0)
t=s[--top];

}while(top>=0);
}
/* 中序遍历*/
void inorder(tree t)
{
tree s[A],p;
int top=0;
p=t;
do
{ while(p!=NULL)
{ s[top++]=p;
p=p->lchild;
}
if(top>=0)
{ p=s[--top];
printf("%c",p->data);
p=p->rchild;
}
}while(top>=0);
}

/* 后续遍历*/
void postorder(tree t)
{ int top=0,s2[A],b;
tree s1[A],p;
p=t;
do
{
while(p!=NULL)
{s1[top]=p;
s2[top++]=0;
p=p->lchild;
}
if(top>=0)
{ b=s2[--top];
p=s1[top];
if(b==0)
{ s1[top]=p;
s2[top++]=1;
p=p->rchild;
}
else
{ printf("%c",p->data);
p=NULL;
}
}
}while(top>0);
}
/* 求深度*/
int deep(tree t)
{ int i=0,j=0;
if(!t)
return 0;
else
{ i=deep(t->lchild);
j=deep(t->rchild);
}
return((i>j?i:j)+1);
}
/*求叶子的个数*/
int thief(tree t)
{ int i=0,j=0;
if(!t)
return 0;
else
{i=thief(t->lchild);
j=thief(t->rchild);
}
if(i==0&j==0)
return(1);
else
return(i+j);
}

main()
{ tree s;
s=creat();
printf("\XIAN xu shu chu \n");
preorder(s);
printf("\n kai shi zhong xu :\n");
inorder(s);
printf("\n hou xu :\n");
postorder(s);
printf("\n the shen du is %d\n",deep(s));
printf("\n the ye zi is %d\n",thief(s));
getch();
}

#include<stdio.h>
#include<stdlib.h>
#define ELEMTP int

struct node
{
ELEMTP data;
struct node *lc,*rc;
};

struct node *root;
int m=0;

main()
{
int cord;
struct node* creat();
void preorderz(struct node *t);
void inorder(struct node *t);
void postorder(struct node *t);
void deletes(struct node *t,struct node *p,struct node *f);
do
{
printf("\n 主菜单 \n");
printf(" 1 建立二叉树 \n");
printf(" 2 先序非递归遍历 \n");
printf(" 3 中序递归遍历 \n");
printf(" 4 后序递归遍历，求叶节点数 \n");
printf(" 5 删除节点 \n");
printf(" 6 结束程序运行 \n");
printf("---------------------------------------\n");
printf("请输入您的选择(1, 2, 3, 4, 5, 6)");
scanf("%d",&cord);
switch(cord)
{
case 1:
{
root=creat(); // 建立二叉树
printf("建立二叉树程序以执行完，\n");
printf("请返回主菜单，用遍历算法验证程序的正确性 \n");
}break;
case 2:
{
preorderz(root);
}break;
case 3:
{
inorder(root);
}break;
case 4:
{
postorder(root);
}break;
case 5:
{
//deletes(root)
}
case 6:
{
printf("二叉树程序执行完，再见！\n");
exit(0);
}
}
}while(cord<=6);
}

struct node* creat()
{
struct node *t,*q,*s[30];
int i,j,x;
printf("i,x=");
scanf("%d%d",&i,&x);//i是按满二叉树编号，x节点应有的序号，x是节点的数据
while((i!=0)&&(x!=0))
{
q=(struct node*)malloc(sizeof(struct node));
q->data=x;
q->lc=NULL; q->rc=NULL;
s[i]=q;
if(i==1)
t=q; //t代表树根节点
else
{
j=i/2; //双亲节点的编号
if((i%2)==0)
s[j]->lc=q;
else
s[j]->rc=q;
}
printf("i,x=");
scanf("%d%d",&i,&x);
}
return(t);
}

/*void preorderz(struct node* p)//前序非递归算法
{
struct node *q,*s[30]; //s辅助栈
int top,bools;
q=p;top=0; //栈顶指针
bools=1; //bools=1为真值继续循环；bools=0为假时栈空，结束循环
do
{
while(q!=NULL)
{
printf("%6d",q->data); //访问节点
top++;
s[top]=q;
q=q->lc;
}
if(top==0)
bools=0;
else
{
q=s[top];
top--;
q=q->rc;
}
}while(bools);
printf("\n");
}//////////////////////////结束preorderz*/

void preorderz(struct node* p)//前序递归遍历
{
if(p!=NULL)
{
printf("%6d",p->data);
inorder(p->lc);
inorder(p->rc);
}
}

void inorder(struct node* p)//中序非递归遍历
{
struct node *s[30],*q;
int top,bools;
q=p;top=0;
bools=1;
do
{
while(q!=NULL)
{
top++;
s[top]=q;
q=q->lc;
}
if(top==0)
bools=0;
else
{
q=s[top];
top--;
printf("%6d",q->data);
q=q->rc;
}
}while(bools);
}

/*void inorder(struct node* p)
{
if(p!=NULL)
{
inorder(p->lc);
printf("%6d",p->data);
inorder(p->rc);
}
}//////////////////////////结束inorder*/

void postorder(struct node* p)
{
struct node *s[30],*s2[30],*q;
int top,bools;
q=p;top=0;
bools=1;
do
{
while(q!=NULL)
{
top++;
s[top]=q;
s2[top]=1;
q=q->lc;
}
if(top==0)
bools=0;
else
{
if(s2[top]==1)
{
s2[top]=2;
q=s[top];
q=q->rc;
}
else
{
q=s[top];
s2[top]=0;
top--;
printf("%6d",q->data);
q=NULL;
}
}
}while(bools);
}

void deletes(struct node *t,struct node *p,struct node *f)
{
struct node *s,*q;
int bools=1;
if(p->lc==NULL)
s=p->rc;
else if(p->rc==NULL)
{
s=p->rc;
while(s->lc!=NULL)
{
q=s;
s=s->rc;
}
if(q==p)
q->rc=s->rc;
else
q->lc=s->rc;
p->data=s->data;
free(s);
bools=0;
}
if(bools==1)
{
if(f==NULL)
t=s;
else if(f->lc==p)
f->lc=s;
else
f->rc=s;
free(p);
}
}

/*void postorder(struct node* p)
{
if(p!=NULL)
{
postorder(p->lc);
postorder(p->rc);
printf("%6d",p->data);
if(p->lc==NULL&&p->rc==NULL)
m++; //统计叶子节点
}
}//////////////////////////结束postorder*/

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node /*二叉树结点定义*/
{
datatype data;
struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
void createbintree(bintree *t)
{/*按照前序遍历的顺序建立一棵给定的二叉树*/
char ch;
if ((ch=getchar())==' ')
*t=NULL;
else {
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}
void preorder(bintree t)
{/*前序遍历二叉树的递归算法*/
if (t) { printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
main() /*主程序*/
{ bintree root;
printf("\n");
createbintree(&root);
printf("\n");
printf("\n前序遍历结果是: ");
preorder(root);
}
我们学校的， 你参考下，或许对你有用
这是前序的，

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}node,*BinTree;
void inorder(node *p,int n)
{
if(p!=NULL)
{
int i;
inorder(p->lchild,n+1);
for(i=0;i<n;i++)
printf("----------");
printf("%c",p->data);
printf("\n");
inorder(p->rchild,n+1);
}
}
void create(BinTree *p)
{
char data;
printf("Please input a word:");
scanf("%s",&data);
if(data=='#')
p=NULL;
else
{
*p=(node *)malloc(sizeof(node));
if(*p==NULL)
{
printf("Ask for free faid!\n");
exit(1);
}
(*p)->data=data;
create(&(*p)->lchild);
create(&(*p)->rchild);
}
}
void main()
{
BinTree root;
create(&root);
inorder(root,0);
}

---

越西县17110133299： 高分求解C++二叉树的遍历(递归) - ？
充邹盐酸： #include typedef struct TP{ int data; struct TP *TLC; struct TP *TRC; }TNode; TNode *MTree()//先序遍历创建二叉树 { TNode *h; int temp; scanf(＂%d＂,&temp); if(temp==0) { h=NULL; } else { h=(TNode *)malloc(sizeof(TNode)); h->data=temp; h->...

越西县17110133299： 高分求一个二叉树的创建和遍历？
充邹盐酸： 说明:输入时按前序遍历方式依次输入各节点值,默认的结束符为0.即当一个节点为叶子节点时,把它的左子节点和右子节点都输为0,当然你可以自己修改为加别的值.例如某棵树的形状如下:A/ \B C/ \ \ D E F 则按如下输入:ABD00E...

越西县17110133299： 二叉树的创建和遍历 - ？
充邹盐酸： 我写了一个二叉树 你给看看 一定能行的 我自己用了 #include ＂stdio.h＂ #include ＂malloc.h＂ #include ＂string.h＂ #include ＂stdlib.h＂ #define Max 20 //结点的最大个数 typedef struct BinTNode{char data;struct BinTNode *lchild,*rchild; }...

越西县17110133299： 1.编写程序任意输入二叉树的结点个数和结点值,构造一棵二叉树,采用三种递归遍历算法(前序、中序、后序) - ？
充邹盐酸： tree.h#include<stdio.h> #include<malloc.h> #define MAX_NODE 50 typedef struct BiTNode {char data;BiTNode *lchild,*rchild;}BiTNode,*BiTree; BiTree CreateBiTree(); void InorderTraverse( BiTree T);creatTree.cpp #include＂tree.h＂BiTree...

越西县17110133299： 二叉树的建立,二叉树的遍历. - ？
充邹盐酸： #include ＂stdio.h＂//二叉树的练习 typedef struct BiTNode { char data; /*结点的数据域*/ struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/ } BiTNode , *BiTree;/*创建一棵二叉树*/ CreatBiTree(BiTree *T) { char c; c = getch(); printf(＂get = ...

越西县17110133299： 二叉树的三种遍历序列(先根次序,中根次序,后跟次序,)求结构图 - ？
充邹盐酸： /*先序递归遍历*/ void DLR(BTNode *bt) { if(bt){ printf(＂%c＂,bt->data);DLR(bt->lchild);DLR(bt->rchild);} } /*中序递归遍历*/ void LDR(BTNode *bt) { if(bt){ LDR(bt->lchild);printf(＂%c＂,bt->data);LDR(bt->rchild);} }/*后序递归遍历*/ void ...

越西县17110133299： 已知二叉树的前序和中序,构造该二叉树的方法是什么 - ？
充邹盐酸： 以下面的例题为例进行讲解: 已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF,求二叉树及后序遍历序列. 分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左边部分是根...

越西县17110133299： 关于二叉树的建立和输出查找,有例题. - ？
充邹盐酸： // c#include #include typedef struct node { int x; struct node *l, *r; }node; node * newnode(int x) { node *t = (node *)malloc(sizeof(node)); t->x = x; t->l = t->r = NULL; return t; } int main() { int N, x; char dir; node *Tree = NULL, *p, *q; scanf(＂%d＂, &N); ...

越西县17110133299： 急求 C语言写的“二叉树的建立和后序遍历的演示” - ？
充邹盐酸： 楼上 你那是C么? #include <stdlib.h> struct tree /* 树的结构宣告 */ { int data; /* 节点数据 */ struct tree *left; /* 指向左子树的指标 */ struct tree *right; /* 指向右子树的指标 */ }; typedef struct tree treenode; /* 树的结构新型态 */ typedef treenode ...

越西县17110133299： 一个简单二叉树的建立与遍历问题？
充邹盐酸： #include <stdlib.h> #include <stdio.h> typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;/*定义二叉链表结点结构*/ void CreateBiTree(BiTree *T) {/* 输入二叉树的先序遍历序列,创建...