首先创建二叉树,然后对二叉树遍历进行了单元测试。只要将相应的注释取消,便可以成功运行。
/********************************************
二叉树遍历前序、中序、后序的递归和非递归实现
********************************************/
#include<stdio.h>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
//创建二叉树节点
BinaryTreeNode* createBinaryTreeNode(int value)
{
BinaryTreeNode* pNode = new BinaryTreeNode();
pNode->m_nValue = value;
pNode->m_pRight = NULL;
pNode->m_pLeft = NULL;
return pNode;
}
//连接二叉树节点
void connectBinaryTreeNode(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight)
{
if(pParent != NULL){
pParent->m_pLeft = pLeft;
pParent->m_pRight = pRight;
}
}
//销毁二叉树
void destoryBinaryTree(BinaryTreeNode* pRoot)
{
if(pRoot != NULL)
{
BinaryTreeNode* pLeft = pRoot->m_pLeft;
BinaryTreeNode* pRight = pRoot->m_pRight;
delete pRoot;
destoryBinaryTree(pLeft);
destoryBinaryTree(pRight);
}
}
/**********************************
//前序遍历,递归实现
void preOrder(BinaryTreeNode* pRoot)
{
if(pRoot)
{
printf("%d\n",pRoot->m_nValue);
preOrder(pRoot->m_pLeft);
preOrder(pRoot->m_pRight);
}
}
***********************************/
/****************************************
//前序遍历,非递归实现
void preOrder(BinaryTreeNode* pRoot)
{
if(pRoot)
{
stack<BinaryTreeNode*> btnStack;
while(pRoot || !btnStack.empty())
{
if(pRoot)
{
printf("%d\t",pRoot->m_nValue);
btnStack.push(pRoot);
pRoot = pRoot->m_pLeft;
}
else
{
pRoot = btnStack.top();
btnStack.pop();
pRoot = pRoot->m_pRight;
}
}
}
}
*********************************************/
/*******************************************
//中序遍历,递归实现
void midOrder(BinaryTreeNode* pRoot)
{
if(pRoot)
{
midOrder(pRoot->m_pLeft);
printf("%d\t",pRoot->m_nValue);
midOrder(pRoot->m_pRight);
}
}
*******************************************/
/*******************************************
//中序遍历,非递归实现
void midOrder(BinaryTreeNode* pRoot)
{
if(pRoot)
{
stack<BinaryTreeNode*> btnStack;
while(pRoot || !btnStack.empty())
{
if(pRoot)
{
btnStack.push(pRoot);
pRoot = pRoot->m_pLeft;
}
else
{
pRoot = btnStack.top();
printf("%d\t",pRoot->m_nValue);
btnStack.pop();
pRoot = pRoot->m_pRight;
}
}
}
}
**********************************************
/******************************************
//后序遍历,递归实现
void postOrder(BinaryTreeNode* pRoot)
{
if(pRoot)
{
postOrder(pRoot->m_pLeft);
postOrder(pRoot->m_pRight);
printf("%d\t",pRoot->m_nValue);
}
}
******************************************/
//后序遍历,非递归实现
void postOrder(BinaryTreeNode* pRoot)
{
if(pRoot)
{
stack<BinaryTreeNode*> btnStack;
btnStack.push(pRoot);
BinaryTreeNode* pPreNode = NULL; //前一次访问的节点
while(!btnStack.empty())
{
pRoot = btnStack.top();
if((!pRoot->m_pLeft && !pRoot->m_pRight) //叶子节点或
|| (pPreNode && ((pPreNode==pRoot->m_pLeft)
||(pPreNode==pRoot->m_pRight))))//左右子节点都已经访问过的节点
{
printf("%d\t",pRoot->m_nValue);
pPreNode = pRoot;
btnStack.pop();
}
else
{
if(pRoot->m_pRight) //空节点不入栈
btnStack.push(pRoot->m_pRight); //将后访问的节点先入栈
if(pRoot->m_pLeft)
btnStack.push(pRoot->m_pLeft);
}
}
}
}
//单元测试
//两边都有树枝
/*
10
/ \
6 14
/ \ / \
4 8 12 16
*/
void test1()
{
BinaryTreeNode* pNode1 = createBinaryTreeNode(10);
BinaryTreeNode* pNode2 = createBinaryTreeNode(6);
BinaryTreeNode* pNode3 = createBinaryTreeNode(14);
BinaryTreeNode* pNode4 = createBinaryTreeNode(4);
BinaryTreeNode* pNode5 = createBinaryTreeNode(8);
BinaryTreeNode* pNode6 = createBinaryTreeNode(12);
BinaryTreeNode* pNode7 = createBinaryTreeNode(16);
connectBinaryTreeNode(pNode1,pNode2,pNode3);
connectBinaryTreeNode(pNode2,pNode4,pNode5);
connectBinaryTreeNode(pNode3,pNode6,pNode7);
//preOrder(pNode1);
//midOrder(pNode1);
postOrder(pNode1);
destoryBinaryTree(pNode1);
}
//左边有树枝
/*
10
/
6
/ \
14 4
*/
void test2()
{
BinaryTreeNode* pNode1 = createBinaryTreeNode(10);
BinaryTreeNode* pNode2 = createBinaryTreeNode(6);
BinaryTreeNode* pNode3 = createBinaryTreeNode(14);
BinaryTreeNode* pNode4 = createBinaryTreeNode(4);
connectBinaryTreeNode(pNode1,pNode2,NULL);
connectBinaryTreeNode(pNode2,pNode3,pNode4);
//preOrder(pNode1);
//midOrder(pNode1);
postOrder(pNode1);
destoryBinaryTree(pNode1);
}
//右边有树枝
/*
10
\
6
/ \
14 4
*/
void test3()
{
BinaryTreeNode* pNode1 = createBinaryTreeNode(10);
BinaryTreeNode* pNode2 = createBinaryTreeNode(6);
BinaryTreeNode* pNode3 = createBinaryTreeNode(14);
BinaryTreeNode* pNode4 = createBinaryTreeNode(4);
connectBinaryTreeNode(pNode1,NULL,pNode2);
connectBinaryTreeNode(pNode2,pNode3,pNode4);
//preOrder(pNode1);
//midOrder(pNode1);
postOrder(pNode1);
destoryBinaryTree(pNode1);
}
//只有根节点
void test4()
{
BinaryTreeNode* pNode1 = createBinaryTreeNode(10);
//preOrder(pNode1);
//midOrder(pNode1);
postOrder(pNode1);
destoryBinaryTree(pNode1);
}
//空树
void test5()
{
//preOrder(NULL);
//midOrder(NULL);
postOrder(NULL);
}
int main()
{
test1();
printf("\n");
test2();
printf("\n");
test3();
printf("\n");
test4();
printf("\n");
test5();
return 0;
}
==转载请注明出处,谢谢!
分享到:
相关推荐
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
数据结构试验报告用先序中序建立二叉树后序遍历非递归.pdf
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
数据结构中关于二叉树的遍历,非递归算法数上未给出
二叉树.非递归算法.先序遍历.中序遍历.后序遍历.doc
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历、计算叶子节点数目和所有节点数目,使用队列实现二叉树的层次遍历.zip
二叉树先序、中序、后序三种遍历的非递归算法
二叉树的先序中序后序遍历 有递归与非递归两中做法
遍历二叉树 MFC 先序 中序 后序 非递归 实现创建并遍历二叉树
二叉树的遍历 (先序、后序、中序、非递归、递归)
从键盘输入二叉树的各结点... 2 )分别实现先序、中序、后序递归遍历二叉树 3 )输出二叉树的高度 4 )输出二叉树的按层次遍历序列 5 )输出二叉树的先序非递归遍历下的结点访问次序 6 )以菜单方式运行
数据结构中二叉树的先序遍历,中序遍历,后续遍历的递归和非递归的算法
(1)输入字符序列,建立二叉链表 (2)中序遍历二叉树:递归 (3)中序遍历二叉树:非递归 (3)二叉树高度
建立二叉树,以括号表示法输出二叉树,求二叉树的先序遍历,中序遍历,后序遍历输出~~~
二叉树先序、中序、后序遍历(递归、非递归算法) 其中自己已经开发了栈!
本程序采用非递归方法实现对二叉树的先序、中序、后序遍历.自定义栈和树的结构。
采用二叉链表存储先序建立二叉树,非递归中序遍历二叉树算法实现