先序遍历
中序遍历
后续遍历
/*
* 程序名：btree2.c，此程序演示二叉树的前序遍历、中序遍历和后序遍历，包括递归和非递归两种方法。
*
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
///
// 二叉树的数据结构。
typedef struct BiTNode
{
char data; // 存放结点的数据元素。
struct BiTNode *lchild; // 指向左子结点地址的指针。
struct BiTNode *rchild; // 指向右子结点地址的指针。
}BiTNode,*BiTree;
///
// 栈的数据结构。
#define MAXSIZE 30 // 顺序栈的最大长度。
typedef BiTree ElemType; // 自定义栈的数据元素为二叉树。
typedef struct
{
ElemType data[MAXSIZE]; // 用数组存储顺序栈中的元素。
int top; // 栈顶指针，从0到MAXSIZE-1，-1表示空栈。
// 也可以从1到MAXSIZE，0表示空栈。
}SeqStack,*PSeqStack;
// 顺序栈SS的初始化操作。
void InitStack(PSeqStack SS);
// 元素入栈，返回值：0-失败；1-成功。
int Push(PSeqStack SS, ElemType *ee);
// 元素出栈，返回值：0-失败；1-成功。
int Pop(PSeqStack SS, ElemType *ee);
// 求顺序栈的长度，返回值：栈SS中元素的个数。
int Length(PSeqStack SS);
// 清空顺序栈。
void Clear(PSeqStack SS);
// 判断顺序栈是否为空，返回值：1-空，0-非空或失败。
int IsEmpty(PSeqStack SS);
// 判断顺序栈是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqStack SS);
// 打印顺序栈中全部的元素。
void PrintStack(PSeqStack SS);
// 获取栈顶元素，返回值：0-失败；1-成功。
// 只查看栈顶元素的值，元素不出栈。
int GetTop(PSeqStack SS, ElemType *ee);
// 求二叉树的高度。
int TreeDepth(BiTree TT);
// 访问结点元素。
void visit(BiTNode *pp);
// 采用递归的方法对二叉树的先序遍历。
void PreOrder(BiTree TT);
// 不采用递归的方法对二叉树的先序遍历。
void PreOrder1(BiTree TT);
// 采用递归的方法对二叉树的中序遍历。
void InOrder(BiTree TT);
// 不采用递归的方法对二叉树的中序遍历。
void InOrder1(BiTree TT);
// 采用递归的方法对二叉树的后序遍历。
void PostOrder(BiTree TT);
// 不采用递归的方法对二叉树的后序遍历。
void PostOrder1(BiTree TT);
int main()
{
BiTree TT=0; // 声明树指针变量。
/*
// 手工构造一个如下结构的二叉树。
1
/ \
2 3
/ \ /
4 5 6
/ \ / \
7 8 9 0
*/
// 分配根节点。
TT=(BiTNode *)malloc(sizeof(BiTNode));
TT->data='1';
TT->lchild=TT->rchild=0;
// 第二层第一个节点。
TT->lchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->lchild->data='2'; TT->lchild->lchild=TT->lchild->rchild=0;
// 第二层第二个节点。
TT->rchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->rchild->data='3'; TT->rchild->lchild=TT->rchild->rchild=0;
// 第三层第一个节点。
TT->lchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->lchild->lchild->data='4'; TT->lchild->lchild->lchild=TT->lchild->lchild->rchild=0;
// 第三层第二个节点。
TT->lchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->lchild->rchild->data='5'; TT->lchild->rchild->lchild=TT->lchild->rchild->rchild=0;
// 第三层第三个节点。
TT->rchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->rchild->lchild->data='6'; TT->rchild->lchild->lchild=TT->rchild->lchild->rchild=0;
// 第四层第一个节点。
TT->lchild->lchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->lchild->lchild->lchild->data='7'; TT->lchild->lchild->lchild->lchild=TT->lchild->lchild->lchild->rchild=0;
// 第四层第二个节点。
TT->lchild->lchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->lchild->lchild->rchild->data='8'; TT->lchild->lchild->rchild->lchild=TT->lchild->lchild->rchild->rchild=0;
// 第四层第三个节点。
TT->lchild->rchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->lchild->rchild->lchild->data='9'; TT->lchild->rchild->lchild->lchild=TT->lchild->rchild->lchild->rchild=0;
// 第四层第四个节点。
TT->lchild->rchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
TT->lchild->rchild->rchild->data='0'; TT->lchild->rchild->rchild->lchild=TT->lchild->rchild->rchild->rchild=0;
// 二叉树的先序遍历。
printf("先序遍历结果1："); PreOrder(TT); printf("\n");
printf("先序遍历结果2："); PreOrder1(TT); printf("\n");
// 二叉树的中序遍历。
printf("中序遍历结果1："); InOrder(TT); printf("\n");
printf("中序遍历结果2："); InOrder1(TT); printf("\n");
// 二叉树的后序遍历。
printf("后序遍历结果1："); PostOrder(TT); printf("\n");
printf("后序遍历结果2："); PostOrder1(TT); printf("\n");
// 求二叉树的高度。
printf("树的高度是：%d\n",TreeDepth(TT));
return 0;
}
// 初始化顺序栈
void InitStack(PSeqStack SS)
{
Clear(SS); // 清空顺序栈。
}
// 清空顺序栈。
void Clear(PSeqStack SS)
{
if (SS == NULL) return; // 检查空指针。
SS->top=-1; // 栈顶指针置为-1。
memset(SS->data,0,sizeof(ElemType)*MAXSIZE); // 数组元素清零。
}
// 求顺序栈的长度，返回值：栈SS中元素的个数。
int Length(PSeqStack SS)
{
if (SS == NULL) return 0; // 检查空指针。
return SS->top+1;
}
// 判断顺序栈是否为空，返回值：1-空，0-非空或失败。
int IsEmpty(PSeqStack SS)
{
if (SS == NULL) return 0; // 检查空指针。
if (SS->top == -1) return 1;
return 0;
}
// 判断顺序栈是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqStack SS)
{
if (SS == NULL) return 0; // 检查空指针。
if (SS->top >= MAXSIZE-1) return 1;
return 0;
}
// 元素入栈，返回值：0-失败；1-成功。
int Push(PSeqStack SS, ElemType *ee)
{
if ( (SS == NULL) || (ee == NULL) ) return 0; // 检查空指针。
if (IsFull(SS) == 1)
{
printf("顺序栈已满，不能插入。\n"); return 0;
}
SS->top++; // 栈指针先加1。
memcpy(&SS->data[SS->top],ee,sizeof(ElemType)); // 用数组的下标访问。
// memcpy(SS->data+SS->top,ee,sizeof(ElemType)); // 采用指针运算也可以。
return 1;
}
// 打印顺序栈中全部的元素。
void PrintStack(PSeqStack SS)
{
if (SS == NULL) return; // 检查空指针。
if (SS->top == -1) { printf("栈为空。\n"); return; }
int kk;
for (kk = 0; kk <= SS->top; kk++)
{
printf("SS[%d],value=%d\n",kk,SS->data[kk]); // 用数组的下标访问。
// printf("SS[%d],value=%d\n",kk,*(SS->data+kk)); // 采用指针运算也可以。
}
}
// 元素出栈，返回值：0-失败；1-成功。
int Pop(PSeqStack SS, ElemType *ee)
{
if ( (SS == NULL) || (ee == NULL) ) return 0; // 检查空指针。
if (SS->top == -1) { printf("栈为空。\n"); return 0; }
memcpy(ee,&SS->data[SS->top],sizeof(ElemType)); // 用数组的下标访问。
// memcpy(ee,SS->data+SS->top,sizeof(ElemType)); // 采用指针运算也可以。
SS->top--; // 栈指针减1。
return 1;
}
// 获取栈顶元素，返回值：0-失败；1-成功。
// 只查看栈顶元素的值，元素不出栈。
int GetTop(PSeqStack SS, ElemType *ee)
{
if ( (SS == NULL) || (ee == NULL) ) return 0; // 检查空指针。
if (IsEmpty(SS) == 1) { printf("栈为空。\n"); return 0; }
memcpy(ee,&SS->data[SS->top],sizeof(ElemType)); // 用数组的下标访问。
// memcpy(ee,SS->data+SS->top,sizeof(ElemType)); // 采用指针运算也可以。
return 1;
}
// 访问结点元素。
void visit(BiTNode *pp)
{
printf("%c ",pp->data); // 访问结点元素就是把值输出来，意思一下就行了。
}
// 二叉树的先序遍历。
void PreOrder(BiTree TT)
{
if (TT == NULL) return;
visit(TT); // 访问子树TT的根结点。
PreOrder(TT->lchild); // 遍历左子树。
PreOrder(TT->rchild); // 遍历右子树。
}
// 二叉树的中序遍历。
void InOrder(BiTree TT)
{
if (TT == NULL) return;
InOrder(TT->lchild); // 遍历左子树。
visit(TT); // 访问子树TT的根结点。
InOrder(TT->rchild); // 遍历右子树。
}
// 二叉树的后序遍历。
void PostOrder(BiTree TT)
{
if (TT == NULL) return;
PostOrder(TT->lchild); // 遍历左子树。
PostOrder(TT->rchild); // 遍历右子树。
visit(TT); // 访问子树TT的根结点。
}
// 不采用递归的方法对二叉树的先序遍历。
void PreOrder1(BiTree TT)
{
SeqStack SS; // 创建顺序栈。
InitStack(&SS); // 初始化顺序栈。
ElemType ee=TT; // 队列的元素是二叉树。
while ( (ee!=NULL) || (IsEmpty(&SS)!=1) )
{
if (ee!=NULL)
{
visit(ee); // 入栈前访问。
Push(&SS,&ee); // 入栈。
ee=ee->lchild; // 继续处理左子树。
}
else
{
Pop(&SS,&ee); // 出栈。
ee=ee->rchild; // 处理右子树。
}
}
}
// 不采用递归的方法对二叉树的中序遍历。
void InOrder1(BiTree TT)
{
SeqStack SS; // 创建顺序栈。
InitStack(&SS); // 初始化顺序栈。
ElemType ee=TT; // 队列的元素是二叉树。
while ( (ee!=NULL) || (IsEmpty(&SS)!=1) )
{
if (ee!=NULL)
{
Push(&SS,&ee); // 入栈。
ee=ee->lchild; // 继续处理左子树。
}
else
{
Pop(&SS,&ee); // 出栈。
visit(ee); // 访问出栈元素。
ee=ee->rchild; // 处理右子树。
}
}
}
// 不采用递归的方法对二叉树的后序遍历。
void PostOrder1(BiTree TT)
{
SeqStack SS; // 创建顺序栈。
InitStack(&SS); // 初始化顺序栈。
ElemType ee=TT; // 队列的元素是二叉树。
ElemType pp=NULL; // 最近访问过的结点。
while ( (ee!=NULL) || (IsEmpty(&SS)!=1) )
{
if (ee!=NULL) // 从根结点开始，沿树的左结点，依次入栈，直到左结点为空。
{
Push(&SS,&ee);
ee=ee->lchild;
}
else // 转向右。
{
// 读取栈顶元素，不出栈。
GetTop(&SS,&ee);
// 如果右子树存在并且没有被访问过。
if ( (ee->rchild!=NULL) && (ee->rchild!=pp) )
{
ee=ee->rchild; // 转向右。
Push(&SS,&ee); // 右子树的根结点入栈。
ee=ee->lchild; // 再转向右子树的左结点。
}
else
{
Pop(&SS,&ee); // 将结点弹出。
visit(ee); // 访问结点。
pp=ee; // 记下最近访问过的结点。
ee=NULL; // 结点访问完后，重置ee为空，继续读取栈顶元素。
}
}
}
}
// 求二叉树的高度。
int TreeDepth(BiTree TT)
{
if (TT==NULL) return 0;
int ll=TreeDepth(TT->lchild); // 求左子树的高度。
int rr=TreeDepth(TT->rchild); // 求右子树的高度。
return ll>rr ? ll+1: rr+1; // 取左、右子树的较大者再加上根结点的高度。
}