树与二叉树 总复习

一、树的定义

树是一个有n个（n>=0）结点的有限集合。

如果n=0，称为空树；

如果n>0，称为非空树，有且仅有一个特定的称为根Root的结点（无直接前驱）

如果n>1,除了根节点外，其他结点划分为m个互不相交的有限集合（记为T1、T2...TM），每个集合本身又是一棵树，称为根的子树（Sub-tree）。

每个结点肯定有唯一的前驱（除根节点外），但是可能有多个后继。

二、树的术语

结点：包含一个数据元素及若干指向其子树的分支

结点的度：结点拥有的子树个数，也即结点包含的分支个数

叶子结点（终端结点）

度为0的结点 {K,L,F,G,M,I,J}

分支结点（）非终端结点

度不为0的结点 {A,B,C,D,E,H}

包含根结点

内部结点：除根之外的分支结点 {B,C,D,E,H}

孩子：结点的子树的根

双亲：孩子的直接前驱

兄弟：同一个双亲的其他孩子

子孙：以某结点为根的树中所有的结点

祖先：从该结点到根结点，经过所有分支结点

树的层次

根结点为第一层，根的孩子为第二层，依次类推。

深度：树中最大的层次

森林：互不相交的树的集合。对于树中每个结点而已，其子树的集合就是森林

二叉树  Binary Tree

每个结点最多只有两棵子树 最多两个孩子

二叉树的子树可以分成左右两个部分 称为左子树和右子树    

 二叉树的性质1

在二叉树的第i层上至多有2i-1个结点  

深度为k的二叉树至多有2^k-1个结点

如果二叉树终端结点数为n0,度为2的结点数为n2，则no=n2+1

证明思路：总结点数n=no+n1+n2

考察分支数B：除了根之外，所有的结点都有且只有一个分支指向它不同度的结点产生不同个数的分支 n=B+1

不同度的结点产生不同个数的分支B=n1+2n2

no=n2+1

五、满二叉树

一个深度为k且有2^^k-1个结点的二叉树

每层上的结点数都是最大数  可以自上而下、自左至右连续编号

完全二叉树  当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一一对应的二叉树

叶子结点只在最大两层上出现

以任何一个结点为根结点，其左子树深度与右子树深度相等或大于1

具有n个结点的完全二叉树 其深度为log2n取整+1

七、二叉树的存储结构：顺序存储

用一组连续的存储单元依次自上而下，自左至右存储结点

对于一般二叉树，空结点的位置也要按照完全二叉树编号

八、二叉树的链式存储结构

1、二叉链表

采用数据域加上左右孩子的指针

2、二叉链表的定义

二叉链表的一个结点的可以用一个结构体表示，里面包含的成员有一个数据域，两个指针域

struct BiNode    binode： 双节点           node:节点

{

char data;

BiNode  *Ichild,*rchild;

}

3、二叉树的链式存储结构

只能双亲找孩子，孩子难以找到双亲

4、二叉树的链式存储结构

三叉链表

 遍历二茶树

根据访问根结点的次序

DLR

LDR

LRD

先序：

boid PreOrderTraverse(BinTree T)

{

if(T)

{

cout<<T->data;

PreOrderTraverse(T->IChild);

PreOrderTraverse()T->rChild):

先序中序、中序后序

都可以求出二叉树

而先序和后序不可以

因为不具备确定左右子树的能力。

树的存储结构

双亲表示法   找双亲容易找孩子难   

孩子表示法：最大的缺点就是空指针链域太多    有些结点有很多孩子 有些结点的孩子很少：结构不均衡          

n结点的树   度为d      多链表表示法中 空指针必有[（d-1）n+1]

 

 

 

树的路径：

路径：从树的一个结点到另一个结点之间的分支构成了两个结点之间的路径

路径长度：路径上的分支的数目

树的路径长度：从根结点到每个结点之间路径长度的和

如果结点权重不一样，我们可以计算带权路径长度

从结点到根结点之间的路径长度乘以该结点的权重

树的带权路径长度WPL    Weighted  path length

树中所有叶子结点的带权路径长度之和（）度为0

相同的叶子结点数，叶子结点也具有相同的权重，但是不同的二叉树会产生不同的WOL

引出概念

树的带权路径长度WPL最小的二叉树被称为最优二叉树

Huffman  哈夫曼树

有什么special的place

权值最大的结点离根最近

权值最小的结点离根最远

 

 

有了编码

怎么解码

要能唯一解码对编码有什么要求

要求前缀编码

即任何一个字符编码都不是其他字符的前缀

Huffman是一种前缀编码