文档介绍：第七章 树状结构
第1页，本讲稿共53页
何谓树状结构
树状结构在计算机信息处理中应用相当广泛，如文件系统、目录组织、菜单管理等。
树状结构中常见的是树和二叉树，本章介绍这两种结构的概念、存储结构和相关算法，并研究共53页
二叉树表示法
二叉树节点的表示法，常用的有下列3种方法：
(1) 二叉树数组表示法
(2) 二叉树结构数组表示法
(3) 二叉树链表表示法
其中“数组表示法”和“结构数组表示法”是属于静态内存空间配置，而“链表表示法”是利用列表结构的方式，属于动态内存空间配置。
第12页，本讲稿共53页
二叉树数组表示法
对于一棵满二叉树，将其结点从上到下，从左到右顺序编号，再根据编号存入对应下标编号的数组中。
如果该树不为满二叉树，也可对各节点编成在满二叉树中相同位置之节点编号值，再以相同的方式存入数组中，若某一编号没有节点存在，则不存值于数组中。
假设一父节点的编号为n
左子节点的编号为：2n，
右子节点的编号为：2n+1。
第13页，本讲稿共53页
二叉树数组表示法
优点：对于任意一个节点都能很容易的找到其父节点、子节点及兄弟。
缺点：这样将导致存储空间的浪费，极端的情况是对于一个二叉树，每个结点只有右孩子而无左孩子时，假设该树的深度为k，则需要2k-1个存储单元，而实际只利用了其中的k个存储单元。
第14页，本讲稿共53页
二叉树链表表示法（二叉链表）
链表的节点结构如下：
每个节点包含三个域：
数据域（Data）：存储结点的数据内容
左指针域（left）：指向该节点的左子树
右指针域（right）：指向该节点的右子树
由这种链式存储结构构成的二叉树称为二叉链表。
第15页，本讲稿共53页
二叉树链表表示法（二叉链表）
二叉链表结构的声明如下：
strust tree
{ struct tree *left;
int data;
struct tree *right;
}
typedef struct tree treenode;
treenode *b_tree;
第16页，本讲稿共53页
二叉树的遍历
“遍历”是访问数据结构中的各个数据值，例如：数组和链表可从前端到尾端或从尾端至前端依序访问各个数据值。而二叉树是一种特殊的数据结构，每个节点其下又各有左、右两个分支。
“二叉树的遍历”是以固定的顺序，有系统地访问二叉树中的各节点，且每个节点均恰好被访问一次。
第17页，本讲稿共53页
一棵二叉树由根结点、左子树和右子树三部分组成，若依次遍历这三部分，也就遍历了整棵树。这里用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，。若按照从左到右的顺序进行遍历，则有LDR、DLR、LRD三种方式，它们分别称为中序遍历、前序遍历和后序遍历。
第18页，本讲稿共53页
二叉树的前序遍历
前序遍历二叉树的算法为：若二叉树为空，则遍历结束，否则依次执行以下操作：
（1）访问根结点；
（2）前序遍历根结点的左子树；
（3）前序遍历根结点的右子树。
第19页，本讲稿共53页
其具体算法实现如下：
void preorder(b_tree point)
{
if (point!=NULL) /*遍历的终止条件*/
{
printf("%d ",point->data); /*处理打印节点内容*/
preorder(point->left); /*处理左子树*/
preorder(point->right); /*处理右子树*/
}
}
第20页，本讲稿共53页
二叉树的中序遍历
中序遍历二叉树的算法为：若二叉树为空，则遍历结束，否则依次执行以下操作：
（1）中序遍历根结点的左子树；
（2）访问根结点；
（3）中序遍历根结点的右子树。
第21页，本讲稿共53页
其具体算法实现如下：
void inorder(b_tree point)
{
if (point!=NULL) /*遍历的终止条件*/
{
inorder(point->left); /*处理左子树*/
printf("%d ",point->data); /*处理打印节点内容*/
inorder(point->right); /*处理右子树*/
}
}
第22页，本讲稿共53页
void inorder(