二叉树的应用举例实验报告(燕山大学)

题目：

班级：

姓名：

学号：得分： 二叉树的应用举例 信息一班 冯琴琴

120108010001

实验三 二叉树的应用举例

一、 实验目的

要求学生必须掌握二叉树的建立及先序、中序、后序三种遍历方式，在此基础上实现树的一些简单应用问题

二、 实验内容及步骤

1.二叉链表的建立，先（中、后）序遍历

输入：字符串序列

输出：先（中、后）序序列

处理方法：通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。以字符串的形式:根、左子树、右子树定义一棵二叉树：

1) 空树以空白字符‘#’表示

2) 只含一个根结点的二叉树（图1示）以字符串‘A##’表示

3) 一般的二叉树，以图2为例，以下列字符串表示：AB#C##D##

4) 无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外

缘移动，对每个节点均途经三次。

先序遍历：第一次经过节点时访问。中序遍历：第二次经过节点时访问。后序遍历：第三次经过节点时访问

图1

图2

2. 统计二叉树中叶子结点的个数，计算二叉树的深度。

输入：字符串序列

输出：叶子结点的个数，二叉树的深度

处理方法：

1) 先序遍历二叉树。在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的

参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

2) 后序遍历二叉树。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由

此，先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。

程序：

#include<iostream.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -1

typedef char TElemType ;

typedef int Status ;

const int MAX_TREE_SIZE =100 ;

const int TREEINCREMENT= 10 ;

typedef struct BiTNode {//结点结构

TElemType data;

BiTNode *lchild,*rchild;

// 左右孩子指针

} BiTNode, *BiTree;

Status InitBiTree(BiTree &T)

{ if (!(T=new BiTNode)) return ERROR;

T->lchild=NULL; T->rchild=NULL;

return OK;

} //InitBiTree

void CreateBiTree(BiTree &T)

{ TElemType e;

}

cin>>e; T->data=e; if(e!='#'){ InitBiTree(T->lchild); InitBiTree(T->rchild); CreateBiTree(T->lchild); CreateBiTree(T->rchild); }

void visit(TElemType e)

{

}

void PreOrderTraverse (BiTree T, void(*call)(TElemType e)) // 先序遍历 这里的函数指针调用输出函数 call--调用

{ if(T->data!='#'){

}

void InOrderTraverse (BiTree T, void(*call)(TElemType e)) //中序遍历

{ if(T->data!='#'){

}

void PostOrderTraverse (BiTree T, void(*call)(TElemType e)) //后序遍历

{ if(T->data!='#'){

}

void CountLeaf (BiTree T, int &count){

if(T->data!='#'){ PostOrderTraverse( T->lchild, visit); PostOrderTraverse( T->rchild, visit); } call(T->data); InOrderTraverse( T->lchild, visit); call(T->data); } call(T->data); PreOrderTraverse ( T->lchild, visit); PreOrderTraverse ( T->rchild, visit); cout<<e<<' '; InOrderTraverse( T->rchild, visit); }

if ((T->lchild->data=='#')&&(T->rchild->data=='#'))

count++; // 对叶子结点计数

CountLeaf( T->lchild, count);

CountLeaf( T->rchild, count);

}

int BiTreeDepth (BiTree T){

int ldepth,rdepth,depth;

if(T->data=='#') depth=0; } else{

ldepth=BiTreeDepth (T->lchild);

rdepth=BiTreeDepth (T->rchild);

}

void main(){

BiTree T;

int depth,count=0; InitBiTree(T); depth=1+(ldepth>rdepth?ldepth:rdepth);} return depth;

CreateBiTree(T);

cout<<"先序遍历:"; PreOrderTraverse ( T, visit); cout<<endl; cout<<"中序遍历:";

InOrderTraverse( T, visit);

cout<<endl; cout<<"后序遍历:"; PostOrderTraverse( T, visit);

cout<<endl; CountLeaf (T, count); cout<<"此二叉树叶子节点为:"; cout<<count; cout<<endl;

depth=BiTreeDepth ( T);

}

运行结果：

cout<<"此二叉树深度为:"; cout<< depth; cout<<endl;

3.中序线索二叉链表的建立及遍历

输入：字符串序列

输出：结点的相关信息，中序序列

处理方法:

1) 在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。

2) 遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的指针p所指结点的前驱。

3) 中序线索二叉树结构对称。其中：第一个结点是最左下的结点，最后一个结点是最右下的结点。

4) 在中序线索二叉树上找结点的(直接)后继/前驱方法：

a) 若该结点有右孩子，其后继为其右子树中最左下的结点；

b) 若该结点无右孩子，其后继由rchild指向：其后继为满足以下条件的最小子树的根r：该结点为r的左子树中最右下的结点。

程序：

#include<iostream.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -1

typedef char TElemType ;

typedef int Status ;

typedef enum { Link, Thread } PointerThr; //Link==0指针, Thread ==1线索 typedef struct BiThrNode {

TElemType data;

BiThrNode *lchild, *rchild; //左右指针

PointerThr LTag, RTag; //左右标志

} BiThrNode, *BiThrTree;

Status InitBiThrTree(BiThrTree &T)

{ if (!(T=new BiThrNode)) return ERROR;

T->lchild=NULL; T->rchild=NULL;

T->LTag=Link;

T->RTag=Link;

return OK;

}

void CreateBiThrTree(BiThrTree &T)

{ TElemType e;

cin>>e;

T->data=e;

if(e!='#'){

InitBiThrTree(T->lchild);

InitBiThrTree(T->rchild);

CreateBiThrTree(T->lchild);

CreateBiThrTree(T->rchild);

}

}

void InThreading(BiThrTree &pre, BiThrTree &p) {

if(p->data!='#'){

InThreading(pre,p->lchild);

if (p->lchild->data=='#'){

p->LTag=Thread;

p->lchild = pre;

}

if (pre->rchild->data=='#'){

pre ->RTag=Thread;

}

pre = p; InThreading(pre,p->rchild); }

Status InOrderThreading(BiThrTree &Thrt, BiThrTree &T) {

BiThrTree pre,p; Thrt->RTag=Thread; Thrt->rchild=Thrt; if(!T) Thrt->lchild=Thrt; Thrt->lchild=T; pre=Thrt; p=T; else{ InThreading(pre, p); pre->RTag = Thread;

pre->rchild = Thrt;

Thrt->rchild=pre; }

return OK;

}

void visit(TElemType e)

{

}

void InOrderTraverse_Thr(BiThrTree T, void (*call)(TElemType e)) {

} BiThrTree p; p = T->lchild; while (p->LTag!=Thread){ p=p->lchild; } while(p->RTag!=Thread||p->rchild!=T){ p=p->rchild; } cout<<p->data; cout<<e<<' '; visit(p->data );

void main(){

BiThrTree T,Thrt;

}

运行结果：

InitBiThrTree(Thrt); InitBiThrTree(T); InOrderThreading(Thrt, T); cout<<"中序线索二叉链表的遍历:"; InOrderTraverse_Thr(Thrt,visit); cout<<endl; CreateBiThrTree(T);

本文来源：https://www.bwwdw.com/article/6gr4.html