目录
一,树
1,基本术语:
2,树的性质:
3,树的遍历:
4,森林的遍历:
5,树和二叉树的转换:
6,二叉树和森林的转化:
7,树的存储:
1,双亲表示法
2、孩子链存储结构
3、孩子兄弟链存储结构
二,二叉树:
1,二叉树的性质:
2,二叉树的遍历:
3,二叉树的存储结构:
顺序存储:
链式存储:
4,二叉树遍历实现
5,基本算法
(1)查找二叉树:
(2)树的高度:
(3)节点个数:
(4)叶子结点个数:
(4)复制二叉树:
(4)左右孩子进行交换:
(5)找到元素x的层次:
6,练习:
三,线索二叉树
1,相关概念:
2,标志位的确立:
四,哈夫曼树:
1,相关概念:
2,构建哈夫曼树:
3,哈夫曼编码:
树形式化定义：T={D，R}。D是包含n个节点的有限集合 （n≥0）。除非n=0时为空树，否则关系R满足以下条件: 有且仅有一个节点 d0∈D，它对于关系R来说没有前趋节点，节点d0称作树的根节点。 除根节点外，每个节点有且仅有一个前趋节点。 D中每个节点可以有零个或多个后继节点
一,树
1,基本术语:
| 1、节点的度与树的度：树中一个节点的子树的个数称为该节点 的度。树中各节点的度的最大值称为树的度 |
| 2、分支节点与叶节点：度不为零的节点称为非终端节点，又叫分 支节点。度为零的节点称为终端节点或叶节点（或叶子节点）。 |
| 3、孩子节点、双亲节点和兄弟节点：在一棵树中，每个节点的后继，被称作该节点的孩子节点（或子女节点）。相应地，该节点被称作孩子节点的双亲节点（或父母节点）。 具有同一双亲的孩子节点互为兄弟节点。 |
| 4、子孙节点和祖先节点：在一棵树中，一个节点的所有子树中的节点称为该节点的子孙节点。 从根节点到达一个节点的路径上经过的所有节点被称作该节点的祖先节点 |
| 5、节点的层次和树的高度：树中的每个节点都处在一个层次上。 节点的层次从树根开始定义，根节点为第1层，它的孩子节点为第2层。 树中节点的最大层次称为树的高度（或树的深度）。 |
| 6、森林：n（n＞0）个互不相交的树的集合称为森林。 |
2,树的性质:
| 性质1 :树中的节点数等于所有节点的度数加1。 |
| 性质2 度为m的树中第i层上至多有m^(i-1)个节点（i≥1）二叉树:2^(i-1) |
| 性质3 高度为h的m次树至多有(m^h-1)/(m-1)个节点。二叉树:2^h-1 |
| 性质4 具有n个节点的m次树的最小高度为[logm (n(m-1))+1](向下取整)。二叉树:log2(n)+1 |
| 性质5 度为m的树中：n = n0+ n1 + … + nm |
3,树的遍历:
| 先根遍历 : 若树不空，则先访问根节点，然后依次先根遍历各棵子树。 |
| 后根遍历 : 若树不空，则先依次后根遍历各棵子树，然后访问根节点。 |
| 层次遍历: 若树不空，则自上而下、自左至右访问树中每个节点 |
4,森林的遍历:
| 先序遍历:从左至右依次对森林中的每一棵树进行先根遍历 |
| 中序遍历:依次从左至右对森林的每一棵树进行后根遍历 |
5,树和二叉树的转换:
树->二叉树:每个节点的第一个孩子,变成左孩子,一个节点的兄弟变成右孩子
二叉树->树:二叉树节点的右孩子变成自己的兄弟,左孩子依旧是孩子
| 树 | 二叉树 | |
| 树T->二叉树 | 先根遍历 | 先序遍历 |
| 树T->二叉树 | 后根遍历 | 中序遍历 |
| 一棵树的先根遍历和后根遍历可以唯一确定这棵树 | ||
| 将森林T转换为二叉树B，若T中有n个非叶子节点， 则二叉树B中无右孩子的节点个数是n+1 | ||
6,二叉树和森林的转化:
森林->二叉树:
将森林中的每一棵树都转化成二叉树,每一棵树的根结点互为兄弟,按照兄弟变右孩子的思路进行转换即可
二叉树->森林:
二叉树根结点的右孩子变成自己的兄弟,再将每一棵二叉树转换成森林
7,树的存储:
1,双亲表示法
第一列表示节点的数据,第二列表示双亲节点的位置下标
2、孩子链存储结构
3、孩子兄弟链存储结构
二,二叉树:
1,二叉树的性质:
| 性质1 非空二叉树上叶节点数等于双分支节点数加1。即： n0=n2+1。 |
| 性质2 非空二叉树上第i层上至多有2^(i-1)个节点（i≥1）。 |
| 性质3 高度为h的二叉树至多有2h-1个节点（h≥1）。 |
| 性质4 具有n个节点的二叉树最小高度为log2(n)+1(向下取整) |
| 性质5 (完全二叉树)若编号为i的节点有左孩子节点，则左孩子节点的编号为2i； 若编号为i的节点有右孩子节点，则右孩子节点的编号为2i+1。(i≥1) |
| 性质6 (完全二叉树)n1的个数可由n来决定,如果n为奇数,则n1=0,如果n为偶数,则n1=1 |
性质7 含有n个节点不相似的二叉树有: |
2,二叉树的遍历:
| 1、先序遍历:访问根节点； 先序遍历左子树； 先序遍历右子树。 |
| 2、中序遍历:中序遍历左子树； 访问根节点； 中序遍历右子树。 |
| 3、后序遍历:后序遍历左子树； 后序遍历右子树； 访问根节点。 |
| 4, 层次遍历: 若树不空，则自上而下、自左至右访问树中每个节点 |
3,二叉树的存储结构:
顺序存储:
存储特点:对于 对于 完全二叉树来说，其顺序存储是十分合适的。 一般的二叉树，特别是对于那些单分支节点较多的二叉树来说 是很不合适的，因为可能只有少数存储单元被利用，特别是对退化 的二叉树（即每个分支节点都是单分支的），空间浪费更是惊人。
链式存储:
二叉存储的特点:除了指针外，二叉链 比较节省存储空间。占用的存储空间与树形 没有关系，只与树中节点个数有关。 在二叉链中， 找一个节点的孩子很容易，但找其双亲不方便。
在二叉链中，空指针的个数:n+1(n为节点个数)
4,二叉树遍历实现
//先序遍历
void PreOrder(BTNode *b){if (b!=NULL){printf("%c ",b->data);PreOrder(b->lchild);PreOrder(b->rchild);}}
//中序遍历
void InOrder(BTNode *b){if (b!=NULL){InOrder(b->lchild);printf("%c ",b->data);InOrder(b->rchild);}}
//后序遍历
void PostOrder(BTNode *b){if (b!=NULL){PostOrder(b->lchild);PostOrder(b->rchild);printf("%c ",b->data);}}时间复杂度/空间复杂度均为:O(n)
层序遍历:使用一个队列。 I. 将根节点进队； II. 队不空时循环：从队列中出列一个节点*p，访问它； 若它有左孩子节点，将左孩子节点进队； 若它有右孩子节点，将右孩子节点进队。
void LevelOrder(BTNode *b){BTNode * p;SQQueue *qu;initQueue(qu);enQueue(qu,b);while(!QueueEmpty(qu)){deQueue(qu,p);printf("%c",p->data); if(p->Lchild!=NULL)enQueue(qu,p->Lchild);if(p->rchild!=NULLL)enQueue(qu,p->rchild)}
}5,基本算法
(1)查找二叉树:
BTNode *FindNode(BTNode *b,ElemType x)
{ BTNode *p;if (b--NULL) return NULL;else if (b->data--x) return b; else { p=FindNode(b->Ichild,x); if (p!-NULL) return p; else return FindNode(b->rchild,x);}
}(2)树的高度:
int BTNodeDepth(BTNode *b){int lchilddep,rchilddep;if (b==NULL) return(0);else{lchilddep=BTNodeDepth(b->lchild);rchilddep=BTNodeDepth(b->rchild);return(lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1));}}(3)节点个数:
int Nodes(BTNode *b){ if (b==NULL) return 0;elsereturn Nodes(b->lchild)+Nodes(b->rchild)+1}(4)叶子结点个数:
int LeafNodes(BTNode *b){int num1,num2;if (b==NULL) return 0;else if (b->lchild==NULL && b->rchild==NULL) return 1;else{num1=LeafNodes(b->lchild);num2=LeafNodes(b->rchild);return (num1+num2)}}(4)复制二叉树:
void Copy(BTNode *b,BTNode *&t){ if (b==NULL) t=NULL;else{ t=(BTNode *)malloc(sizeof(BTNode));t->data=b->data;Copy(b->lchild,t->lchild); Copy(b->rchild,t->rchild)；}}(4)左右孩子进行交换:
void Swap(BTNode *b,BTNode *&t){ if (b==NULL) t=NULL;else{ t=(BTNode *)malloc(sizeof(BTNode));t->data=b->data;Swap(b->lchild,t->rchild); //递归交换左子树Swap(b->rchild,t->lchild);}}(5)找到元素x的层次:
int Level(BTNode *b,ElemType x,int h){if (b==NULL) return 0;else if (b->data==x) return h;else{l=Level(b->lchild,x,h+1);if (l==0)return Level(b->rchild,x,h+1);else return l;}}
6,练习:
已知一颗非满二叉树有31个分支节点,则总结点个数是多少??
答:n2+n1=31,n1=0=> n2=31; n0=n2+1=>n0=32;n=n0+n1+n2=63
三,线索二叉树
1,相关概念:
| 1,修改空链域改为存放指向节点的前趋和后继节点的地址。 |
| 2,这样的指向该线性序列中 的“前趋”和“后继”的指针，称 作线索（thread）。 |
| 3,创建线索的过程称为线索化。 |
| 4,线索化的 二叉树称为线索二叉树。 |
| 5,显然线索二叉树与采用的 遍历方法相关，有先序线索二叉树、 中序线索二叉树和后序线索二叉树。 |
| 6,线索二叉树的目的是提高 该遍历过程的效率。 |
2,标志位的确立:
| 在节点的存储结构上增加两个标志位 | |
| 左标志ltag | 0 表示lchild指向左孩子节点 |
| 1 表示lchild指向前趋节点，即左线索 | |
| 右标志rtag | 0 表示rchild指向右孩子节点 |
| 1 表示rchild指向后继节点，即右线索 | |
| 节点结构 |  |
增加一个头节点:一中序遍历为例,如果一个节点的左指针域为空,查看这个节点的前驱,将ltag改为1,并且指向他中序遍历中的前驱,如果它中序遍历没有前驱,就指向头结点.如果一个节点的右指针域为空,查看这个节点的后驱,将rtag改为1,并且指向他中序遍历中的后驱,如果它中序遍历没有后驱,就指向头结点.
中序线索二叉树的中序遍历示例演示:
void ThInOrder(TBTNode *tb){TBTNode *p=tb->lchild;while (p!=tb){while (p->ltag==0) p=p->lchild;printf("%c",p->data);while (p->rtag==1 && p->rchild!=tb){p=p->rchild;printf("%c",p->data);}p=p->rchild;}} 四,哈夫曼树:
1,相关概念:
| 二叉树的带权路径长度: 设二叉树具有n个带权值的叶节点，那么从根节点到各个叶 节点的路径长度与相应节点权值的乘积的和，叫做二叉树的带权路径长度 |
| 哈夫曼树: 具有最小带权路径长度的二叉树称为哈夫曼树（也称最优 树） |
| 满二叉树不一定是哈夫曼树,具有相同节点的哈夫曼树不唯一 |
2,构建哈夫曼树:
| 构建哈夫曼树的原则: |
| 权值越大的叶节点越靠近根结点 |
| 权值越小的叶节点越远离根结点 |
| 哈夫曼树特点 |
| 哈夫曼树共有2n-1个节点(合并n-1次,产生n-1个新节点) |
| 哈夫曼树n1为0,n=n0+n1+n2,===> n=2n0-1 |
| 构造哈夫曼树的过程 |
| （1）给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶节点的二叉树， 从而得到一个二叉树的集合F={T1，T2，…，Tn}。 |
| （2）在F中选取根节点的权值最小和次小的两棵二叉树作为左、右子树 构造一棵新的二叉树，这棵新的二叉树根节点的权值为其左、右子树根节点权值之和。 |
| （3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉 树加入到集合F中。 |
| （4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树 便是所要建立的哈夫曼树。 |
3,哈夫曼编码:
前缀编码:设计一个长度不等的编码,必须使任意一字符的编码都不是另一字符的编码的前缀
| 什么样的前缀码能使电文总长最短??--哈夫曼编码 |
| 1,统计字符集中每个字符在电文中出现的概率 |
| 2,利用哈夫曼树的特点:权越大的叶子结点离根越远,将每个字符的概率作为权值,构造哈夫曼树 |
| 3,在哈夫曼树的左右分支上标0-1,从根到叶子结点的路径上的标号连接起来,作为该叶子结点的字符编码 |
