本文包含兩個檔案的代碼和一張測試效果圖:
- BinaryTree.h檔案: 用于存儲資訊:存放函數、結構體、棧的函數實作、變量名等
- TreeTravel.cpp檔案: 用于測試
- 效果圖:(位于最上方)
效果圖:
#include<stdio.h>
#include<stdlib.h>
#define MAX_TRUE_SIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
typedef char TElemType; //樹結點的資料類型
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
Status CreateBiTree(BiTree *T){
TElemType ch;
scanf("%c", &ch);
if(ch == '#'){
*T = NULL;
}
else{
*T = (BiTree)malloc(sizeof(BiTNode));
if(!*T){
return ERROR;
}
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return OK;
}
void PreOrderTraverse(BiTree T){
if(T == NULL){
return;
}
printf("%c", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T){
if(T == NULL){
return;
}
InOrderTraverse(T->lchild);
printf("%c", T->data);
InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T){
if(T == NULL){
return;
}
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c", T->data);
}
void PreOrder(BiTree T)
{
if(T == NULL){
return;
}
BiTree Seqstack[MAX_TRUE_SIZE];
int top = -1;
BiTree p;
top++;
Seqstack[top] = T; // 先将根結點壓棧
while(top > -1) // 棧不為空時循環
{
p = Seqstack[top]; // 棧頂元素出棧
top--;
printf("%c", p->data); // 通路棧頂元素
if(p->rchild != NULL) // 如果右孩子不為空,則進棧
{
top++;
Seqstack[top] = p->rchild;
}
if(p->lchild != NULL) // 如果左孩子不為空,則進棧
{
top++;
Seqstack[top] = p->lchild;
}
}
}
#include "BinaryTree.h"
int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf("前序周遊:");
PreOrderTraverse(Tree);
printf("\n");
printf("中序周遊:");
InOrderTraverse(Tree);
printf("\n");
printf("後序周遊:");
PostOrderTraverse(Tree);
printf("\n");
printf("非遞歸先序周遊:");
PreOrder(Tree);
printf("\n");
}