c++ 二叉查找树 非递归（先序、中序、后序）遍历

c++ 二叉查找树 非递归（先序、中序、后序）遍历

关键词： c++ 二叉查找树 非递归（先序、中序、后序）遍历

<smarttagtype name="RTX" namespaceuri="Tencent"><!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Author>FtpDown</o:Author> <o:LastAuthor>FtpDown</o:LastAuthor> <o:Revision>4</o:Revision> <o:TotalTime>16</o:TotalTime> <o:Created>2006-06-04T07:11:00Z</o:Created> <o:LastSaved>2006-06-04T07:12:00Z</o:LastSaved> <o:Pages>1</o:Pages> <o:Words>505</o:Words> <o:Characters>2884</o:Characters> <o:Company>www.ftpdown.com</o:Company> <o:Lines>24</o:Lines> <o:Paragraphs>6</o:Paragraphs> <o:CharactersWithSpaces>3383</o:CharactersWithSpaces> <o:Version>11.5606</o:Version> </o:DocumentProperties> </xml><![endif]--><!--[if gte mso 9]><xml> <w:WordDocument> <w:SpellingState>Clean</w:SpellingState> <w:GrammarState>Clean</w:GrammarState> <w:PunctuationKerning /> <w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing> <w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery> <w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery> <w:ValidateAgainstSchemas /> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:Compatibility> <w:SpaceForUL /> <w:BalanceSingleByteDoubleByteWidth /> <w:DoNotLeaveBackslashAlone /> <w:ULTrailSpace /> <w:DoNotExpandShiftReturn /> <w:AdjustLineHeightInTable /> <w:BreakWrappedTables /> <w:SnapToGridInCell /> <w:WrapTextWithPunct /> <w:UseAsianBreakRules /> <w:DontGrowAutofit /> <w:UseFELayout /> </w:Compatibility> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> </w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" LatentStyleCount="156"> </w:LatentStyles> </xml><![endif]--><!--[if !mso]>< classid="clsid:38481807-CA0E-42D2-BF39-B33AF135CC4D" id=ieooui></object> <style> st1\:*{behavior:url(#ieooui) } </style> <![endif]--><!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;} </style> <![endif]--><!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="2050" /> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1" /> </o:shapelayout></xml><![endif]--></smarttagtype>

#include <iostream.h>

#include <malloc.h>

#include <stack>

#include <list>

using namespace std;

typedef int ElemType;

typedef struct treeT

{

ElemType key;

struct treeT* left;

struct treeT* right;

}treeT, *pTreeT;

class BITree{

public:

pTreeT Insert(ElemType target, pTreeT* <rtx w:st="on"><span class="SpellE">pp</span></rtx>Tree);

void PreOrder(pTreeT root);

void lev_Order(pTreeT);

void InOrderNoRec(pTreeT root);

void PreOrderNoRec(pTreeT root);

void PosOrderNoRec(pTreeT root);

};

;

pTreeT BITree::Insert(ElemType target, pTreeT* <rtx w:st="on"><span class="SpellE">pp</span></rtx>Tree)

{

pTreeT Node;

Node = *<rtx w:st="on"><span class="SpellE">pp</span></rtx>Tree;

if (NULL == Node)

{

Node=(pTreeT)malloc(sizeof(treeT));

Node->key = target;

Node->left = NULL;

Node->right = NULL;

*<rtx w:st="on"><span class="SpellE">pp</span></rtx>Tree=Node;

return *<rtx w:st="on"><span class="SpellE">pp</span></rtx>Tree ;

}

if (Node->key == target) //不允许出现相同的元素

{

return NULL;

}

else if (Node->key > target) //向左

{

return Insert(target, &Node->left);

}

else

{

return Insert(target, &Node->right);

}

}

void BITree::PreOrder(pTreeT root)

{

if(root!=NULL)

{

cout<<root->key<<",";

PreOrder(root->left);

PreOrder(root->right);

}

}

void BITree::lev_Order(pTreeT root)

{

list<pTreeT> list1;

pTreeT p;

list1.push_back(root);

while(!list1.empty())

{

p=(pTreeT)list1.front();

list1.pop_front();

cout<<p->key<<",";

if(p->left!=NULL)

list1.push_back(p->left);

if(p->right!=NULL)

list1.push_back(p->right);

}

}

void BITree::InOrderNoRec(pTreeT root)

{

stack<pTreeT > s;

while ((NULL != root) || !s.empty())

{

if (NULL != root)

{

s.push(root);

root = root->left;

}

else

{

root = s.top();

cout<<root->key<<",";

s.pop();

root = root->right;

}

}

}

void BITree::PreOrderNoRec(pTreeT root)

{

stack<pTreeT > s;

while ((NULL != root) || !s.empty())

{

if (NULL != root)

{

cout<<root->key<<",";

s.push(root);

root = root->left;

}

else

{

root = s.top();

s.pop();

root = root->right;

}

}

}

void BITree::PosOrderNoRec(pTreeT root)

{

stack<pTreeT> st;

pTreeT p = root;

pTreeT pre = NULL;//pre表示最近一次访问的结点

while(p || st.size()!=0)

{

//沿着左孩子方向走到最左下 。

while(p)

{

st.push(p);

p = p->left;

}

//get the top element of the stack

p = st.top();

//如果p没有右孩子或者其右孩子刚刚被访问过

if(p->right == NULL || p->right == pre)

{

//visit this element and then pop it

cout<< p->key<<",";

st.pop();

pre = p;

p = NULL;

}

else

{

p = p->right;

}

}

}

测试代码：

#include <iostream.h>

#include "Tree.h"

#include <malloc.h>

#include <assert.h>

void main()

{

BITree bitree;

//int i;

pTreeT root = NULL;

bitree.Insert(10, &root);

bitree.Insert(8, &root);

bitree.Insert(7, &root);

bitree.Insert(9, &root);

bitree.Insert(12, &root);

bitree.Insert(11, &root);

bitree.Insert(13, &root);

//递归先序遍历

cout<<"递归先序遍历"<<endl;

bitree.PreOrder(root);

//层次遍历（队列实现）

cout<<endl<<"层次遍历（队列实现）"<<endl;

bitree.lev_Order(root);

//非递归先序遍历

cout<<endl<<"非递归先序遍历"<<endl;

bitree.PreOrderNoRec(root);

//非递归中序遍历

cout<<endl<<"非递归中序遍历"<<endl;

bitree.InOrderNoRec(root);

//非递归后序遍历

cout<<endl<<"非递归后序遍历"<<endl;

bitree.PosOrderNoRec(root);

}