Question

求二叉树的遍历编程 要求： 1、建立二叉树 2、先序、中序、后序遍历输出 3、输出二叉树的深度和叶子节数目

要求：
1、建立二叉树 2、先序、中序、后序遍历输出 3、输出二叉树的深度和叶子节数目

Answer 1

创建 并 中序遍历输出

#include <stdio.h>
#include <malloc.h>
typedef enum PointerTag; //指针标志
typedef int DataType;
typedef struct BiThreTree{ //定义结点元素
PointerTag LTag,RTag;
DataType data;
struct BiThreTree *lchild,*rchild;
}BiThreTree;
BiThreTree *pre; //全局变量，用于二叉树的线索化
BiThreTree *CreateTree() //按前序输入建立二叉树
{
BiThreTree *T;
DataType e;
scanf("%d",&e);
if(e==0)
T=NULL;
else
{T=(BiThreTree *)malloc(sizeof(BiThreTree));
T->data=e;
T->LTag=Link; //初始化时指针标志均为Link
T->RTag=Link;
T->lchild=CreateTree();
T->rchild=CreateTree();
}
return T;
}
void InThread(BiThreTree *T)
{
BiThreTree *p;
p=T;
if(p)
{
InThread(p->lchild);
if(!p->lchild)
{ p->LTag=Thread;
p->lchild=pre;
}
if(!pre->rchild)
{ pre->RTag=Thread;
pre->rchild=p;
}
pre=p;
InThread(p->rchild);
}
}
BiThreTree *InOrderThrTree(BiThreTree *T) //中序线索化二叉树
{
BiThreTree *Thre; //Thre为头结点的指针
Thre=(BiThreTree *)malloc(sizeof(BiThreTree));
Thre->lchild=T;
Thre->rchild=Thre;
pre=Thre;
InThread(T);
pre->RTag=Thread;
pre->rchild=Thre;
Thre->rchild=pre;
return Thre;
}
void InThrTravel(BiThreTree *Thre) //中序遍历二叉树
{
BiThreTree *p;
p=Thre->lchild;
while(p!=Thre) //指针回指向头结点时结束
{
while(p->LTag==Link)
p=p->lchild;
printf("%4d",p->data);
while(p->RTag==Thread&&p->rchild!=Thre)
{p=p->rchild;
printf("%4d",p->data);
}
p=p->rchild;
}
}
int main()
{
BiThreTree *T,*Thre;
T=CreateTree();
Thre=InOrderThrTree(T);
InThrTravel(Thre);
system("pause");
}

第二个问题我看不懂。。。什么叫先中后序？

Answer 2

#include<stdio.h>
#include<stdlib.h>
typedef struct BiT{
char data;
struct BiT *lchild;
struct BiT *rchild;
}BiT;
BiT* CreateBiTree(BiT *T) {
//构造二叉链表表示的二叉树T
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
T = (BiT *)malloc(sizeof(BiT));
T->data = ch;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return T;
}
void PreOrderTraverse(BiT *T) {
// 先序遍历二叉树T
if (T) {
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiT *T) {
// 中序遍历二叉树T
if (T) {
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiT *T) {
// 后序遍历二叉树T
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
void main() {
printf("先序建树:");
BiT *T=CreateBiTree(T);
printf("\n先序遍历:");
PreOrderTraverse(T);
printf("\n中序遍历:");
InOrderTraverse(T);
printf("\n后序遍历:");
PostOrderTraverse(T);
getchar();getchar();
}

Answer 3

数据结构书上抄吧。。。。