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

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

#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循环。只要栈非空

//非递归实现二叉树后序遍历--该方法是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);
}

//非递归实现先序遍历二叉树
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);
}

//非递归实现中序遍历二叉树
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;
}