二叉树的中序、前序、后序的递归及非递归遍历算法,层次
#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);
}
}
/**//*==========================================================================
=
* 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:=========================================================================
==*/
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 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 {
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();
}
}
}
}
浙公网安备 33021202002483