数据结构与算法第五章树

度：结点子女个数为该结点的度；树中各结点度最大值为树的度。

结点层次：根结点在第一层，其子女结点层次等于其层次$+1$。

结点深度：结点深度即结点层次；离根最远结点层次即为树的深度。

结点高度：叶结点的高度为1，其双亲结点高度等于自己高度$+1$。

有序树/无序树，树中结点的各子树有次序/无次序，可以/不可以交换位置。

二叉树

根据先序、中序序列/中序、后序序列确定一棵二叉树

对二叉树，设度为$i$结点有$n_i$个，则$n_0＝n_2+1$

二叉树的链表表示（二叉链表，三叉链表）

利用二叉树前序遍历建立二叉树

以递归方式建立二叉树。输入结点值的顺序必须对应二叉树结点前序遍历的顺序，并约定以输入序列中不可能出现的值作为空结点的值以结束递归,

线索化二叉树

通过二叉树遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。

希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。

ltag 和 rtag，指明指针是指示子女还是前驱／后继。后者称为线索。

ltag (rtag) = 0，表示相应指针指示左子女（右子女）；ltag (rtag) = 1, 表示相应指针指示前驱（后继）线索。

根据给出的二叉树画出相对应遍历顺序的线索树

$n$个结点的线索二叉树上含有的线索数为$\boxed{n+1}$

树与森林

树的存储方式

1）广义表表示

2）双亲表示（存data和parent）

3）子女链表表示（无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。）

4）子女-指针表示：每一个结点包含的指针个数为树的度，记为$d$，则空指针数为$nd-n+1$

5）子女—兄弟表示（存第一个子女与兄弟）

先根次序遍历（对应子女—兄弟表示二叉树表示前序遍历），后根次序遍历（根最后访问）（对应子女—兄弟表示二叉树表示中序遍历）

广度优先（层次次序）遍历

将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。森林与二叉树表示的转换可以借助树的二叉树表示来实现。

将森林借助子女—兄弟表示法转化为二叉树，其中根均为兄弟，先转各树，再转森林。

森林的两种遍历同树的两种遍历

堆

完全二叉树，且每个节点均小于/均大于其左右孩子

会画直接调整，单次插入，单次删除的流程

将一组用数组存放的任意数据调整成堆的方法：逐个插入，$O(n\log_2n)$；直接调整，$O(n)$，选用优的方式，构建堆的时间复杂度为$O(n)$

最小堆的每次插入，时间复杂度为$O(\log_2n)$

template <class E>
MinHeap<E>::MinHeap (int sz) 
{
     maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize;
     //三目运算符的解释：wei'zhen
     heap = new E[maxHeapSize];//创建堆空间
     if (heap == NULL) 
     {
          cerr << “堆存储分配失败！” << endl;  exit(1);
     }
     currentSize = 0;//建立当前大小
};
template <class E>
MinHeap<E>::MinHeap (E arr[], int n) 
{
     maxHeapSize = (DefaultSize < n) ? n : DefaultSize;
     heap = new E[maxHeapSize]; 
     if (heap == NULL) 
     {
        cerr << “堆存储分配失败！” << endl;  exit(1);
     }
     for (int i = 0; i < n; i++) heap[i] = arr[i];
     currentSize = n;//复制堆数组, 建立当前大小
     int currentPos = (currentSize-2)/2;    
     //找最初调整位置:最后分支结点
     while (currentPos >= 0) 
     {      //逐步向上扩大堆
           siftDown (currentPos, currentSize-1);
            //局部自上向下下滑调整
           currentPos--;
     }                  
};

