树的操作（构造，遍历，求高度，查找）非递归
2018-07-20 来源：open-open
// BTree1.cpp : 定义控制台应用程序的入口点
//1.使用广义表构造二叉树
//2.程序默认数据为：a(b(c,d),e(,f))
//3.三种遍历使用非递归，求树的高度、查找节点使用递归
#include "stdafx.h"
#include<iostream>
#include<stack>
using namespace std;
#define ElemType char
#define Status int
#define OK 0
#define ERROR 1
#define MAX_LEN 100
typedef struct BTnode
{
ElemType date;
BTnode *lchild,*rchild;
}BTnode,*BTree;
typedef enum{L,R} tagtype;
typedef struct
{
BTree ptr;
tagtype tag;
}stacknode;
Status creat(BTree &T,char *str);//根据str创建二叉树T
Status visit(BTree e);//访问节点，打印date
Status preorder(BTree T);//先序遍历，非递归
Status inorder(BTree T);//中序遍历，非递归
Status postorder(BTree T);//后序遍历，非递归
Status getTreeHeight(BTree T,int &H);//求树的高度，递归
Status findNode(BTree T,ElemType e,BTnode &bt);//求树中结点data值为e的节点，并返回此节点的引用
int _tmain(int argc, _TCHAR* argv[])
{
int i,height,flag;
BTree T;
BTnode bt;
char *buffer,e;
printf("想输入自己的数据请输入--1or采用默认数据请输入--2：");
cin>>flag;
if(flag==1)
{
buffer=(char*)malloc(MAX_LEN*sizeof(char));
scanf("%s",buffer);
}
else if(flag==2)
buffer="a(b(c,d),e(,f))";
T=NULL;
creat(T,buffer);//创建树
//先序遍历
printf("先序遍历:");
preorder(T);
//中序遍历
printf("\n中序遍历:");
inorder(T);
//后序遍历
printf("\n后序遍历:");
postorder(T);
//求树的高度
height=0;
getTreeHeight(T,height);
printf("\n此树的高度为：%d\n",height);
//查找date值为e的节点并返回节点的引用
printf("请输入要查找的字符值：");
cin>>e;
findNode(T,e,bt);
if(bt.date==NULL)
printf("未找到");
else
printf("找到他了：%c",bt.date);
printf("\n");
system("pause");
return 0;
}
Status creat(BTree &T,char *str)//初始T=NULL
{
char *ch;
int flag=0;
BTree p;
stack<BTnode *> Stack; //实例化栈
p=NULL;
ch=str;
while((*ch)!='\0')
{
switch(*ch)
{
case'(':
Stack.push(p);
flag=1;
break;
case',':
flag=2;
break;
case')':
Stack.pop();
break;
default://对字符的处理
p=(BTree)malloc(sizeof(BTnode));
p->date=*ch;
p->lchild=p->rchild=NULL;
if(T==NULL)
T=p;
else
{
if(flag==1)
Stack.top()->lchild=p;
if(flag==2)
Stack.top()->rchild=p;
}
}
ch++;
}
return OK;
}
Status visit(BTree e)
{
printf("%c",e->date);
return OK;
}
Status preorder(BTree T)
{
BTree p;
stack<BTnode *> Stack;
p=T;
Stack.push(NULL);
while(p!=NULL)
{
visit(p);//访问节点
if(p->rchild!=NULL)//如果有右孩子，此右孩子节点进栈，
Stack.push(p->rchild);
if(p->lchild!=NULL)//向左移动
p=p->lchild;
else//左孩子已访问过，p=根—>rchild
{
p=Stack.top();
Stack.pop();
}
}
return OK;
}
Status inorder(BTree T)
{
BTree p;
p=NULL;
stack<BTree> Stack;//实例化栈
Stack.push(T);//根节点进栈
while(!Stack.empty())
{
while(Stack.top()!=NULL)//一路向左，至最左
Stack.push(Stack.top()->lchild);
Stack.pop();//空指针弹出
if(!Stack.empty())
{
p=Stack.top();
Stack.pop();
visit(p);
Stack.push(p->rchild);//向右移动
}
}
return OK;
}
Status postorder(BTree T)
{
stack<stacknode> Stack;
stacknode S;
BTree p;
p=T;
do
{
while(p!=NULL)//一路向左，进栈，至最左
{
S.ptr=p;
S.tag=L;
Stack.push(S);
p=p->lchild;
}
while(!Stack.empty()&&Stack.top().tag==R)
{
S=Stack.top();
Stack.pop();
p=S.ptr;
visit(p); //tag为R，表示右子树访问完毕，故访问根结点
}
if(!Stack.empty())//向右移一个
{
Stack.top().tag=R;
p=Stack.top().ptr->rchild;
}
}while(!Stack.empty());
return OK;
}
Status getTreeHeight(BTree T,int &H)
{
//递归，分别计算左、右子树的高度，后比较较大者，+1
int lchildH,rchildH;
lchildH=rchildH=0;//左右子树高度，初始化
if(T==NULL)
H=0;
else
{
getTreeHeight(T->lchild,lchildH);//计算左子树的高度
getTreeHeight(T->rchild,rchildH);//计算右子树的高度
if(lchildH>rchildH)
H=lchildH+1;
else
H=rchildH+1;
}
return OK;
}
Status findNode(BTree T,ElemType e,BTnode &bt)
{
if(T==NULL)//当前BTree为空
{
bt.date=NULL;
return ERROR;
}
else if(T->date==e)//找到，当前节点符合
bt=*T;
else
{
findNode(T->lchild,e,bt);//在左子树中寻找
if(bt.date==NULL)
findNode(T->rchild,e,bt);//在右子树中寻找
}
return OK;
}
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。
最新资讯
热门推荐