当前位置：文档之家› 二叉树的中序、前序、后序的递归及非递归遍历算法,层次序的非递归遍历算法的实现

二叉树的中序、前序、后序的递归及非递归遍历算法,层次序的非递归遍历算法的实现

#ifndef TREE_H
#define TREE_H


#include
#include
#include
#include
#include

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 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 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 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
#include
#include
#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{
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;
}如果有兴趣不妨运行一下，看看效果^_^
另外请教怎样让二叉树漂亮的输出，即按照树的形状输出
posted on 2006-01-01 20:20 ngaut 阅读(37470) 评论(15) 编辑 收藏 引用 所属分类: c/c++/ds


评论
# re: 二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现 2006-01-03 23:09 PIGWORLD
给你写了个后序遍历的非递归实现，直接写的，没有验证过，估计没有什么大的问题，看看吧
思想是：
先找到最左边的叶子并把路上遇到的节点依次压栈，然后弹出栈顶的元素（该元素为最左边的叶子），并判断（1）它有没有右节点；（2）右节点是否被访问过。如果（1）为有右节点同时（2）为没有访问过，则先压入刚才弹出的元素，然后再压入它的右子树。否则，就访问该节点，并设置pre为改节点。

void BT_PostOrderNoRec(pTreeT root)
{
stack s;
s.push(root);

while(root != 0 || !s.isEmpty()) {

//找到最左边的叶子
while((root = root->left) != 0) {
s.push(root);
}

pTree pre; //记录前一个访问的节点
root = s.pop(); //弹出栈顶元素

//如果右子树非空，并且右子树未访问过，
//则（在内层while循环中）把右子树压栈
if(root->right != 0 && pre != root->right) {
//要把上一句中弹出的元素重新压栈
s.push(root);
root = root->right;
s.push(root);
}

//否则
else {
弹出栈顶节点，访问它并设置pre为该节点
root = pre = s.pop();
visit(root);
//使root为0以免进入内层循环
root = 0;
}
} 回复 更多评论

# re: 二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现 2006-09-08 17:22 247
*
* *
*
#
# # 回复 更多评论

# re: 二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现 2006-09-12 14:54 路人甲
void BT_PostOrderNoRec(pTreeT root)
{
stack s;
pTreeT pre=NULL;

while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
if (root->right!=NULL && pre!=root->right){
root=root->right;
}
else{
root=pre=s.top();
visit(root);
s.pop();
root=NULL;
}
}
}
} 回复 更多评论

# re: 二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现 2006-09-12 14:57 路人甲
根据lz和前面那个人的代码，经过调试成功，
现如下：
void BT_PostOrderNoRec(pTreeT root)
{
stack s;
pTreeT pre=NULL;

while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
if (root->right!=NULL && pre!=root->right){
root=root->right;
}
else{
root=pre=s.top();
visit(root);
s.pop();
root=NULL;
}
}
}
} 回复 更多评论

# re: 二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现 2007-09-12 12:11 路人乙
对 前面那个人的就象是POP了两次 丢失了一个 回复 更多评论

# re: 二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现 2008-01-09 21:33 ^^
maybe this is better:
void BT_PostOrderNoRec(pTreeT root)
{
stack s;
pTreeT pre = NULL;
pTreeT top = NULL;

while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->right;
}
else
{
top = s.top();
if(top->left != NULL && top->left != pre)
root = top->left;
else
{
visit(top);
s.pop();
pre = top;
}
}
}
}
回复 更多评论

# re: 二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现 2008-01-09 21:46 ^^
sorry,it is:
void BT_PostOrderNoRec(pTreeT root)
{
stack 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();
}
}
}
}

相关主题
文本预览
相关文档 最新文档