计算机考研：数据结构常用算法精析(6)

kyone

　　线索化二叉树的遍历
    有了线索的二叉链表那么遍历就方便多了，不需要借助栈也不需要用递归了，因为他已经把前驱后继都连起来了，而不像二叉树那样，走不动的时候就只能退栈了。
而且遍历速度快。
    算法思路：先找到中序下的第一结点，访问之;若被访问的结点的右指针为线索指针，直接取其后继结点访问;……，直到被访问结点的右子树存在，再从相应右子起找中序下的第一结点，……，依次类推，直到整个树遍历完毕。
    算法描述：
    BTptr Tinorder(BTptr Thrt) //对中序线索二叉树的遍历//
    {
    BTptr p=T->lchild; //P 指向的是根结点
    while(p!=Thrt) //循环链表没有到头结点
    {
    while(p->Ltag==Link) p=p->Lchild; //找到中序下的第一结点//
    visit(p);
    while(p->Rtag==Thread&&p->Rchild!=Thrt)//如果右指针指向的是后继结点
    { p=p->Rchild; //那么就大胆的访问吧，取p后继结点,访问之//
    visit(p);
    }
    p=p->Rchild; // 如果不是后继结点，那么还得按照中序遍历的方法求得后继//
    }
    }
    在中序线索二叉树中，每一非空的线索均指向其祖先结点。
    在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点(该结点的后继指针指向祖先)，中序后继是其右子树上按中序遍历的最左边的结点(该结点的前驱指针指向祖先)。
    非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。
                    

kyfive

　　树的存储结构
    1.双亲表示法
    树中结点形式：
    其中data域存放结点的数据值(意义同前);parent域为该结点之父结点的地址(或序号)。描述如下：
    typedef struct tnode
    { datatype data;
    int parent ;
    } PTnode ;
    typedef struct
    { PTnode nodes[maxsize]; //树存储空间//
    int n ; //当前树的结点数//
    }Ptree ;
    2孩子表示法
    该表示法是采用链表结构来存储树的信息。
    (1)固定指针数表示法：设树T的度为d(d叉树)，即树中任一结点最多发出d个分支，所以结点定义为： data
    ch1
    ……
    chd
    (2)可变指针数表示法
    结点形式： data
    ch1
    ……
    chd
    d
    其中d为本结点的出度，chi为第i个孩子结点的指针。
    (3)孩子链表示法
    该表示法将树中每一结点的诸孩子组成单链表，若树中结点数为n，则有n个孩子链表(叶结点的链表为空)。又将n个链表的头结点组成头结点表。
                    

