本文包含两个文件的代码和一张测试效果图:
- BinaryTree.h文件: 用于存储信息:存放函数、结构体、栈的函数实现、变量名等
- TreeTravel.cpp文件: 用于测试
- 效果图:(位于最上方)
效果图:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAnYldHL0FWby9mZvwFN4ETMfdHLkVGepZ2XtxSZ6l2clJ3LcV2Zh1Wa9M3clN2byBXLzN3btgHL9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsQTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yMyMzN4UGN5YDZyEWMxEjNzYzXwMTMzAjMxAzLcFTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
#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");
}