#include "stdio.h"

#include "malloc.h"

#define maxsize 20 //规定树中结点的最大数目 

#include"windows.h"

typedef struct node{ //定义数据结构

int ltag,rtag; //表示child 域指示该结点是否孩子

char data; //记录结点的数据

struct node *lchild,*rchild; //记录左右孩子的指针

}Bithptr;

Bithptr *Q[maxsize]; //建队，保存已输入的结点的地

址

Bithptr *CreatTree(){ //建树函数，返回根指针

char ch;

int front,rear;

Bithptr *T,*s;

 T=NULL;

front=1;rear=0; //置空二叉树

printf("                       

***********************************\n");

printf("                        *                          

*\n");

printf("                        *         线索

二叉树的运算。      *\n");

printf("                        *                         

*\n");

printf("                       

***********************************\n");

printf("                         请依次输入数据

@表示空结点，以#结束\n");

ch=getchar(); //输入第一个字符

while(ch!='#') //判断是否为结束字符

{

s=NULL;

if(ch!='@') //判断是否为空结点

{

s=(Bithptr *)malloc(sizeof(Bithptr));

s->data=ch;

s->lchild=NULL;

s->rchild=NULL;

s->rtag=0;

s->ltag=0;

}

rear++;

Q[rear]=s; //将结点地址加入队列中

if(rear==1)T=s; //输入为第一个结点为根结点

else

{

if(s!=NULL&&Q[front]!=NULL) //孩子和双亲结点

均不是虚结点

if(rear%2==0)

Q[front]->lchild=s;

else Q[front]->rchild=s;

if(rear%2==1)front++;

}

ch=getchar();

}

return T;

}

void Inorder(Bithptr *T) //中序遍历

{

if(T)

{

if(T->ltag!=1)Inorder(T->lchild);

printf("→%c",T->data);

}

}

Bithptr *pre=NULL;

void PreThread(Bithptr *root) //中序线索化算法??函

数实现

{ 

Bithptr *p;

p=root;

if(p){

PreThread(p->lchild);//线索化左子树

if(pre&&pre->rtag==1)pre->rchild=p; //前驱结点后继线索化

if(p->lchild==NULL)

{

p->ltag=1;

p->lchild=pre;

}

if(p->rchild==NULL) //后继结点前驱线索化

p->rtag=1;

pre=p;

PreThread(p->rchild);

}

} 

void PrintIndex(Bithptr *t) //输出线索

{

Bithptr *f;

f=t;

if(f)

{

if(f->ltag==1&&f->lchild==NULL&&f->rtag==1)

printf(" 【%c 】",f->data);

//如果是第一个结点

if(f->ltag==1&&f->lchild!=NULL) printf("%c→

【%c 】",f->lchild->data,f->data); //如果此结点有前驱就输出前驱和此结点

if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)

printf("→%c",f->rchild->data); //如果此结点有前驱

也有后继??就输出后继

else if(f->rtag==1&&f->rchild!=NULL) printf("

【%c 】→%c",f->data,f->rchild->data);//如果没有前驱??就输出此结点和后继

printf("\n");

if(f->ltag!=1)PrintIndex(f->lchild);

if(f->rtag!=1)PrintIndex(f->rchild);

}

}

 

第二篇：实验报告三 二叉树应用

实验报告三二叉树应用

一、问题描述

1.实验题目：二叉树应用

2.基本要求：用二叉树表示一个表达式，计算二叉树的深度

3.测试数据：

输入的字符串表达式为：a+(b-c)*d

运行结果应为输出按中序遍历表达式成立的二叉树，并输出中序表达式，前序表达式，后序表达式及二叉树深度：

+

a*

-

bcd

中缀表达式：a+(b-c)*d

前缀表达式：+a*-bcd

后缀表达式：abc-d*+

二、需求分析

1.本程序用来求任意一个字符串表达式的二叉树形式，并输出其中序表达式，前序表达式，后序表达式及二叉树深度。

2.用户根据程序运行后的提示信息输入字符串表达式，运算符仅限+-*/，操作数仅限字符型。

3.用户输入完毕后，程序自动输出运算结果。

三、测试结果

四、附录

//用二叉树表示一个表达式，计算二叉树的深度

#include<iostream>

#include<stack>

#include<queue>

#include<string>

#include<math.h>

#defineOK1

#defineERROR0

#defineMAX(a,b)(a>b?a:b)

usingnamespacestd;

classTNode//节点类

{public:

charoper;//数据域，为简便起见，操作数用单个字符代替TNode*left;

TNode*right;

ints;

intt;//计算树的层数使用

TNode()//缺省构造函数

{left=right=NULL;

oper=0;

}

TNode(charop)//赋值构造函数

{left=right=NULL;

oper=op;

}

};

boolisOper(charop)//判断是否为运算符

{

charoper[]={'(',')','+','-','*','/','^'};

for(inti=0;i<sizeof(oper);i++)

{if(op==oper[i])

{

returntrue;

}

}

returnfalse;

}

intgetOperOrder(charop)//返回运算符op所对应的优先级{//左括号优先级，加减号为，方幂为，右括号，栈底返回

2

switch(op)

{

case'(':return1;

case'+':

case'-':return2;

case'*':

case'/':return3;

case'^':return4;

default:

//定义在栈中的右括号和栈底字符的优先级最低

return0;

}

}

voidfreeTree(TNode*&p)//递归删除树

{

if(p->left!=NULL)

freeTree(p->left);

if(p->right!=NULL)

freeTree(p->right);

delete(p);

}

voidpostOrder(TNode*p)//先序遍历

{

if(p)

{postOrder(p->left);

postOrder(p->right);

cout<<p->oper;

}

}

voidpreOrder(TNode*p)//后序遍历

{

if(p)

{cout<<p->oper;

preOrder(p->left);

preOrder(p->right);

}

}

voidinOrder(TNode*p)//中序遍历,同时输出不带冗余括号的中辍表达式{

3

if(p)

{

if(p->left)

{//如果当前节点的左子树是运算符,且运算符优先级不高于当前运算符,那么右边的表达式需要先计算,要加括号

if(isOper(p->left->oper)&&getOperOrder(p->left->oper)<getOperOrder(p->oper)){cout<<"(";

inOrder(p->left);

cout<<")";

}

else

{

inOrder(p->left);

}

}

cout<<p->oper;

if(p->right)

{

{if(isOper(p->right->oper)&&getOperOrder(p->right->oper)<=getOperOrder(p->oper))cout<<"(";

inOrder(p->right);

cout<<")";

}

else{

inOrder(p->right);

}

}

}

}

voidpost2tree(TNode*&p,stringstr)//后缀表达式生成二叉树

{

stack<TNode*>nodeStack;

chartemp;

inti=0;

temp=str[i++];

while(temp!='\0')

{if(temp!='\0'&&!isOper(temp))//不是运算符，则进栈

{p=newTNode(temp);//以temp为结点值构造二叉树结点

nodeStack.push(p);

temp=str[i++];}

else

{p=newTNode(temp);

if(nodeStack.size())

4

{p->right=nodeStack.top();//若非空则弹栈并设为结点的右孩子

nodeStack.pop();}

if(nodeStack.size())

{p->left=nodeStack.top();//若非空则弹栈并设为结点的左孩子

nodeStack.pop();}

nodeStack.push(p);

temp=str[i++];

}

}

}

voidpre2tree(TNode*&p,stringstr)//前缀表达式生成二叉树

{stack<TNode*>nodeStack;

chartemp;

inti=str.size()-1;

temp=str[i--];

while(temp!='\0')

{if(temp!='\0'&&!isOper(temp))

{p=newTNode(temp);//以temp为内容来建立新的结点

nodeStack.push(p);

temp=str[i--];}

else

{p=newTNode(temp);

if(nodeStack.size())//若栈顶指针所指结点左孩子为空

{p->left=nodeStack.top();//则当前结点设置成其左孩子

{nodeStack.pop();}if(nodeStack.size())//若栈顶指针所指结点右孩子为空p->right=nodeStack.top();//则当前结点设置成其右孩子

nodeStack.pop();//栈顶元素左右孩子指针设置完毕弹出}

nodeStack.push(p);

temp=str[i--];

}

}

}

}

voidin2tree(TNode*&p,stringstr)//中缀表达式转换成后缀表达式生成二叉树{stack<char>a;

chartemp;

stringPostfixexp="";

inti=0;

temp=str[i++];

while(temp!='\0')

5

{if(!isOper(temp))

{Postfixexp+=temp;

temp=str[i++];}

elseif(temp=='(')//进栈

{a.push(temp);

temp=str[i++];}

elseif(temp==')')

{

while(a.top()!='(')//脱括号

{

Postfixexp+=a.top();

a.pop();//在碰到开括号和栈为空前反复弹出栈中元素

}

a.pop();

temp=str[i++];

}

elseif(temp=='+'||temp=='-'||temp=='*'||temp=='/')//出栈

{

while(!a.empty()&&a.top()!='('&&getOperOrder(a.top())>=getOperOrder(temp))//若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时，

//将栈顶元素弹出到后缀表达式中，并且str下标加1

{Postfixexp+=a.top();

a.pop();}

a.push(temp);

temp=str[i++];

}}

while(!a.empty())

{Postfixexp+=a.top();

a.pop();

}

post2tree(p,Postfixexp);}

voidcount(TNode*p,int&height,intn)//求值函数

{if(p->left==NULL&&p->right==NULL)

{if(n>height)

height=n;}

if(p->left!=NULL)

count(p->left,height,n+1);

if(p->right!=NULL)

count(p->right,height,n+1);}

voidpaint(TNode*p)//输出函数

6

{intheight=0;

inth=0;

inti;

usingstd::queue;

queue<TNode*>aQueue;

count(p,height,1);

TNode*pointer=p;

TNode*lastpointer;

if(pointer)

{pointer->s=1;

pointer->t=1;

aQueue.push(pointer);}

while(!aQueue.empty())

{lastpointer=pointer;

pointer=aQueue.front();

aQueue.pop();

if(pointer->s>h)

{cout<<endl;

h=pointer->s;}

if(pointer->t==1)

{for(i=0;i<pow(2,height-pointer->s)-1;i++)

cout<<"";}

elseif(lastpointer->s!=pointer->s){

for(i=0;i<(pointer->t-1)*(pow(2,height-pointer->s+1)-1)+(pointer->t-1)-1+pow(2,height-pointer->s);i++)

cout<<"";}

else

{for(i=0;i<(pointer->t-lastpointer->t)*(pow(2,height-pointer->s+1)-1)+(pointer->t-lastpointer->t)-1;i++)

cout<<"";}

cout<<pointer->oper;

if(pointer->left!=NULL){

pointer->left->s=pointer->s+1;

pointer->left->t=pointer->t*2-1;

aQueue.push(pointer->left);}

if(pointer->right!=NULL){

pointer->right->s=pointer->s+1;

pointer->right->t=pointer->t*2;

aQueue.push(pointer->right);

}

}

}

7

//求二叉树的深度

intBiTreeDepth(TNode*T){

if(!T)return0;//二叉树为空树时

intDl=0,Dr=0;

if(T->left)Dl=BiTreeDepth(T->left);//求左子树深度if(T->right)Dr=BiTreeDepth(T->right);//求右子树深度returnMAX(Dl,Dr)+1;

}

intmain()

{stringexpression;

TNode*tree;

cout<<endl<<"请输入字符串表达式:";

cin>>expression;

if(isOper(expression[0]))

pre2tree(tree,expression);

elseif(isOper(expression[1]))

in2tree(tree,expression);

else

post2tree(tree,expression);

paint(tree);

cout<<endl;

cout<<"中缀表达式为:";

inOrder(tree);

cout<<endl;

cout<<"前缀表达式为:";

preOrder(tree);

cout<<endl;

cout<<"后缀表达式为:";

postOrder(tree);

cout<<endl;

printf("\n二叉树深度为%d",BiTreeDepth(tree));freeTree(tree);

cout<<endl;

system("pause");

return0;

}

8