数据结构之树与二叉树

树的定义

树是一种非线性的数据结构。它是若干结点(A,B,C等都是结点)的集合，是由唯一的根(结点A)和若干棵互不相交的子树(如B,E,F,K,L这5个结点组成的树就是一棵子树)组成的。树的结点数目可以为0，当为0时，这棵树称为空树。

树的基本术语

节点的度：树中某个节点的子树的个数。

树的度：树中各节点的度的最大值。

分支节点：度不为零的节点。

叶子节点：度为零的节点。

路径：i->j；路径长度：路径经过节点数目减1。

孩子节点：某节点的后继节点；双亲节点：该节点为其孩子节点的双亲节点（父母节点）；兄弟节点：同一双亲的孩子节点；子孙节点：某节点所有子树中的节点；祖先节点：从树节点到该节点的路径上的节点。

节点的层次：根节点为第一层（以此类推）；树的高度：树中节点的最大层次。

有序树：树中节点子树按次序从左向右安排，次序不能改变；无序树：与之相反

森林：互不相交的树的集合。

二叉树的定义

1.每个结点最多只有两颗子树，即二叉树中结点的度只能为0，1，2。
2.子树有左右顺序之分，不能颠倒。

二叉树的主要性质

非空二叉树上叶子结点数等于双分支结点数加1

所有结点的分支数等于单分支结点数加上双分支结点数的两倍。

总分支数=总结点数-1

度为m的树中第i层最多有m^(i-1)个节点；二叉树的第i层上最多有2^(i-1)个结点。

高度(或深度)为k的二叉树最多有2^k -1(k>=1)个结点.换句话说，满二叉树中前k层的结点个数为2^k -1。

几种特殊的二叉树

斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点有：

1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

2）非叶子结点的度一定是2。

3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

二叉树的遍历

前序遍历：

中序遍历：

后序遍历：

树的遍历

二叉树的遍历算法

二叉树深度优先遍历的递归实现

先序遍历：

void preorder(BTNode *p)
{
    if(p!=NULL)
    {
        Visit(p)
        //假设访问函数Visit ()已经定义过，
        //其中包含了对结点p的各种访问操作，
        //如可以打印出p对应的数值。
        preorder(p->lchild);
        preorder(p->rchild);
    }
}

中序遍历：

void inorder(BTNode *p)
{
    if(p!=NULL)
    {
        preorder(p->lchild);
        Visit(p)
        //假设访问函数Visit ()已经定义过，
        //其中包含了对结点p的各种访问操作，
        //如可以打印出p对应的数值。
        preorder(p->rchild);
    }
}

后序遍历：

void postorder(BTNode *p)
{
    if(p!=NULL)
    {
        preorder(p->lchild);
        preorder(p->rchild);
         Visit(p)
        //假设访问函数Visit ()已经定义过，
        //其中包含了对结点p的各种访问操作，
        //如可以打印出p对应的数值。
    }
}

已知前序遍历序列为A,B,C,D,E,F,中序遍历序列为C,B,A,E,D,F,则后序遍历序列为：

前序：A,B,C,D,E,F
中序：C,B,A,E,D,F
先看前序遍历序列，则知道A为根结点，再看中序遍历序列，C,B,A,E,D,F ,A左边的为左子树，A右边的为右子树
再看前序序列，B为根节点，又因为中序系列中C在B的左边，所以C为B的左子树，再看前序序列，D为根节点，再看中序序列(只需看A的右边)，E,D,F，显然E为D的左子树，F为D的右子树。
则后序遍历序列为CBEFDA

已知后序遍历序列为D,E,C,B,H,G,F,A,中序遍历序列为B,D,C,E,A,F,H,G,则前序遍历序列为：

后序：D,E,C,B,H,G,F,A
中序：B,D,C,E,A,F,H,G
先看后序遍历序列，则知道A为根结点，再看中序遍历序列，B,D,C,E为A的左子树部分，F,H,G为A的右子树部分,再看后序序列，F为根节点，因为H,G在F的右边，所以，H,G,为F的又子树，再看后序序列，G为根结点，再看中序序列，H在G的左边，所有，H为G的左子树，再看后序序列，B为根结点，再看中序序列，则知DCE为B的右子树部分，再看后序序列，C为根结点，再看中序序列(DCE)，知D为C的左子树，E为C的右子树。
则前序遍历序列为：A,B,C,D,E,F,G,H

二叉树遍历算法的改进

二叉树深度优先遍历的非递归实现

……

赫夫曼树和赫夫曼编码

赫夫曼树又叫作最优二叉树，它的特点是带权路径最短。

关于几个路径的概念：

1.路径：路径是指从树中一个结点到另一个结点的分支所构成的路线。
2.路径长度：路径长度是指路径上的分支数目。
3.树的路径长度：树的路径长度是指从根到每个结点的路径长度之和。
4.带权路径长度：结点具有权值，从结点到根之间的路径长度乘以结点的权值，就是该结点的带权路径长度。
5.树的带权路径长度(WPL)：树的带权路径长度是指树中所有叶子结点的带权路径长度之和。