二叉排序树的实现_折半查找方法的实现_c二叉树非递归中序遍历(7)

{

pParent=GetParent(pParent->data);

}

pPost=pParent;

}

returnpPost;

}

else

{

cout<<"数值为"<<item<<"的结点不存在！"<<endl;

returnpPost;

}

}

//用栈实现非递归的先序遍历

voidBSTree::PreOrderVisit()

{

PreOrder(root);

}

//用栈实现非递归的先序遍历

voidBSTree::PreOrder(BSNode*root)

{

//定义栈

BSNode*stack[STACK_MAXSIZE];

inttop=0;//top为0表示栈空,指向栈顶的下一个位置

BSNode*p=root;

cout<<"二叉树的先序遍历：";

while(p||(top!=0))//指针不空或栈不空

{

if(p)

{

stack[top++]=p;//入栈

cout<<p->data<<"";//访问该结点

p=p->m_lchild;

}

else

{

p=stack[--top];//出栈

p=p->m_rchild;

}

}

cout<<endl;

}

//用栈实现非递归的中序遍历

voidBSTree::InOrderVisit()

{

InOrder(root);

}

//用栈实现非递归的中序遍历

voidBSTree::InOrder(BSNode*root)

{

//定义栈

BSNode*stack[STACK_MAXSIZE];

inttop=0;//top为0表示栈空,指向栈顶的下一个位置

BSNode*p=root;

cout<<"二叉树的中序遍历：";

while(p||(top!=0))//指针不空或栈不空

{

if(p)

{

stack[top++]=p;//入栈

p=p->m_lchild;

}

else

{

p=stack[--top];//出栈

cout<<p->data<<"";//访问该结点

p=p->m_rchild;

}

}

cout<<endl;

}

//用栈实现非递归的后序遍历,后序遍历较为复杂，需要用到两个栈

voidBSTree::PostOrderVisit()

{

PostOrder(root);

}

//用栈实现非递归的后序遍历,后序遍历较为复杂，需要用到两个栈

voidBSTree::PostOrder(BSNode*root)

{

//定义栈

BSNode*stack1[STACK_MAXSIZE];

BSNode*stack2[STACK_MAXSIZE];

inttop1=0;//top为0表示栈空,指向栈顶的下一个位置

inttop2=0;

BSNode*p=root;

cout<<"二叉树的后序遍历：";

while(p||(top1!=0))//指针不空或栈不空

{

if(p)

{

stack1[top1++]=p;//入栈1

stack2[top2++]=p;//入栈2

p=p->m_rchild;//注意此处是指向右孩子

}

else

{

p=stack1[--top1];//栈1的栈顶元素出栈，栈2元素不出栈

p=p->m_lchild;

}

}

while(top2!=0)

{

p=stack2[--top2];//栈2栈顶元素出栈

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25453-7.html