1、创建一棵二叉树，以二叉链表作存储结构，实现先根遍历算法 2、创建一棵二叉树，实现先根遍历算法、中根

Question

最好是c++的

Answer 1

你需要的东西这里面都包含了，你自己看哪里用得上就摘一段下来吧。

// 数据结构.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}

#include<stdio.h>
#include<stdlib.h>
#define MAX 20
#define NULL 0
typedef char ElemType;
typedef int Status;
typedef enum{link,thread} pointertag;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
pointertag Ltag,Rtag;
}BiTNode,*BiTree;
BiTree pre;
Status CreateBiTree(BiTree *T)//按前序构建二叉树。
{
char ch;
ch=getchar();
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=ch;
(*T)->Ltag=(*T)->Rtag=link;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return 1;
}
Status CreateBiTree1(BiTree *T)//按中序输入构建二叉树。
{
char ch;
ch=getchar();
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
CreateBiTree(&(*T)->lchild);
(*T)->data=ch;
CreateBiTree(&(*T)->rchild);
}
return 1;
}
void MidOrder(BiTree T)//递归中序输出。
{
if(T)
{
MidOrder(T->lchild);
printf("%2c",T->data);
MidOrder(T->rchild);
}
}
void PreOrder(BiTree T)//前序输出。
{
if(T)
{
printf("%2c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void EndOrder(BiTree T)//后序输出。
{
if(T)
{
EndOrder(T->lchild);
EndOrder(T->rchild);
printf("%2c",T->data);
}
}
void MidOrder1(BiTree T)//非递归中序输出。
{
int i=0;
BiTree p,s[100];
p=T;
do
{
while(p)
{
s[i++]=p;
p=p->lchild;
}
if(i>0)
{
p=s[--i];
printf("%2c",p->data);
p=p->rchild;
}
}while(i>0||p!=NULL);

}
void Levle(BiTree T)//按层次遍历二叉树。
{
BiTree Queue[MAX],b;
int front,rear;
front=rear=0;
if(T)
{
Queue[rear++]=T;
while(front!=rear)
{
b=Queue[front++];
printf("%2c",b->data);
if(b->lchild!=NULL)
Queue[rear++]=b->lchild;
if(b->rchild!=NULL)
Queue[rear++]=b->rchild;
}
}
}
int depth(BiTree T)//求二叉树的深度。
{
int dep1,dep2;
if(T==NULL)return 0;
else
{
dep1=depth(T->lchild);
dep2=depth(T->rchild);
return dep1>dep2?dep1+1:dep2+1;
}
}
void InThreading(BiTree p)//线索化。
{
if(p)
{
InThreading(p->lchild);
if(p->lchild=NULL){p->Ltag=thread;p->lchild=pre;}
if(pre->rchild==NULL){pre->Rtag=thread;pre->rchild=p;}
pre=p;
InThreading(p->rchild);
}
}
Status InorderThreading(BiTree *Thrt,BiTree T)//中序遍历二叉树T，并将其线索化。
{
(*Thrt)=(BiTree)malloc(sizeof(BiTNode));
(*Thrt)->Ltag=link;
(*Thrt)->Rtag=thread;
(*Thrt)->rchild=*Thrt;
if(T==NULL)
(*Thrt)->lchild=*Thrt;
else
{
(*Thrt)->lchild=T;
pre=*Thrt;
InThreading(T);
pre->rchild=(*Thrt);
pre->Rtag=thread;
(*Thrt)->rchild=pre;
}
return 1;
}
Status InorderTraverse(BiTree Thrt)//中序遍历线索二叉树Thrt,Thrt指向头结点。
{
BiTree p;
p=Thrt->lchild;
while(p!=Thrt)
{
while(p->Ltag==link)p=p->lchild;
printf("%2c",p->data);
while(p->Rtag==thread&&p->lchild!=Thrt)
{
p=p->rchild;
printf("%2c",p->data);
}
p=p->rchild;
}
return 1;
}
void main()
{
BiTree T=NULL,Thrt=NULL;
printf("创建一个二叉树\n");
CreateBiTree(&T);
//InorderThreading(&Thrt,T);
//InorderTraverse(Thrt);
//printf("中序遍历的结果是：");
//MidOrder(T);
//printf("\n");
printf("先序遍历的结果是：");
PreOrder(T);
printf("\n");
/*printf("后序遍历的结果是：");
EndOrder(T);
printf("\n");
printf("按层次遍历二叉树的结果是：");
Levle(T);
printf("\n");
printf("深度输出为：%d",depth(T));
printf("\n");*/
}

Answer 2

#include "stdio.h"
#include "malloc.h"
#define ELEMTYPE char
typedef struct BiTNode
{ ELEMTYPE data;
struct BiTNode *lchild,*rchild;
} BiTNode;
BiTNode *bulid() /*建树*/
{ BiTNode *q;
BiTNode *s[20];
int i,j;
char x;
printf("请按顺序输入二叉树的结点以输入0和*号结束\n");
printf("请输入你要输入的为第几个结点i=\n");
scanf("%d",&i);
printf("请输入你要输入该结点的数为x=");
getchar();
scanf("%c",&x);
while(i!=0&&x!='*')
{q=(BiTNode*)malloc(sizeof(BiTNode));
q->data=x;
q->rchild=NULL;
q->lchild=NULL;
s[i]=q;

if(i!=1)
{ j=i/2;
if(i%2==0)
s[j]->lchild=q;
else
s[j]->rchild=q;
}

printf("请输入你要输入的为第几个结点x=\n");
scanf("%d",&i);
printf("请输入你要输入该结点的数x=");
getchar();
scanf("%c",&x);
}
return s[1];
}
void preoder(BiTNode *bt) /*先序遍历*/
{ if(bt!=NULL)
{
printf("%c\n",(bt->data));

preoder(bt->lchild);

preoder(bt->rchild);
}
}
void InOrder(BiTNode *bt) /*中序遍历*/
{ if(bt!=NULL)
{ InOrder(bt->lchild);
printf("%c\n",bt->data);
InOrder(bt->rchild);
}
}
void postOrder(BiTNode *bt) /*后序遍历*/
{ if(bt!=NULL)
{ postOrder(bt->lchild);
postOrder(bt->rchild);
printf("%c\n",bt->data);
}
}

main()
{ int a;
BiTNode *bt;
bt=bulid();
k1: printf("需要先序遍历输出请输入1，中序遍历请输入2，后序遍历请输入3,结束输入0:");
scanf("%d",&a);
switch(a)
{
case(1): preoder(bt); goto k1;
case(2): InOrder(bt); goto k1;
case(3): postOrder(bt); goto k1;
case(0): break;
}
}

Answer 3

w