中序序列 BDE_AG_H
后序序列 _DC_GH_A
_____________(A)____________
____________/___\___________
________(BDE_)_(G_H)________
先序的第二个元素是B，所以B是A的左子树根节点
由中序B在最前，知道其他元素都在B的右子树上
所以，后序序列为(DE_)B(G_H)A，对比已有的后序序列_DC_GH_A
得后序序列为：EDCBGHFA，中序序列为：BDECAGFH
先序序列 ABC_EF__
中序序列 BDECAGFH
后序序列 EDCBGHFA
所以，二叉树为：
_____________(A)_____________
____________/___\____________
__________(B)____(F)_________
___________\_____/_\_________
___________(C)_(G)_(H)_______
___________/_________________
_________(D)_________________
#include<malloc.h>// malloc()等#include<stdio.h>// 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h>// atoi()，exit()
#include<math.h>// 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data// 结点的值
BiTNode *lchild,*rchild// 左右孩子指针
}BiTNode,*BiTree
int Nil=0// 设整型以0为空
void visit(int e)
{ printf("%d ",e)// 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number
scanf("%d",&number)// 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode))// 生成根结点
if(!T)
exit(OVERFLOW)
T->data=number// 将值赋给T所指结点
CreateBiTree(T->lchild)// 递归构造左子树
CreateBiTree(T->rchild)// 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild)// 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild)// 递归销毁右子树，如无右子树，则不执行任何操作
free(T)// 释放根结点
T=NULL// 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data)// 先访问根结点
PreOrderTraverse(T->lchild,Visit)// 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit)// 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit)// 先中序遍历左子树
Visit(T->data)// 再访问根结点
InOrderTraverse(T->rchild,Visit)// 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit)// 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit)// 再后序遍历右子树
Visit(T->data)// 最后访问根结点
}
}
void main()
{
BiTree T
InitBiTree(T)// 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n")
CreateBiTree(T)// 建立二叉树T
printf("先序递归遍历二叉树：\n")
PreOrderTraverse(T,visit)// 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n")
InOrderTraverse(T,visit)// 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n")
PostOrderTraverse(T,visit)// 后序递归遍历二叉树T
}
//输入先序扩展序列: 6 5 0 0 7 0 0//后序遍历序列: 5 7 6
// 6
// / \
// 5 7
// / \ / \
// 0 0 0 0
//输入先序扩展序列: 4 2 1 0 0 3 0 0 5 0 6 0 0
//后序遍历序列: 1 3 2 6 5 4
//
// 4
// / \
// 2 5
// / \ / \
// 1 3 0 6
// / \ / \ / \
// 0 0 0 0 0 0
#include<stdio.h>
#include<stdlib.h>
#define max 100 //20 //栈的大小
struct bitree //二叉树的结构体
{
int data
struct bitree *llink //左分支
struct bitree *rlink //右分支
}
struct stack_post //栈的结构体 [用于后序遍历]
{
struct bitree *bt //指向二叉树
int leftOrRight //当前节点是哪个分支,1=左分支 0=右分支
}
struct stack_post sk[max] //全局变量:栈(用于后序遍历)
//void build(struct bitree *n)
//创建二叉树: 先序扩展序列 + 递归法
void build(struct bitree **n)
{
//注:struct bitree **n 是指针的指针
int ch
scanf("%d",&ch)
if(ch==0)
{
*n=NULL
}
else
{
*n=(struct bitree *)malloc(sizeof(struct bitree))
if(*n == NULL)
{
printf("\nMemory overflow!\n")
exit(1)
}
(*n)->data=ch
build(&((*n)->llink))
build(&((*n)->rlink))
}
//原代码
/*
n=(struct bitree *)malloc(sizeof(struct bitree))
scanf("%d",&ch)
if(ch==0)
n=NULL
else
{
if(!(n=(struct bitree *)malloc(sizeof(struct bitree))))
{
return
}
n->data=ch
build(n->llink)
build(n->rlink)
}
*/
}
//后序遍历序列(非递归)
void Post_Order(struct bitree *n)
{
struct bitree *p=NULL
////struct stack_post sk[max] //全局变量:栈(用于后序遍历)
int top=0 //栈顶为0, top=1用于存放第1个数据
int leftOrRight //当前节点是哪个分支,1=左分支 0=右分支
struct bitree *tmpTree
if(n == NULL) return
p = n //当前二叉树的节点
leftOrRight = 1 //1=左分支(默认从左分支开始遍历)
while(p != NULL)
{
if(p->llink != NULL) //有左分支,当前节点入栈
{
top++
sk[top].bt=p
sk[top].leftOrRight=leftOrRight
p = p->llink
leftOrRight = 1
}
else if(p->rlink != NULL) //有右分支,当前节点入栈
{
top++
sk[top].bt=p
sk[top].leftOrRight=leftOrRight
p = p->rlink
leftOrRight = 0
}
else //该节点是"叶子"
{
printf("%d ",p->data)
while(1) //处于"回溯"状态
{
tmpTree=sk[top].bt //看[栈顶]
if(tmpTree==NULL) //[栈]已经没有数据
{
p=NULL //整个遍历过程结束,退出循环
break
}
if(leftOrRight == 1) //处于"左分支"回溯
{
if(tmpTree->rlink == NULL)//[栈顶]的节点没有右分支,出栈,打印
{
p=sk[top].bt
leftOrRight=sk[top].leftOrRight
top--
printf("%d ",p->data)
//仍然处于"回溯"状态
}
else //[栈顶]的节点有右分支,不出栈,右分支成为当前节点
{
p=tmpTree->rlink
leftOrRight=0 //设置当前处于右分支
break //退出"回溯"状态
}
}
else //处于"右分支"回溯
{
//[栈]有节点,出栈,打印
p=sk[top].bt
leftOrRight=sk[top].leftOrRight
top--
printf("%d ",p->data)
//仍然处于"回溯"状态
}
} //while(1)结束
} //if(p->llink != NULL)else结束
} //while(p != NULL)结束
//栈顶top=0,说明[栈]已经没有数据
printf("\n核对,栈顶 top = %d\n",top)
}
//有错误
//原代码,后序遍历序列(非递归)
/*
void postorder(struct bitree *n)
{
struct bitree *p,*q
int i
p=(struct bitree *)malloc(sizeof(struct bitree))
p=n
q=(struct bitree *)malloc(sizeof(struct bitree))
struct bitree *s[max]
for(i=0i<maxi++)
{
s[i]=(struct bitree *)malloc(sizeof(struct bitree))
}
int top=-1
do
{
while(p!=NULL)
{
if(p->rlink!=NULL)
{
top++
s[top]=p->rlink
}
p=p->llink
}
p=s[top]
top--
if(p->rlink==NULL||p->rlink==q)
{
printf("%d ",p->data)
q=p
p=NULL
}
else
p=p->rlink
}while(p!=NULL||top!=-1)
}
*/
//后序遍历序列(递归) [用于对比测试]
void postTest(struct bitree *n)
{
if(n!=NULL)
{
postTest(n->llink)
postTest(n->rlink)
printf("%d ",n->data)
}
}
int main()
{
struct bitree *n
//原代码n=(struct bitree *)malloc(sizeof(struct bitree))
printf("Input the preorder-numbers of the tree('0' for NULL):\n")
//原代码build(n)
build(&n)
printf("\nPostorder is below: ")
//原代码postorder(n) //后序遍历序列(非递归)
Post_Order(n) //后序遍历序列(非递归)
printf("\n后序遍历序列(递归): ")
postTest(n) //用于对比测试
printf("\n")
return 0
}
