Question

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

首先不要从网上复制，再就是最好是自己编的，最重要的是二叉树的建立，可以自己写出来，可以多写几种形式，，谢了高分，，
不是要先建立二叉链表？这个二叉树到底是怎样建立的？请各位答复一下 是C语言的，

Answer 1

我上机报告的代码和截图

#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;

}

Answer 2

/* 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();
}

Answer 3

#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*/

Answer 4

#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);
}
我们学校的， 你参考下，或许对你有用
这是前序的，

Answer 5

#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);
}