//最小堆下滑调整算法
template <class E>
void MinHeap<E>::siftDown (int start, int m ) 
{
//私有函数: 从结点start开始到m为止, 自上向下比较, 
//如果子女的值小于父结点的值,则关键码小的上浮, 
//继续向下层比较, 将一个集合局部调整为最小堆。
//由于堆存储在下标从 0 开始计数的一维数组中，故结点下标不超过n-1
    int i = start,j = 2*i+1;//j是i的左子女位置
    E temp = heap[i];           
    while (j <= m) 
    {//检查是否到最后位置
        if ( j < m && heap[j] > heap[j+1] ) j++;//让j指向两子女中的小者
        if ( temp <= heap[j] ) break;//小则不做调整
        else 
        { 
            heap[i] = heap[j];  
            i = j; 
            j = 2*j+1; 
        }//否则小者上移, i, j下降
     }
     heap[i] = temp;//回放temp中暂存的元素，即将i的值放到它应该要去的位置
};

//最小堆的插入
//每次插入都加在堆的最后，再自下向上执行调整，使之重新形成堆
template <class E>
bool MinHeap<E>::Insert (const E& x )  {
//公共函数: 将x插入到最小堆中
    if ( currentSize == maxHeapSize )
    { 
        cerr << "Heap Full" << endl;
        return false; 
    }
    heap[currentSize] = x;//插入
    siftUp (currentSize);//向上调整
    currentSize++;//堆计数加1，此处借当前插入个数与末尾下标玩了个花招
    return true;
};
template <class E>
void MinHeap<E>::siftUp (int start) 
{
//私有函数: 从结点start开始到结点0为止, 自下向上
//比较, 如果子女的值小于父结点的值, 则相互交换, 
//这样将集合重新调整为最小堆。关键码比较符<=
//在E中定义。
    int j = start,i = (j-1)/2;//j表示起始结点位置，i表示其父亲位置 
    E temp = heap[j];//这一句是什么意思？也就是这个j的值应该要去的位置。
    while (j > 0) //j=0则不用向上调整了。
    {//沿父结点路径向上直达根
        if (heap[i] <= temp) break;//父结点值小, 不调整
        else 
        { 
            heap[j] = heap[i];//这里的赋值只是换掉原先的位置，对于最终位置的赋值没有考虑
            j = i;  
            i = (i-1)/2; 
        }
        //父结点结点值大, 调整
    }   
    heap[j] = temp;//回送
};

//最小堆的删除（注意维持堆的完全二叉树的形态）只能删除头节点（也就是优先队列队头）
template <class E>
bool MinHeap<E>::Remove (E& x) 
{
    if ( !currentSize ) 
    {
        cout << "Heap empty" << endl;  
        return false;
    }
    x = heap[0];  
    heap[0] = heap[currentSize-1];
    currentSize--;
    siftDown(0, currentSize-1);//自上向下调整为堆
    return true;            //返回最小元素
};

Huffman树

路径长度（PL）：连接两结点路径上分支构成路径，长度为分支数。

外部路径长度（$EPL$）：各叶结点（外结点）到根结点的路径长度之和。

内部路径长度（$IPL$）：各非叶结点（内结点）到根结点的路径长度之和。

树的路径长度为$EPL+IPL$。

$n$个节点的二叉树路径数不小于下述数列前$n$项和：$\displaystyle \sum_{i=1}^{n} floor( \log_2i) $,$\displaystyle \sum_{i=1}^{n} \lfloor \log_2 i \rfloor$，完全二叉树满足此要求。

带权路径长度，权$w_i$为外结点所带，其到根的路径长度为$l_i$，树的带权路径长度为$\displaystyle WPL=\sum_{i=1}^{n}w_i*l_i$

注意：带权路径长度的计算只考虑外结点

带权路径长度达到最小的扩充二叉树即为Huffman树。在Huffman树中，权值大的结点离根最近。

Huffman编码，实现数据压缩。先进行Huffman树构建，再进行分支编码。而且此种编码是一种前缀编码，即任一个二进制编码不是其他二进制编码的前缀，解码时不会混淆，例如A=0，T=00，来了00是解码成T还是AA呢？

数据结构与算法第五章 树

数据结构与算法第五章树