二叉树

1，基本概念

满二叉树

完全二叉树：节点从上到下，从左到右排下来。

平衡二叉树(AVL)：左右子树都是平衡二叉树，且左右子树的深度只差的绝对值不超过1；

节点的平衡因子：该节点的左子树的深度减去右子树的深度。平衡二叉树的所有节点的平衡因子只可能是0，1,-1

2，二叉树的性质

<1>在二叉树的第i(i>=1)层上至多有 2^(i-1) 个节点

<2>深度为k(k>=1)的满二叉树有 2^k-1 个节点，完全二叉树的节点范围：2^(k-1)-1<n<=2^k-1

<3>度为0的节点(终节点)数n0，度为1的节点数n1，度为2的节点数n1。则n0=n2+1 ; n=n1+2n2+1=n0+n1+n2

<4>有n个节点的完全二叉树，对任一节点i有：

PARENT(i)是i/2 (整除)；

若2i>n，则无左孩子，否则LCHILD(i)=2i；

若2i+1>n，则无右节点，否则RCHILD(i)=2i+1；

<5>深度为h的平衡二叉树，最小节点数：2^(h-1) 最大节点数：2^h-1

<6>深度为h的满三层二叉树的节点数：(3^n-1)/2

3，遍历二叉树

先序遍历：访问根节点，先序遍历左子树，先序遍历右子树

中序遍历：中序遍历左子树，访问根节点，中序遍历右子树

后序遍历：后序遍历左子树，后序遍历右子树，访问根节点

例题：前序序列为ABDGHCEFI，中序序列为GDHBAECIF，画出该二叉树

思路：ABDGHCEFI GDHBAECIF A是根节点，A的左子树(BDGH,GDHB)，右子树(CEFI,ECIF)

B C

D E F

G H I

4，线索二叉树

lchild

LTag

data

RTag

rchild

LTag 为 0时，lchild域指向节点的左孩子；为1时，lchild指向节点的前驱。

RTag 为 0时，rchild域指向节点的右孩子；为1时，rchild指向节点的后继。

5，树的存储结构

表示法：双亲表示法，孩子表示法，双亲孩子表示法，左孩子右兄弟表示法

6，哈夫曼树Huffman tree(最优二叉树)

树的带权路径长度(WPL)

哈夫曼编码

7，在一棵二叉树排序中（n个节点）：

每个节点的左子树上所有节点的值均小于该节点的值，右子树上所有节点的值均大于等于该节点的值；（在插入删除节点时，不能破坏这个规则）

按中序遍历得到的节点序列是一个有序序列；

进行查找插入删除时，算法的时间复杂度为O(log₂n)；

平均查找长度与树的形态有关：ASL=(1+2*2+3*4+4*2)/10=3

　　24　　　　55

12　　37　　53　　60

　　28　40

最坏的情况是二叉树是深度为n的单枝树，ASL=(n+1)/2，与单链表的顺序查找相同