創建二叉樹,輸入先序擴展序列:ABD##E##C#F##
先序遍歷輸出節點:A?B?D?E?C?F
中序遍歷輸出節點:D?B?E?A?C?F
後序遍歷輸出節點:D?E?B?F?C?A
二叉樹示意圖:
A/?\
BC/\/?\
D?E?#F
/?\/?\/?\ ##?##?##測試數據2:
創建二叉樹,輸入先序擴展序列:ABC##DE#G##F###
先序遍歷輸出節點:A?B?C?D?E?G?F
中序遍歷輸出節點:C?B?E?G?D?F?A
後序遍歷輸出節點:C?G?E?F?D?B?A
二叉樹示意圖:
A
/\B?#
/?\
CD
/?\/?\ #?#EF/?\?/?\
#G## /?\##
#include<stdio.h>
#include<stdlib.h>
typedef?struct?Node//二叉樹的結構體
{
char?data;//字符
struct?Node?*lchild;?//左分支
struct?Node?*rchild;?//右分支
}Bitree;
//創建二叉樹:?用"先序遍歷"(遞歸法)
void?CreateBiTree(Bitree?**bt)
{
char?ch;
scanf("%c",&ch);?//輸入字符
if(ch=='#')?//'#'是空節點NULL
*bt=NULL;
else
{
*bt=(Bitree?*)malloc(sizeof(Bitree));
(*bt)->data=ch;
CreateBiTree(&((*bt)->lchild));
CreateBiTree(&((*bt)->rchild));
}
}
//用"先序遍歷"輸出節點(遞歸法)
void?preOrder(Bitree?*ptr)
{
if(ptr!=NULL)
{
printf("%c?",ptr->data);
preOrder(ptr->lchild);
preOrder(ptr->rchild);
}
}
//用"中序遍歷"輸出節點(遞歸法)
void?inOrder(Bitree?*ptr)
{
if(ptr!=NULL)
{
inOrder(ptr->lchild);
printf("%c?",ptr->data);
inOrder(ptr->rchild);
}
}
//用"後序遍歷"輸出節點(遞歸法)
void?postOrder(Bitree?*ptr)
{
if(ptr!=NULL)
{
postOrder(ptr->lchild);
postOrder(ptr->rchild);
printf("%c?",ptr->data);
}
}
int?main()
{
Bitree?*root;
printf("創建二叉樹,輸入先序擴展序列:");
CreateBiTree(&root);
printf("先序遍歷輸出節點:?");
preOrder(root);
printf("\n中序遍歷輸出節點:?");
inOrder(root);
printf("\n後序遍歷輸出節點:?");
postOrder(root);
printf("\n");
return?0;
}