首页 » C++ » 递归与非递归实现二叉树的遍历

递归与非递归实现二叉树的遍历

原文 http://blog.csdn.net/soygrow/article/details/79235819

2018-02-03 02:00:31阅读(486)

递归实现二叉树的后续遍历

首先后续遍历可以使用递归来实现。一般情况下,能用递归实现的问题都可以用栈来解决,只是递归更符合人的思维方式,代码相对来说较简单。但是不能说明递归的方式比栈的方式更快、更省空间,因为在递归过程中都是操作系统帮助用栈实现存储信息。

下面使用递归的方式实现二叉树的后续遍历(包括先序和中序的实现,方法大致相同):

//递归实现后续遍历二叉树
void RecursionBackOrder(BTree *root)
{
    if (root == NULL)
        return;
    //cout<<root->data;若在此处处理数据则是先序遍历
    if (root->lChild != NULL)
        RecursionBackOrder(root->lChild);
    //cout<<root->data;若在此处处理数据则是中序遍历
    if (root->rChild != NULL)
        RecursionBackOrder(root->rChild);
    cout<<root->data;
}

使用栈来实现非递归的后续遍历二叉树的方法:

首先判断根节点是否为空,若不为空,则该根节点入栈,并标记已经访问过 进入while循环–栈中还存在元素。 又进入while循环—入栈。 取出栈的top元素,判断是否top元素的左右孩子是否存在、根据top元素的flag标记判断是否已经被访问过
若左右孩子存在,则先将右孩子入栈,同时标记flag被访问过,然后在将左孩子入栈,也标记其flag标记变量 出while循环。 出栈。 再出while循环。 取出栈的top元素,出栈。

下面是实现代码:

#pragma once
#ifndef LISTNODE_H
#define LISTNODE_H
#include <iostream>
#include <stack>
using namespace std;
struct BTree
{
    int data;
    BTree *lChild;
    BTree *rChild;
    BTree():lChild(NULL),rChild(NULL){};
};
//构造二叉树
void InitBTree(BTree *root)
{
    root->data = 1;
    root->lChild = new BTree();
    root->lChild->data = 2;
    root->rChild = new BTree();
    root->rChild->data = 3;
    root->lChild->lChild = new BTree();
    root->lChild->lChild->data = 4;
    root->lChild->rChild = new BTree();
    root->lChild->rChild->data = 5;
    root->rChild->lChild = new BTree();
    root->rChild->lChild->data = 6;
    root->rChild->rChild = new BTree();
    root->rChild->rChild->data = 7;
}
//递归实现后续遍历二叉树
void RecursionBackOrder(BTree *root)
{
    if (root == NULL)
        return;
    //cout<<root->data;若在此处处理数据则是先序遍历
    if (root->lChild != NULL)
        RecursionBackOrder(root->lChild);
    //cout<<root->data;若在此处处理数据则是中序遍历
    if (root->rChild != NULL)
        RecursionBackOrder(root->rChild);
    cout<<root->data;
}
struct StactBTree
{
    BTree *bTreeNode;
    int flag;//0:未访问,1:已访问
    StactBTree():flag(0),bTreeNode(NULL){};
};
//非递归实现后序遍历二叉树
int BackOrderBTree(BTree *root)
{
    if (root == NULL)
        return -1;
    //插入root节点
    StactBTree stackBTree;
    stackBTree.bTreeNode = root;
    stack<StactBTree> s;
    //将根节点放入栈
    s.push(stackBTree);
    stackBTree.flag = 1;//标记已经访问
    StactBTree* tmpStackBTree;
    //栈不为空将一直循环
    while (s.size()>0)
    {
        tmpStackBTree = &(s.top());//取得栈顶元素
        //入栈操作
        while (tmpStackBTree->flag==0 && (tmpStackBTree->bTreeNode->lChild!=NULL || tmpStackBTree->bTreeNode->rChild!= NULL))
        {
            //标记已经访问过该节点
            tmpStackBTree->flag = 1;
            //右子树不为空--后序遍历先从右子树入栈
            if (tmpStackBTree->bTreeNode->rChild!=NULL)
            {
                StactBTree tStackBTree;
                tStackBTree.bTreeNode = tmpStackBTree->bTreeNode->rChild;
                //入栈
                s.push(tStackBTree);
            }
            //左子树不为空--后序遍历后从左子树入栈.
            if (tmpStackBTree->bTreeNode->lChild!= NULL)
            {
                StactBTree tStackBTree;
                tStackBTree.bTreeNode = tmpStackBTree->bTreeNode->lChild;
                //入栈
                s.push(tStackBTree);
            } 
            tmpStackBTree = &(s.top());//取得栈顶元素
        }
        //出栈操作
        StactBTree *popStackBTree = &(s.top());
        cout<<popStackBTree->bTreeNode->data;
        s.pop();//出栈
    }
    return 0;
}
#endif
// LastOrderBTree.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "listNode.h"
int _tmain(int argc, _TCHAR* argv[])
{
    BTree *root = new BTree();
    InitBTree(root);
    RecursionBackOrder(root);//后序遍历二叉树
    cout<<endl;
    if (0 != BackOrderBTree(root))
        cout<<"输入存在错误"<<endl;
    cout<<endl;
    return 0;
}

执行结果:

4526731
4526731

下面是面试宝典中的代码:

主要思路和我之前的想法基本上一致 首先判断根节点是否为空,若不为空,则该根节点入栈 while循环。只要栈非空 取出栈top元素,判断该元素flag变量是否为2
若为2,则出栈。 否则判断该节点的右孩子是否为空,若不为空,则入栈。再判断左孩子节点是否为空,若不为空,则入栈。

