#include<stdio.h>
#include<stdlib.h>

typedef struct Tree{
?
?int data;?? ??? ??? ??? ??? ?//?? ?存放數(shù)據(jù)域
?struct Tree *lchild;?? ??? ??? ?//?? ?遍歷左子樹指針
?struct Tree *rchild;?? ??? ??? ?//?? ?遍歷右子樹指針
?
}Tree,*BitTree;

BitTree CreateLink()
{
?? ?int data;
?? ?int temp;
?? ?BitTree T;
?? ?
?? ?scanf("%d",&data);?? ??? ?//?? ?輸入數(shù)據(jù)
?? ?temp=getchar();?? ??? ??? ?//?? ?吸收空格
?? ?
?? ?if(data == -1){?? ??? ??? ?//?? ?輸入-1 代表此節(jié)點下子樹不存數(shù)據(jù)，也就是不繼續(xù)遞歸創(chuàng)建
?? ??? ?
?? ??? ?return NULL;

?? ?}else{
?? ??? ?T = (BitTree)malloc(sizeof(Tree));?? ??? ??? ?//?? ??? ?分配內(nèi)存空間
?? ??? ?T->data = data;?? ??? ??? ??? ??? ??? ??? ??? ?//?? ??? ?把當前輸入的數(shù)據(jù)存入當前節(jié)點指針的數(shù)據(jù)域中
?? ??? ?
?? ??? ?printf("請輸入%d的左子樹: ",data);?? ??? ?
?? ??? ?T->lchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始遞歸創(chuàng)建左子樹
?? ??? ?printf("請輸入%d的右子樹: ",data);?? ??? ??? ?
?? ??? ?T->rchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始到上一級節(jié)點的右邊遞歸創(chuàng)建左右子樹
?? ??? ?return T;?? ??? ??? ??? ??? ??? ??? ?//?? ??? ?返回根節(jié)點
?? ?}?? ?
?? ?
}
//?? ?先序遍歷
void ShowXianXu(BitTree T)?? ??? ??? ?//?? ??? ?先序遍歷二叉樹
{
?? ?if(T==NULL)?? ??? ??? ??? ??? ??? ?//?? ?遞歸中遇到NULL，返回上一層節(jié)點
?? ?{
?? ??? ?return;
?? ?}
?? ?printf("%d ",T->data);
?? ?ShowXianXu(T->lchild);?? ??? ??? ?//?? ?遞歸遍歷左子樹
?? ?ShowXianXu(T->rchild);?? ??? ??? ?//?? ?遞歸遍歷右子樹
}
//?? ?中序遍歷
void ShowZhongXu(BitTree T)?? ??? ??? ?//?? ??? ?先序遍歷二叉樹
{
?? ?if(T==NULL)?? ??? ??? ??? ??? ??? ?//?? ?遞歸中遇到NULL，返回上一層節(jié)點
?? ?{
?? ??? ?return;
?? ?}
?? ?
?? ?ShowZhongXu(T->lchild);?? ??? ??? ?//?? ?遞歸遍歷左子樹
?? ?printf("%d ",T->data);
?? ?ShowZhongXu(T->rchild);?? ??? ??? ?//?? ?遞歸遍歷右子樹
?? ?
}
//?? ?后序遍歷
void ShowHouXu(BitTree T)?? ??? ??? ?//?? ??? ?后序遍歷二叉樹
{
?? ?if(T==NULL)?? ??? ??? ??? ??? ??? ?//?? ?遞歸中遇到NULL，返回上一層節(jié)點
?? ?{
?? ??? ?return;
?? ?}
?? ?
?? ?ShowHouXu(T->lchild);?? ??? ??? ?//?? ?遞歸遍歷左子樹
?? ?ShowHouXu(T->rchild);?? ??? ??? ?//?? ?遞歸遍歷右子樹
?? ?printf("%d ",T->data);
}


int main()
{
?? ?BitTree S;
?? ?printf("請輸入第一個節(jié)點的數(shù)據(jù):\n");
?? ?S = CreateLink();?? ??? ??? ?//?? ??? ?接受創(chuàng)建二叉樹完成的根節(jié)點
?? ?printf("先序遍歷結(jié)果: \n");
?? ?ShowXianXu(S);?? ??? ??? ??? ?//?? ??? ?先序遍歷二叉樹

?? ?printf("\n中序遍歷結(jié)果: \n");
?? ?ShowZhongXu(S);?? ??? ??? ??? ?//?? ??? ?中序遍歷二叉樹
?? ?
?? ?printf("\n后序遍歷結(jié)果: \n");
?? ?ShowHouXu(S);?? ??? ??? ??? ?//?? ??? ?后序遍歷二叉樹
?? ?
?? ?return 0;?? ?
} ?? ?