Posted on 2008-08-29 12:59
dengbo 阅读(537)
评论(0) 编辑 收藏 引用 所属分类:
数据结构 严蔚敏
6.1 树的类型定义
基本术语
结点
:数据元素 + 若干指向子树的分支
结点的度
:分支的个数
树的度
:树中所有结点的度的最大值
叶子
结点:度为零的结点
分支
结点:度大于零的结点
从根到结点的
路径：
孩子
结点、双亲结点、兄弟结点、祖先、子孙
结点的层次
:假设根结点的层次为1,
第
l层的结点的子树根结点的层次为l+1
树的深度
：树中叶子结点所在的最大层次
森林
：是m（m≥0）棵互不相交的树的集合
任何一棵非空树是一个二元组
Tree =
（root，F）
其中：
root被称为根结点，F被称为子树森林
6.2 二叉树的类型定义
二叉树 或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
二叉树的重要特性：
性质
1
：
在二叉树的第 i 层上至多有2i-1个结点(i≥1)
性质
2 ：
深度为k的二叉树上至多含2k-1个结点（k≥1）
性质 3 ：
对任何一棵二叉树，若他含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0 = n2+1
两类特殊的二叉树：
满二叉树
：指的是深度为k且含有2k-1个结点的二叉树
完全二叉树
：树中所含的n
个结点和满二叉树中编号为1
至n的结点一一对应
性质
4
：
具有n个结点的完全二叉树的深度为
性质
5
：
若对含n个结点的二叉树从上到下且从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：
(1) 若i=1，则该结点是二叉树的根，无双亲,
否则，编号为
的结点为其双亲结点;
(2) 若2i>n，则该结点无左孩子，
否则，编号为2i的结点为其左孩子结点；
(3) 若2i+1>n，则该结点无右孩子结点，
否则，编号为2i+1的结点为其右孩子结点。
6.3 二叉树的存储结构
一、
二叉树的顺序存储表示
#define MAX_TREE_SIZE 100 //
二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0
号单元存储根结点
SqBiTree bt;
显然，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为
k 且只有 k 个结点的单支树（树中不存在度为 2 的结点）却需要长度为2k-1的一维数组。
二、二叉树的链式存储表示
1. 二叉链表
typedef struct BiTNode 
{
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
typedef struct TriTNode {
TElemType data;
struct TriTNode *lchild, *rchild; // 左右孩子指针
struct TriTNode *parent; //
} TriTNode, *TriTree;
3．双亲链表
typedef struct BPTNode {
TElemType data;
int *parent; // 指向双亲的指针
char LRTag; // 左、右孩子标志域
} BPTNode
typedef struct {
BPTNode nodes[MAX_TREE_SIZE];
int num_node; // 结点数目
} BPTree