kyone

    头结点形式： data
    parent
    fchild
    其中data域存放结点的数据值;parent域为该结点之父结点的序号;fchild为指向本结点第一个孩子的指针。
    typedef struct CTnode //链表结点//
    { int child;
    struct CTnode * next;
    } *Childptr ;
    typedef struct //头结点//
    { datatype data; int parent;
    Childptr firstchild;
    } CTBox ;
    typedef struct
    { CTBox nodes[maxsize]; //头结点数组//
    int n ,root; //n为当前树中结点数，root为根结点所在位置//
    }CTree;
    ..
        3.孩子-兄弟表示法(或二叉树表示法
    data
    nextsibiling
    fchild
    结点形式(同二叉树链式结构)：
    其中fchild为指向本结点第一孩子的指针，而nextsiling为指向本结点右兄弟的指针。
    1.树T转换成二叉树BT(TÞBT)
    转换方法：对树T中每一结点，除保留第一孩子外，断开它到其它孩子的指针，并将各兄弟连接起来。转换后，原结点的第一孩子为左子，而原结点的右兄弟为其右子。
    在转换成的二叉树中，根结点的右子一定为空
    2森林F转换成二叉树BT(FÞBT)
    方法：先将F中各树转换成二叉树;然后各二叉树通过根的右指针相连。
                    

kythree

    3.二叉树BT恢复成森林F(BTÞF)
    这是FÞBT的逆变换。
    方法：对BT中任一结点，其Lchild所指结点仍为孩子，而Rchild所指结点为它的右兄弟，即“左孩子，右兄弟”。
    先序遍历森林F
    设F={ T1,T2,………..,Tm }，其中Ti(1≤i≤m)为F中第i棵子树。
    方法：若F≠φ，则：
    (1)访问F中T1之根;
    (2)先序遍历T1之根下的各子树(子森林);
    (3)先序遍历除T1之外的森林(T2,……,Tm)。
    显然(2)、(3)为递归调用，即：若子森林存在，仍按先序遍历方法对其遍历。
    方法等价为：先将F转换二叉树BT，然后对BT按前序(DLR)遍历，其结果是一样的。
    后序遍历森林F
    方法：若F≠φ，则：
    (1)后序遍历F中T1之根下的各子树(子森林);
    (2)访问T1之根;
    (3)后序遍历除T1之外的森林{ T2,……,Tm }。
    显然，(1)、(3)递归调用，即：若子森林存在，仍按后序遍历方法对其遍历。
    此方法等价为：先将F转换成二叉树BT，然后对BT按中序(LDR)遍历
    例题：设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有( C )个。 我不明白的题
    A. n-1 B.n C. n+1 D. n+2
    Huffman树
    设H树中叶结点数为n(即给定的权值个数)，因H树中出度=1的结点数为0，出度=2的结点数为n-1，故H树中总的结点数m=2n-1。因而可将树中全部结点存储在一个一维数组中。因而可将树中全部结点存储在一个一维数组中。
    由此写出构造H树的C语言描述算法：
                    

kytwo

    void HuffmTree (huffm HT[m+1] ) //构造H树的算法//
    {
    int i, j, p1, p2; int w, s1, s2;
    for (i=1,i
    { s2=s1; p2=p1; //以j结点为第一个权值最小的根结点//
    s1=HT[j].wi; p1=j;
    }
    else if (HT[j].wi
    {
    s2=HT[j].wi ;
    p2=j; //以j为第二个权值最小的根//
    }
    HT[p1].parent=HT[p2].parent=i; //构造新树//
    HT[i].Lchild=p1; HT[i].Rchild=p2;
    HT[i].wi =HT[p1].wi +HT[p2].wi; //权值相加送新结点//
    }
    }
                    

kyone

    求Huffman编码的算法：
    typedef struct
    { char bits[n+1]; //存放一个字符的Huffman编码
    int start; //存放该字符编码的最后一个位置
    char ch; //待编码字符//
    }ctype;
    void Huffmcode(ctype code[n+1]) //求n个字符的Huffman编码的算法//
    {
    int i, j, p, s; huffm HT[m+1]; //H树存储空间//
    ctype md; //存放当前编码的变量//
    for (i=1;i    Huffman译码
    译码是编码的逆运算。设电文(二进制码)已存入字符型文件fch中，译码过程：根据编码时建造的H树和相应的Huffman编码，从H树的根(序号为m)出发，逐个取电文中的二进制码，若当前二进制码=“0”，则走左子，否则走右子，一旦到达H树的叶结点，取相应叶结点中字符code[i].ch。重复上述译码过程，直到电文结束。算法如下：
    void Transcode(HuffmTree HT[m+1],ctype code[n+1])
    { int i, chat c; FILE *fp;
    if ((fp=fopen(“fch”,“r”))==NULL) Error(fch);
    //打开文件fch，只读，文件指针Þfp，打不开时出错处理//
    i=m; //取H树根结点序号//
    while ((c=fgetc(fp))!=EOF) //读入一个二进制码//
    {
    if(c= =‘0’)
    i=HT[i].Lchild; //向左走//
    else
    i=HT[i].Rchild; //向右走//
    if(HT[i].Lchild= =0) //HT[i]为叶子//
    { putchar (code[i].ch); //输出译出的字符//
    i=m;
    }
    }
    fclose(fp); //关闭文件fch//
    if (HT[i].Lchild!=0) Error(HT); //电文结束i未达到叶结点，则电文有误//
    }
    第6章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!