您所在位置：主题：二叉树非遍历递归算法
**雪纷飞**
[专家分：0] 发布于 2008-12-16 20:53:00
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include "../stackhead.h"
void Menu_name()
{//作者信息
printf("\n\n\n\n\n\n\n");
printf(" *************************************************\n");
printf(" 二叉树前、中、后序非递归遍历\n\n");
printf(" 制作:董蓉蓉\n");
printf(" 班级:电子商务0702班\n");
printf(" 学号: 0709040231\n");
printf(" 指导老师:孙夫雄\n");
printf(" **************************************************\n");
printf("\n\n\n\t\t");
}
void PreOrderN(BinaryTreeNode *BT)
{//二叉树前序遍历非递归算法
Stack S;
BinaryTreeNode *p=BT;
CreatStack (S);
while (p||!IsEmpty(S))
{if(p)
{
cout<<p->data<<" ";
Push(S,p);
p=p->LChild;
}
else
if (!IsEmpty(S))
{
Pop(S,p);
p=p->RChild;
}
}
}
void InOrderN(BinaryTreeNode *BT)
{//二叉树中序遍历非递归算法
Stack S;
BinaryTreeNode *p=BT;
CreatStack (S);
do
{
while(p)
{
Push (S,p);
p=p->LChild;
}
if(!IsEmpty(S))
{
Pop(S,p);
cout<<p->data<<" ";
p=p->RChild;
}
}
while((p)||!IsEmpty(S));
}
void PostOrderN(BinaryTreeNode *BT)
{//二叉树后序遍历非递归算法
Stack S;
BinaryTreeNode *p=BT;
CreatStack (S);
SType temp;
while ((p||!IsEmpty(S)))
if (p) //找最左子树
{
temp.B=false;
temp.ptr=p;
Push (S,temp);
p=p->LChild;
}
else
if(!IsEmpty(S)) //左子树为空时,利用堆栈回朔
{
Pop(S,temp);
p=temp.ptr;
if(temp.B)
{
cout<<p->data<<" ";
p=NULL; //将p设为空的目的是为强制退栈作准备
}
else
{
temp.B=true; //改变进栈标志,准备重新进栈
Push(S,temp);
p=p->RChild;
}
}
}
char re_choose[]={"\n选择非法，请输入正确的编号...\n"};
BinaryTreeNode *treeNode[9];
void main_switch(char j)
//操作选择函数
{
int i;
char data[100];
switch(j)
{
case '1' ://构造一个10结点的二叉树
char k='A';
for(i=0;i<10;i++)
{
printf("请输入第%d个整数:\t", i+1);
scanf("%d",&k);
treeNode[i]=MakeNode(k);
k++;
}
MakeBinaryTree(treeNode[0],treeNode[1],treeNode[2]);//A:B(L) , NULL(R)
MakeBinaryTree(treeNode[1],treeNode[3],treeNode[4]);//B:c(L) , d(R)
MakeBinaryTree(treeNode[2],treeNode[5],treeNode[6]);//D:NULL(L) , E(R)
MakeBinaryTree(treeNode[4],treeNode[7],treeNode[8]);
MakeBinaryTree(treeNode[6],NULL,treeNode[9]);
case '2' ://显示二叉树的结构
system("cls");
printf("二叉树的结构:\n");
printf("\t\tA\n");
printf("\t\t├───┐\n");
printf("\t\tB C\n");
printf("\t\t├─┐ ├─┐ \n");
printf("\t\tD E F G \n");
printf("\t\t ├─┐ └─┐\n");
printf("\t\t H I J\n");
system("pause");
system("cls");
break;
case '3'://二叉树的前序遍历非递归算法
system("cls");
PreOrderN(treeNode[0]);
printf("\n");
system("pause");
system("cls");
break;
case '4'://二叉树的中序遍历非递归算法
system("cls");
InOrderN(treeNode[0]);
printf("\n");
system("pause");
system("cls");
break;
case '5'://二叉树的后序遍历非递归算法
system("cls");
PostOrderN(treeNode[0]);
printf("\n");
system("pause");
system("cls");
break;
case '0':
exit(0);
break;
default :
cout <<re_choose<<endl;
system("pause");
system("cls");
break;
}//end switch
}
void Menu() //菜单函数
{
cout <<"\n\n\t\t"<<"=========二叉树前序、中序、后序非递归遍历==========="<<endl;
cout <<"\n\t\t"<<" 请选择以下一个功能:"<<endl;
cout <<"\n\t\t"<<" 1.构造一个二叉树."<<endl;
cout <<"\n\t\t"<<" 2.显示二叉树的结构."<<endl;
cout <<"\t\t 3.二叉树前序非递归遍历. " << endl;
cout <<"\t\t 4.二叉树中序非递归遍历." << endl;
cout <<"\t\t 5.二叉树后序非递归遍历." << endl;
cout <<"\t\t 0.退出.\n"<<endl;
cout <<"\t\t====================================================\n"<<endl;
}
int main()
{
char a[100];
system("cls");
Menu_name();
system("pause");
system("cls");
while(1)
{ system("cls");
Menu();
printf("\n\t请输入功能编号:");
gets(a);
if(a[1]!='\0')
{ cout <<"\n"<<re_choose<<endl;
system("pause");
system("cls");
continue;
}
else
{ if(a[0]=='0')
break;
main_switch(a[0]);
}
}
return 0;
}
程序编译后提示：
:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(29) : error C2664: 'Push' : cannot convert parameter 2 from 'struct TreeNode *' to 'SType &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(35) : error C2664: 'Pop' : cannot convert parameter 2 from 'struct TreeNode *' to 'SType &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(50) : error C2664: 'Push' : cannot convert parameter 2 from 'struct TreeNode *' to 'SType &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(55) : error C2664: 'Pop' : cannot convert parameter 2 from 'struct TreeNode *' to 'SType &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(113) : error C2664: 'MakeNode' : cannot convert parameter 1 from 'char' to 'int &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(125) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(142) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(150) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(158) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(166) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(169) : error C2361: initialization of 'k' is skipped by 'default' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
执行 cl.exe 时出错.
实验2.obj - 1 error(s), 0 warning(s)
#include <stdio.h>
#include <iostream.h>
#include "../stackhead.h"
void Menu_name()
{//作者信息
printf("\n\n\n\n\n\n\n");
printf(" *************************************************\n");
printf(" 二叉树前、中、后序非递归遍历\n\n");
printf(" 制作:董蓉蓉\n");
printf(" 班级:电子商务0702班\n");
printf(" 学号: 0709040231\n");
printf(" 指导老师:孙夫雄\n");
printf(" **************************************************\n");
printf("\n\n\n\t\t");
}
void PreOrderN(BinaryTreeNode *BT)
{//二叉树前序遍历非递归算法
Stack S;
BinaryTreeNode *p=BT;
CreatStack (S);
while (p||!IsEmpty(S))
{if(p)
{
cout<<p->data<<" ";
Push(S,p);
p=p->LChild;
}
else
if (!IsEmpty(S))
{
Pop(S,p);
p=p->RChild;
}
}
}
void InOrderN(BinaryTreeNode *BT)
{//二叉树中序遍历非递归算法
Stack S;
BinaryTreeNode *p=BT;
CreatStack (S);
do
{
while(p)
{
Push (S,p);
p=p->LChild;
}
if(!IsEmpty(S))
{
Pop(S,p);
cout<<p->data<<" ";
p=p->RChild;
}
}
while((p)||!IsEmpty(S));
}
void PostOrderN(BinaryTreeNode *BT)
{//二叉树后序遍历非递归算法
Stack S;
BinaryTreeNode *p=BT;
CreatStack (S);
SType temp;
while ((p||!IsEmpty(S)))
if (p) //找最左子树
{
temp.B=false;
temp.ptr=p;
Push (S,temp);
p=p->LChild;
}
else
if(!IsEmpty(S)) //左子树为空时,利用堆栈回朔
{
Pop(S,temp);
p=temp.ptr;
if(temp.B)
{
cout<<p->data<<" ";
p=NULL; //将p设为空的目的是为强制退栈作准备
}
else
{
temp.B=true; //改变进栈标志,准备重新进栈
Push(S,temp);
p=p->RChild;
}
}
}
char re_choose[]={"\n选择非法，请输入正确的编号...\n"};
BinaryTreeNode *treeNode[9];
void main_switch(char j)
//操作选择函数
{
int i;
char data[100];
switch(j)
{
case '1' ://构造一个10结点的二叉树
char k='A';
for(i=0;i<10;i++)
{
printf("请输入第%d个整数:\t", i+1);
scanf("%d",&k);
treeNode[i]=MakeNode(k);
k++;
}
MakeBinaryTree(treeNode[0],treeNode[1],treeNode[2]);//A:B(L) , NULL(R)
MakeBinaryTree(treeNode[1],treeNode[3],treeNode[4]);//B:c(L) , d(R)
MakeBinaryTree(treeNode[2],treeNode[5],treeNode[6]);//D:NULL(L) , E(R)
MakeBinaryTree(treeNode[4],treeNode[7],treeNode[8]);
MakeBinaryTree(treeNode[6],NULL,treeNode[9]);
case '2' ://显示二叉树的结构
system("cls");
printf("二叉树的结构:\n");
printf("\t\tA\n");
printf("\t\t├───┐\n");
printf("\t\tB C\n");
printf("\t\t├─┐ ├─┐ \n");
printf("\t\tD E F G \n");
printf("\t\t ├─┐ └─┐\n");
printf("\t\t H I J\n");
system("pause");
system("cls");
break;
case '3'://二叉树的前序遍历非递归算法
system("cls");
PreOrderN(treeNode[0]);
printf("\n");
system("pause");
system("cls");
break;
case '4'://二叉树的中序遍历非递归算法
system("cls");
InOrderN(treeNode[0]);
printf("\n");
system("pause");
system("cls");
break;
case '5'://二叉树的后序遍历非递归算法
system("cls");
PostOrderN(treeNode[0]);
printf("\n");
system("pause");
system("cls");
break;
case '0':
exit(0);
break;
default :
cout <<re_choose<<endl;
system("pause");
system("cls");
break;
}//end switch
}
void Menu() //菜单函数
{
cout <<"\n\n\t\t"<<"=========二叉树前序、中序、后序非递归遍历==========="<<endl;
cout <<"\n\t\t"<<" 请选择以下一个功能:"<<endl;
cout <<"\n\t\t"<<" 1.构造一个二叉树."<<endl;
cout <<"\n\t\t"<<" 2.显示二叉树的结构."<<endl;
cout <<"\t\t 3.二叉树前序非递归遍历. " << endl;
cout <<"\t\t 4.二叉树中序非递归遍历." << endl;
cout <<"\t\t 5.二叉树后序非递归遍历." << endl;
cout <<"\t\t 0.退出.\n"<<endl;
cout <<"\t\t====================================================\n"<<endl;
}
int main()
{
char a[100];
system("cls");
Menu_name();
system("pause");
system("cls");
while(1)
{ system("cls");
Menu();
printf("\n\t请输入功能编号:");
gets(a);
if(a[1]!='\0')
{ cout <<"\n"<<re_choose<<endl;
system("pause");
system("cls");
continue;
}
else
{ if(a[0]=='0')
break;
main_switch(a[0]);
}
}
return 0;
}
程序编译后提示：
:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(29) : error C2664: 'Push' : cannot convert parameter 2 from 'struct TreeNode *' to 'SType &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(35) : error C2664: 'Pop' : cannot convert parameter 2 from 'struct TreeNode *' to 'SType &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(50) : error C2664: 'Push' : cannot convert parameter 2 from 'struct TreeNode *' to 'SType &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(55) : error C2664: 'Pop' : cannot convert parameter 2 from 'struct TreeNode *' to 'SType &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(113) : error C2664: 'MakeNode' : cannot convert parameter 1 from 'char' to 'int &'
A reference that is not to 'const' cannot be bound to a non-lvalue
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(125) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(142) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(150) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(158) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(166) : error C2360: initialization of 'k' is skipped by 'case' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(169) : error C2361: initialization of 'k' is skipped by 'default' label
c:\documents and settings\administrator\桌面\实验\实验2\实验2.cpp(107) : see declaration of 'k'
执行 cl.exe 时出错.
实验2.obj - 1 error(s), 0 warning(s)