上周数据结构课在讲二叉树的遍历，老师只讲递归算法，没有什么技术含量，遂自己琢磨非递归算法实现...
前序遍历:先访问根节点，再访问左子树，最后访问右子树。设置一个栈，出栈即为访问节点。先将根节点进栈，在栈不空时一直如下循环:出栈，访问，将其右孩子进栈，再将左孩子进栈。
中序遍历:先访问左子树，再访问根节点，最后访问右子树。设置一个栈，出栈即为访问节点。先将根节点的左节点全部进栈，然后出栈一个节点，访问。将该节点的右孩子节点进栈，再将右孩子节点的所有左节点全部进栈...如此这般直到栈空为止。
后序遍历:先访问左子树，再访问右子树，最后访问根节点。设置一个栈。先将根节点的左节点全部进栈。出栈一个节点，将该节点的右孩子进栈，再将右孩子的左节点全部进栈...当一个节点的左、右孩子都被访问过后再访问该节点，如此这般直到栈空为止。(判断某节点的右孩子是否被访问，需要单独设置一个指针跟踪刚刚访问的节点。在后序遍历中，某节点的右孩子节点一定刚好在该节点之前被访问)
因为代码的重点是非递归遍历，所以建立二叉树的过程我就使用了"前序递归"。对于如下一棵树，以"#"代表空节点，前序递归建立二叉树需要的输入数据和前序遍历的顺序是一样的，且每个叶子节点的左右孩子均为"#"。
输入:ABDH##I##EJ##K##CF#L##G##
前序遍历:A B D H I E J K C F L G
中序遍历:H D I B J E K A F L C G
后序遍历:H I D J K E B L F G C A
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 200
/* 定义二叉树节点类型 */
typedef struct node
{
char data;
struct node *lchild, *rchild;
}BTNode;
/* 函数声明 */
BTNode* CreatBitTree();
void PreOrder(BTNode*);
void InOrder(BTNode*);
void PostOrder(BTNode*);
/* 主函数 */
int main()
{
BTNode *root = NULL;
root = CreatBitTree();
PreOrder(root);
InOrder(root);
PostOrder(root);
system("pause");
return 0;
}
/* 递归前序建立二叉树 */
BTNode* CreatBitTree()
{
char ch;
BTNode *b;
scanf("%c", &ch);
/* 遇到空节点停止递归 */
if (ch == '#')
{
b = NULL;
}
else
{
b = (BTNode*) malloc(sizeof(BTNode));
/* 建立根节点 */
b->data = ch;
/* 递归先序建立左子树 */
b->lchild = CreatBitTree();
/* 递归先序建立右子树 */
b->rchild = CreatBitTree();
}
return b;
}
/* 非递归前序遍历二叉树 */
void PreOrder(BTNode* b)
{
BTNode *stack[MAXSIZE], *p;
int top = -1;
if (b != NULL)
{
/* 根节点入栈 */
top++;
stack[top] = b;
/* 栈不空时循环 */
while (top > -1)
{
/* 出栈并访问该节点 */
p = stack[top];
top--;
printf("%c ", p->data);
/* 右孩子入栈 */
if (p->rchild != NULL)
{
top++;
stack[top] = p->rchild;
}
/* 左孩子入栈 */
if (p->lchild != NULL)
{
top++;
stack[top] = p->lchild;
}
}
printf("\n");
}
}
/* 非递归中序遍历二叉树 */
void InOrder(BTNode* b)
{
BTNode *stack[MAXSIZE], *p;
int top = -1;
if (b != NULL)
{
p = b;
while (top > -1 || p != NULL)
{
/* 扫描p的所有左节点并入栈 */
while (p != NULL)
{
top++;
stack[top] = p;
p = p->lchild;
}
if (top > -1)
{
/* 出栈并访问该节点 */
p = stack[top];
top--;
printf("%c ", p->data);
/* 扫描p的右孩子 */
p = p->rchild;
}
}
printf("\n");
}
}
/* 非递归后序遍历二叉树 */
void PostOrder(BTNode* b)
{
BTNode *stack[MAXSIZE], *p;
int sign, top = -1;
if (b != NULL)
{
do
{
/* b所有左节点入栈 */
while (b != NULL)
{
top++;
stack[top] = b;
b = b->lchild;
}
/* p指向栈顶前一个已访问节点 */
p = NULL;
/* 置b为已访问 */
sign = 1;
while (top != -1 && sign)
{
/* 取出栈顶节点 */
b = stack[top];
/* 右孩子不存在或右孩子已访问则访问b */
if (b->rchild == p)
{
printf("%c ", b->data);
top--;
/* p指向被访问的节点 */
p = b;
}
else
{
/* b指向右孩子节点 */
b = b->rchild;
/* 置未访问标记 */
sign = 0;
}
}
}while (top != -1);
printf("\n");
}
}
其他实现：
#ifndef TREE_H
#define TREE_H
#include <stdio.h>
#include <malloc.h>
#include <stack>
#include <queue>
#include <assert.h>
using namespace std;
typedef int ElemType;
typedef struct treeT
{
ElemType key;
struct treeT* left;
struct treeT* right;
}treeT, *pTreeT;
/**//*===========================================================================
* Function name: visit
* Parameter: root:树根节点指针
* Precondition:
* Description:
* Return value:
* Author: Liu Qi, //-
===========================================================================*/
static void visit(pTreeT root)
{
if (NULL != root)
{
printf(" %d\n", root->key);
}
}
/**//*===========================================================================
* Function name: BT_MakeNode
* Parameter: target:元素值
* Precondition: None
* Postcondition: NULL != pTreeT
* Description: 构造一个tree节点，置左右指针为空，并且返回指向新节点的指针
* Return value: 指向新节点的指针
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
static pTreeT BT_MakeNode(ElemType target)
{
pTreeT pNode = (pTreeT) malloc(sizeof(treeT));
assert( NULL != pNode );
pNode->key = target;
pNode->left = NULL;
pNode->right = NULL;
return pNode;
}
/**//*===========================================================================
* Function name: BT_Insert
* Parameter: target:要插入的元素值, pNode:指向某一个节点的指针
* Precondition: NULL != ppTree
* Description: 插入target到pNode的后面
* Return value: 指向新节点的指针
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
pTreeT BT_Insert(ElemType target, pTreeT* ppTree)
{
pTreeT Node;
assert( NULL != ppTree );
Node = *ppTree;
if (NULL == Node)
{
return *ppTree = BT_MakeNode(target);
}
if (Node->key == target) //不允许出现相同的元素
{
return NULL;
}
else if (Node->key > target) //向左
{
return BT_Insert(target, &Node->left);
}
else
{
return BT_Insert(target, &Node->right);
}
}
/**//*===========================================================================
* Function name: BT_PreOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 前序遍历
* Return value: void
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
void BT_PreOrder(pTreeT root)
{
if (NULL != root)
{
visit(root);
BT_PreOrder(root->left);
BT_PreOrder(root->right);
}
}
/**//*===========================================================================
* Function name: BT_PreOrderNoRec
* Parameter: root:树根节点指针
* Precondition: Node
* Description: 前序(先根)遍历非递归算法
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_PreOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
visit(root);
s.push(root);
root = root->left;
}
else
{
root = s.top();
s.pop();
root = root->right;
}
}
}
/**//*===========================================================================
* Function name: BT_InOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 中序遍历
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_InOrder(pTreeT root)
{
if (NULL != root)
{
BT_InOrder(root->left);
visit(root);
BT_InOrder(root->right);
}
}
/**//*===========================================================================
* Function name: BT_InOrderNoRec
* Parameter: root:树根节点指针
* Precondition: None
* Description: 中序遍历,非递归算法
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_InOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
visit(root);
s.pop();
root = root->right;
}
}
}
/**//*===========================================================================
* Function name: BT_PostOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 后序遍历
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_PostOrder(pTreeT root)
{
if (NULL != root)
{
BT_PostOrder(root->left);
BT_PostOrder(root->right);
visit(root);
}
}
/**//*===========================================================================
* Function name: BT_PostOrderNoRec
* Parameter: root:树根节点指针
* Precondition: None
* Description: 后序遍历,非递归算法
* Return value: void
* Author: Liu Qi, // [1/1/2006]
===========================================================================*/
void BT_PostOrderNoRec(pTreeT root)
{
//学习中，尚未明白
}
/**//*===========================================================================
* Function name: BT_LevelOrder
* Parameter: root:树根节点指针
* Precondition: NULL != root
* Description: 层序遍历
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_LevelOrder(pTreeT root)
{
queue<treeT *> q;
treeT *treePtr;
assert( NULL != root );
q.push(root);
while (!q.empty())
{
treePtr = q.front();
q.pop();
visit(treePtr);
if (NULL != treePtr->left)
{
q.push(treePtr->left);
}
if (NULL != treePtr->right)
{
q.push(treePtr->right);
}
}
}
#endif
测试代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "tree.h"
#define MAX_CNT 5
#define BASE 100
int main(int argc, char *argv[])
{
int i;
pTreeT root = NULL;
srand( (unsigned)time( NULL ) );
for (i=0; i<MAX_CNT; i++)
{
BT_Insert(rand() % BASE, &root);
}
//前序
printf("PreOrder:\n");
BT_PreOrder(root);
printf("\n");
printf("PreOrder no recursion:\n");
BT_PreOrderNoRec(root);
printf("\n");
//中序
printf("InOrder:\n");
BT_InOrder(root);
printf("\n");
printf("InOrder no recursion:\n");
BT_InOrderNoRec(root);
printf("\n");
//后序
printf("PostOrder:\n");
BT_PostOrder(root);
printf("\n");
//层序
printf("LevelOrder:\n");
BT_LevelOrder(root);
printf("\n");
return 0;
}
补充一个后续遍历非递归版：
void BT_PostOrderNoRec(pTreeT root)
{
stack<treeT *> s;
pTreeT pre = NULL;
pTreeT top = NULL;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
top = s.top();
if(top->right != NULL && top->right != pre)
root = top->right;
else
{
visit(top);
pre = top;
s.pop();
}
}
}
}