数据结构二叉树应用原理

二叉树

一、程序设计题目：

(1)建立一个字符二叉树实例，并横向打印该二叉树；(2)计算并输出二叉树的深度和叶子节点数；(3)分别按中序和后序遍历二叉树输出节点数据。

二、需求分析：

(1)建立一个记录字符数据的二叉树T。二叉树的数据由用户以键盘形式直接输入；(2)本程序输出用户所建立的二叉树T的深度和叶子结点数；(3)本程序还将按中序遍历和后序遍历输出结点数据。（本人认为该步骤即为横向打印二叉树，因此不再做横向打印的要求）。

三、概要设计：

1.抽象数据类型二叉树的定义如下：

ADT BinaryTree{

数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：

若D=Φ，则B=Φ，称BinaryTree为空二叉树；

若D≠Φ，则B={H}，H是如下二元关系：

(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；

(2)若D-{root}≠Φ，则存在D-{root}={D1 ，Dr }，且D1 ∩Dr =Φ；

(3)若D1 ≠Φ，则D1中存在惟一的的元素xr ，<root, x1 >∈H，且存在D1 上的关系H1

H1 ，Hr }；

(4)(D1 ，{ H1 })是一棵符合本定义的二叉树，称为根的左子树，(Dr ，{Hr })是一棵符合本定义的二叉树，称为根的右子树。

基本操作P：

CreateBiTree(&T)；

操作结果：构造二叉树T。

DestroyBiTree(&T)；

1 H；若Dr 中存在惟一的元素xr ，<root, xr>H；H={<root, x1 >，<root, xr>，∈H，且存在Dr 上的关系Hr

初始条件：二叉树T存在。

操作结果：销毁二叉树T。

BiTreeDepth(&T)；

初始条件：二叉树T存在。

操作结果：返回T的深度。

CountLeaf(&T)；

初始条件：二叉树T存在。

操作结果：求T的叶子结点数。

}ADT BinaryTree

2.主程序

Void mian()

{

初始化；

构造二叉树；

处理命令；

}

3.本程序只有两个模块，调用关系为主程序模块调用二叉树模块。

四、详细设计：

1.二叉树类型

Typedef struct BiNode{

char data;

struct BiNode *lchild,*rchild; //左右孩子指针 }BiNode,*BiTree;

二叉树的基本操作：

MidVisitBiTree(BiTree &T)

//中序遍历访问二叉树T

BehindVisitBiTree(BiTree &T)

//后序遍历访问二叉树T

其操作的伪码算法如下：

void MidVisitBiTree(BiTree &T)

{//按中序遍历访问二叉树T，并输出结点数据

if(T){

MidVisitBiTree(T->lchild);

printf(“%c”,T->data);

MidVisitBiTree(T->rchild);

}

else return;

return;

}

void BehindVisitBiTree(BiTree &T)

{//按后序遍历访问二叉树T，并输出结点数据

if(T){

BehindVisitBiTree(T->lchild);

BehindVisitBiTree(T->rchild);

printf(“%c”,T->data);

}

else return;

return;

}

2.主程序伪码算法

void main()

{

BiTree t;

int high;

printf("请按先序遍历输入一组字符数据。(每输入一个字符按回车确定,结束输入仍按回车结束)\n");

CreateBiTree(t); //构造二叉树

high=BiTreeDepth(t); //求二叉树深度

printf("二叉树的深度是%d\n",high);

CountLeaf(t); //求二叉树叶子数

printf("二叉树的叶子数是%d\n",leaf);

printf("中序遍历:");

MidVisitBiTree(t);

printf("\n后序遍历:");

BehindVisitBiTree(t);

printf("\n");

}

3.其它伪码算法

int BiTreeDepth(BiTree &T) //计算二叉树T的深度 {

int lh,rh,h;

if(T==NULL) h=0;

else{

//递归访问左右孩子,并计算其支路深度

lh=BiTreeDepth(T->lchild);

rh=BiTreeDepth(T->rchild);

h=(lh>rh ? lh:rh)+1; //条件运算符判断二叉树的深度 }

return h;

}

void CountLeaf(BiTree &T) //计算二叉树T的叶子结点数 {

if(T)

{

if(!(T->lchild&&T->rchild)) leaf++;

//判断当前结点是否为叶子结点

CountLeaf(T->lchild);

//若当前结点不是叶子,递归访问其左右孩子

CountLeaf(T->rchild);

}

return;

}

五、调试分析：

该程序的核心算法是构造二叉树T，在进行调试时，遇到的主要问题是，该程序是按先序次序输入字符，用户要事先确定二叉树，不能输入一连串的字符由程序自动分配。如要强制输入的话，程序只能对其构造单支树的二叉链表。为此该程序特别打出要输入左右孩子的提示。其次，对二叉树的中序和后序遍历，按照课本上的算法需多出Visit()函数，本人认为既然要让用户知道对二叉树已经遍历过了，就得将其打印出来，因此省去了Visit()函数直接printf输出，也合并了横向打印二叉树这一步骤。

该程序的主要算法CreateBiTree以及中序遍历MidVisitBiTree和后序遍历BehinVisitBiTree的时间复杂度均为O(n)。

六、总结：

对于本次编程一开始的时候还很顺利，直到调试时才注意到输入字符的复杂程度，可以说，对于不了解二叉树的用户来说是无法理解该程序的。对于每次输入的字符，都应事先勾画出心中的二叉树。计算二叉树深度的算法看似简单其实不然，其先用遍历二叉树算法得出每条支路的深度，然后用条件运算符比较得出二叉树的深度。

05本(3)班

梁中君

2005107408

第二篇：数据结构二叉树的基本操作实现及其应用

实验三二叉树的基本操作实现及其应用

一、实验目的

1．熟悉二叉树结点的结构和对二叉树的基本操作。

2．掌握对二叉树每一种操作的具体实现。

3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

4.会用二叉树解决简单的实际问题。

二、实验内容

题目一设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树，

2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点

以上比做，以下选做

3求二叉树中所有结点数

4求二叉树的深度

**************************************************************** /* 定义DataType为char类型 */

typedef char DataType;

/* 二叉树的结点类型 */

typedef struct BitNode

{ DataType data;

struct BitNode *lchild,*rchild;

}*BitTree;

数据结构 二叉树应用原理

第二篇：数据结构 二叉树的基本操作实现及其应用

专栏推荐

数据结构二叉树应用原理

第二篇：数据结构二叉树的基本操作实现及其应用