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

2018-02-05 10:39:05来源:网络收集作者:程序诗人人点击

分享

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

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


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


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

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


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

下面是实现代码:


#pragma once
#ifndef LISTNODE_H
#define LISTNODE_H
#include
#include
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<data;若在此处处理数据则是先序遍历
if (root->lChild != NULL)
RecursionBackOrder(root->lChild);
//cout<data;若在此处处理数据则是中序遍历
if (root->rChild != NULL)
RecursionBackOrder(root->rChild);
cout<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 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<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<if (0 != BackOrderBTree(root))
cout<<"输入存在错误"<cout<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 s;//栈
s.push(stackBTree);
while (s.size()>0)
{
StactBTree *topStack = &(s.top());//取栈顶元素
//flag=2:表示已经访问过该节点的左右孩子节点
if (topStack->flag == 2)
{
cout<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<return 1;
}
先序遍历

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


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

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


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

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


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

非递归实现中序遍历:


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

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台