#include<stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK? 1
#define ERROR? 0
#define OVERFLOW? 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;
typedef enum {Link,Thread} PointerTag;
typedef struct BiThrNode
{
TElemType data; struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag;}BiThrNode;
typedef BiThrNode *BiThrTree;
BiTree CreateBiTree(BiTree T) //先序遍歷構造二叉樹
{
char ch; scanf("%c",&ch); if(ch=='#') //#代表空指針 T=NULL; else { T=(BiTNode *)malloc(sizeof(BiTNode)); //申請結點 if(!T)exit(OVERFLOW);
T->data=ch; //生成根結點 T->lchild=CreateBiTree(T->lchild); //構造左子樹 T->rchild=CreateBiTree(T->rchild); //構造右子樹 } return T;}
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType))
{//中序遍歷二叉樹
if(T) { if(InOrderTraverse(T->lchild,visit))if(visit(T->data))
if(InOrderTraverse(T->rchild,visit))
return OK; return ERROR; } else return OK;}
Status PrintElement(TElemType e)
{
printf("%-2c",e); return OK;}
void main()
{
BiTree T=NULL; printf("請輸入構造二叉樹的字符序列:"); T=CreateBiTree(T); if(T) printf("二叉樹建立成功!\n"); else printf("二叉樹構造失敗!!!\n"); printf("中序遍歷二叉樹:"); InOrderTraverse(T,PrintElement); printf("\n");}