该方法和我之前的方法进行相比,可以发现,该方法要对每个节点flag变量进行两次+1操作,不管左右孩子是否存在。
下面是相关代码:

//非递归实现二叉树后序遍历--该方法是P377中的方法
int lastOrder(BTree *root)
{
    if (root == NULL)
        return -1;
    //将根节点入栈
    StactBTree stackBTree;
    stackBTree.bTreeNode = root;
    stack<StactBTree> s;//栈
    s.push(stackBTree);
    while (s.size()>0)
    {
        StactBTree *topStack = &(s.top());//取栈顶元素
        //flag=2:表示已经访问过该节点的左右孩子节点
        if (topStack->flag == 2)
        {
            cout<<topStack->bTreeNode->data;
            s.pop();//出栈
        }
        else
        {
            StactBTree tmpStackBTree;
            //右孩子节点存在--入栈
            if (topStack->bTreeNode->rChild != NULL)
            {
                tmpStackBTree.bTreeNode = topStack->bTreeNode->rChild;
                s.push(tmpStackBTree);
            }
            topStack->flag++;
            //左孩子节点存在--入栈
            if (topStack->bTreeNode->lChild != NULL)
            {
                tmpStackBTree.bTreeNode = topStack->bTreeNode->lChild;
                s.push(tmpStackBTree); 
            }
            topStack->flag++;
        }
    }
    cout<<endl;
    return 1;
}
先序遍历

递归实现先序、中序与后续遍历的方法是相同的。代码如下

//递归实现先序遍历二叉树
void RecursionPreOrder(BTree *root)
{
    if (root == NULL)
        return;
    cout<<root->data;
    if (root->lChild != NULL)
        RecursionPreOrder(root->lChild);
    if (root->rChild != NULL)
        RecursionPreOrder(root->rChild);
}

非递归实现先序遍历二叉树思路(首先说明不用对访问过的节点进行标记):

当当前节点不为NULL或者栈不为空,进入循环–0

当当前节点不为NULL时–1 对当前节点数据进行处理–2 若左孩子存在,左孩子入栈;当前节点为左孩子节点

转到1

当栈不为空时

取栈顶元素,出栈 当前节点等于右孩子节点 转到0

以上方法不用对访问过的节点进行标记,下面是相关代码:

//非递归实现先序遍历二叉树
int PreOrderBook(BTree* root)
{
    if (root ==NULL)
        return -1;
    stack<BTree*> s;
    BTree* stackBTree = root;
    BTree* tmpBTree;
    while (stackBTree!=NULL || s.size()>0)
    {
        while (stackBTree!=NULL)
        {
            cout<<stackBTree->data;
            s.push(stackBTree);
            stackBTree = stackBTree->lChild;//查看左孩子
        }
        if (s.size()>0)
        {
            stackBTree = s.top();//取栈顶元素
            s.pop();//出栈
            stackBTree = stackBTree->rChild;
        }
    }
    cout<<endl;
    return 0;
}
//非递归实现先序遍历二叉树
int PreOrder(BTree *root)
{
    if (root == NULL)
        return -1;
    stack<BTree*> s;
    s.push(root);//根节点入栈
    while (s.size()>0)
    {
        //取栈定元素
        BTree* topStackBTree = s.top();
        //先序遍历--栈定元素出栈
        cout<<topStackBTree->data;
        s.pop();
        if (topStackBTree->rChild!=NULL)
        {
            s.push(topStackBTree->rChild);
        }
        if (topStackBTree->lChild!=NULL)
        {
            s.push(topStackBTree->lChild);
        }
    }
    cout<<endl;
    return 0;
}

上面代码中,第二种方式是直接对栈进行判断的方式:

首先判断根节点是否为空,若不空则将根节点入栈 当栈非空时进入循环
去栈顶元素,对数据进行处理,并保存当前栈顶元素的地址 将栈顶元素出栈 若存在右孩子,则右孩子入栈 若存在左孩子,则左孩子入栈 循环结束

中序遍历
递归实现中序遍历:

//递归实现中序遍历二叉树
void RecursionMidOrder(BTree *root)
{
    if (root == NULL)
        return;
    if (root->lChild != NULL)
        RecursionMidOrder(root->lChild);
    cout<<root->data;
    if (root->rChild != NULL)
        RecursionMidOrder(root->rChild);
}

非递归实现中序遍历:

判断根节点是否为空,若不为空,将根节点作为当前节点 若当前节点非空或者栈非空,则进入while循环
若当前节点非空时,进入while循环
若左孩子节点存在,则将左孩子入栈,并将左孩子设为当前节点 若左孩子节点不存在,跳出while循环 若栈非空时,进入if循环
取栈顶元素,对元素进行相关处理,保存栈顶元素的地址然后栈顶元素出栈 将右孩子节点设为当前节点 结束
//非递归实现中序遍历二叉树
int MidOrder(BTree* root)
{
    if (root ==NULL)
        return -1;
 
    stack<BTree*> s;
    BTree* stackBTree = root;
 
    BTree* tmpBTree;
    while (stackBTree!=NULL || s.size()>0)
    {
        tmpBTree = NULL;
        while (stackBTree!=NULL)
        {
            s.push(stackBTree);
            stackBTree = stackBTree->lChild;//查看左孩子
        }
 
        if (s.size()>0)
        {
            tmpBTree = s.top();//取栈顶元素
            cout<<tmpBTree->data;
            s.pop();//出栈
 
            stackBTree = tmpBTree->rChild;
        }
    }
 
    cout<<endl;
 
    return 0;
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