`
famoushz
  • 浏览: 2856372 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

二叉树的遍历:前序,中序,后序,层序--包括递归和非递归实现 (zt)

    博客分类:
  • work
阅读更多

 

后序遍历还没有明白,继续学习^_^,过几天写个huffman编码的例子来玩玩,不多说了,看代码吧,注意:程序申请的空间并没有释放^_^
/**//********************************************************************
    created:    2005/12/30
    created:    30:12:2005   10:39
    filename:     bintree.h
    author:        Liu Qi
   
    purpose:    二叉树的3种遍历方式(包括非递归实现),前序,后序和中序,先访问根节点就是
    前序(部分书籍称为先根遍历,个人觉得该说法更好^_^),类似的,最后访问根节点就是后序
*********************************************************************/


#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;
        }
    }
}

void BT_PreOrderNoRec(pTreeT root)
{
    stack<treeT *> s;

    while ((NULL != root))
    {
         while (NULL != root)
        {
            visit(root);
            s.push(root);
            root = root->left;
        }


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


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

void BT_PostOrderNoRec(pTreeT root)
{
stack<pTreeT> 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<treeT *> 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<treeT *> 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;
}
}
}
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics