二叉树的应用
一、实验目的
1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
3．熟悉二叉树的应用
二、实验内容
本次实验提供2个题目，学生可以根据自己的情况任选一个。 题目一：二叉树的应用
[问题描述]
建立一棵二叉树，试编程实现二叉树的如下基本操作：
1. 按先序序列构造一棵二叉链表表示的二叉树T；
2. 求二叉树的深度，叶子结点数目；
3. 将二叉树每个结点的左右子树交换位置，输出交换后的二叉树的中序遍历。
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），
[测试数据]
如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为
深度：5
叶子结点：3
中序遍历：AFDGEBC
三、算法设计
1.按先序创建二叉树
2.求二叉树的深度
3.求叶子节点的数目
4.交换二叉树的左右子树输出中序遍历结果
四、实验报告要求
1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
五、附录（源代码）
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
typedef struct BiTNode
{
char data; struct BiTNode *lchild,*rchild; }BiNode,*BiTree;
void createTree(BiTree &T) //创建二叉树 {
char ch; scanf("%c",&ch); if(ch=='0') { T=(BiTree)malloc(sizeof(BiNode)); if(!T) exit(0); T->data=ch; T=NULL; else
createTree(T->lchild);
}
int height(BiTree &T)
{ int i,j; } return ; createTree(T->rchild);
} { } if(!T) { i=height(T->lchild); j=height(T->rchild); if(i>j) return i+1; else } return j+1; return 0; else int leafs(BiTree &T) int num1,num2; if(T==NULL) return 0; else{ if(T->lchild==NULL&&T->rchild==NULL) return 1; num1=leafs(T->lchild); num2=leafs(T->rchild); return num1+num2; } void exchange(BiTree &T) { BiTree temp=NULL; if(T->lchild==NULL&&T->rchild==NULL) { temp=T->lchild; return; else
} } T->lchild=T->rchild; T->rchild=temp; if(T->lchild) exchange(T->lchild); exchange(T->rchild); if(T->rchild)
void InOrder(BiTree &T) {
}
int main()
{
BiTree T; T=NULL; int n; while(1){ printf("********************************************\n"); printf("1.创建二叉树\n"); printf("2.求二叉树的深度\n"); printf("3.求二叉树叶子节点的数目\n"); printf("4.交换二叉树左右子树并输出交换后的中序遍历\n"); printf("0.退出\n"); printf("********************************************\n"); printf("请选择："); scanf("%d",&n); getchar(); if(T) { } InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild);
} switch(n){ case 1: { } { } { } { } exchange(T); InOrder(T); printf("\n"); break; printf("二叉树中叶子节点数目为：%d\n",leafs(T)); break; printf("二叉树的深度为：%d\n",height(T)); break; printf("请输入二叉树元素(0表示空)："); createTree(T); break; case 2: case 3: case 4: case 0: } } return 0; exit(0);
六、运行结果
（1）创建二叉树
(2)求二叉树的深度
（3）求二叉树叶子节点的数目
(4)交换二叉树左右子树并输出交换后的中序遍历
第二篇：实验报告三 二叉树应用
实验报告三二叉树应用
一、问题描述
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