案例分析：
写出下面二叉树的先、中、后序遍历输出的结果：
注：先自己推算，然后用程序验算。
先序遍历的结果：A F H D C B J G E I K
中序遍历的结果：D H C F J B G A I E K
后序遍历的结果：D C H J G B F I K E A
代码如下：
#include "pch.h" #include <iostream> using namespace std; int top = -1; typedef struct Bitnode { char data; Bitnode *lchild, *rchild; }Bitnode,*bittree; //创建一个二叉树 void Createbittree(bittree *t) { *t =(Bitnode *) malloc(sizeof(Bitnode)); (*t)->data = 'A'; (*t)->lchild= (Bitnode *)malloc(sizeof(Bitnode)); (*t)->rchild =(Bitnode *)malloc(sizeof(Bitnode)); (*t)->lchild->data = 'F'; (*t)->rchild->data = 'E'; (*t)->lchild->lchild = (Bitnode *)malloc(sizeof(Bitnode)); (*t)->lchild->rchild = (Bitnode *)malloc(sizeof(Bitnode)); (*t)->rchild->lchild = (Bitnode *)malloc(sizeof(Bitnode)); (*t)->rchild->rchild = (Bitnode *)malloc(sizeof(Bitnode)); (*t)->lchild->lchild->data = 'H'; (*t)->lchild->rchild->data = 'B'; (*t)->rchild->lchild->data = 'I'; (*t)->rchild->rchild->data = 'K'; (*t)->rchild->lchild->lchild= NULL; (*t)->rchild->lchild->rchild= NULL; (*t)->rchild->rchild->lchild = NULL; (*t)->rchild->rchild->rchild = NULL; (*t)->lchild->lchild->lchild = (Bitnode *)malloc(sizeof(Bitnode)); (*t)->lchild->lchild->lchild->lchild = NULL; (*t)->lchild->lchild->lchild->rchild = NULL; (*t)->lchild->lchild->rchild = (Bitnode *)malloc(sizeof(Bitnode)); (*t)->lchild->lchild->rchild->lchild = NULL; (*t)->lchild->lchild->rchild->rchild = NULL; (*t)->lchild->rchild->lchild = (Bitnode *)malloc(sizeof(Bitnode)); (*t)->lchild->rchild->lchild->lchild = NULL; (*t)->lchild->rchild->lchild->rchild = NULL; (*t)->lchild->rchild->rchild = (Bitnode *)malloc(sizeof(Bitnode)); (*t)->lchild->rchild->rchild->lchild = NULL; (*t)->lchild->rchild->rchild->rchild = NULL; (*t)->lchild->lchild->lchild->data = 'D'; (*t)->lchild->lchild->rchild->data = 'C'; (*t)->lchild->rchild->lchild->data = 'J'; (*t)->lchild->rchild->rchild->data = 'G'; } //先序遍历入栈 void Push(Bitnode **a,Bitnode *elem) { a[++top] = elem; } //先序遍历出栈 void Pop() { if (top==-1) { return; } top--; } //获取栈顶元素 Bitnode *Get_top(Bitnode**a) { return a[top]; } //输出节点数据 void Printelem(Bitnode *elem) { cout << elem->data << " "; } //实现先序遍历算法 void preorder(Bitnode*tree) { Bitnode *a[30]; Bitnode *p; Push(a, tree); while (top!=-1) { p = Get_top(a); Pop(); while (p) { Printelem(p); if (p->rchild) { Push(a,p->rchild); } p = p->lchild; } } } //中序遍历二叉树 void inorder(bittree tree) { Bitnode *a[30]; //定义一个顺序栈 Bitnode *p; //临时指针 Push(a, tree); //根节点入栈 while (top != -1) //top！=-1来判定栈是否为空 { while ((p=Get_top(a))&&p)//获取栈顶元素不为空 { //左子树节点入栈，如果没有，null入栈 Push(a, p->lchild); } Pop();//跳出循环，栈顶元素是空， if (top!=-1) { p = Get_top(a);//获取栈顶元素 Pop(); Printelem(p); Push(a,p->rchild);//右子树节点入栈 } } } //二叉树后序遍历（非递归法） struct Snode { bittree p; int tag; }; //后序遍历的入栈函数 void PostPush(Snode*a, Snode sdata) { a[++top] = sdata; } //后序遍历 void PostOrder(bittree tree) { Snode a[20]; Bitnode*p; //节点指针 int tag; Snode sdata; p = tree; while (p||top!=-1)//用的或，这两种都行 { while (p) { sdata.p = p; sdata.tag = 0;//遍历左子树，设置标记位为0 PostPush(a, sdata);//入栈 p = p->lchild;//以该节点为根节点，遍历左子树 } sdata=a[top]; Pop(); p = sdata.p; tag = sdata.tag; if (tag==0)//条件为真，左子树遍历完成，该节点需要遍历右子树 { sdata.p = p; sdata.tag = 1; PostPush(a, sdata);//更改节点标志位，重新入栈 p = p->rchild;//将该节点的右子树设置为根节点，重新循环 } else { Printelem(p); p = NULL; } } } int main() { bittree tree; Createbittree(&tree); cout << "先序遍历的结果为："; preorder(tree); cout << endl; cout << "中序遍历的结果为："; inorder(tree); cout << endl; cout << "后序遍历的结果为："; PostOrder(tree); cout << endl; return 0; }
结果为：
