计算机备考资料：数据结构基本概念(六)

《计算机备考资料：数据结构基本概念(六)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构：基本概念(六)Ø线索二叉树的定义　　在一个具有n个结点的二叉链表中，利用n+1个空指针域存放指向该结点在某种遍历序列中的前驱和后继结点的指针，这些指向前驱和后继结点的指针称为线索，加上线索的二叉树称为线索二叉树，相应地，加上线索的二叉链表称为线索链表。　　Ø线索二叉树的存储结构定义　　线索链表中的结点定义如下：　　enumflag{Child,Thread};//枚举类型，枚举常量Child=0，Thread=1　　structThrNode　　{　　ElemTypedata;//ElemType表示不确定的数据类型　　ThrNode*lchil

2、d,*rchild;　　flagltag,rtag;　　}*root;//root表示线索链表的头指针　　Ø树的存储结构　　包括：双亲表示法、孩子表示法、孩子兄弟表示法。　　双亲表示法的存储结构定义如下：　　#defineMaxSize100;//树中最大结点个数　　structPNode//数组元素的类型　　{　　ElemTypedata;//树中结点的数据信息，　　intparent;//该结点的双亲在数组中的下标　　};　　PNodeTree[MaxSize];　　孩子表示法的存储结构定义如下：　　structCTNode//孩子结点　　{　　int

3、child;　　CTNode*next;　　};　　structCBNode//表头结点　　{　　ElemTypedata;　　CTNode*firstchild;//指向孩子链表的头指针　　};　　孩子兄弟表示法又称为二叉链表表示法，存储结构定义如下：　　structTNode　　{　　ElemTypedata;//ElemType表示不确定的数据类型　　TNode*firstchild;//firstchild指向该结点的第一个孩子　　TNode*rightsib;//rightsib指向该结点的右兄弟　　};　　Ø树转换为二叉树　　树转换为二叉树的方

4、法是：　　⑴加线——树中所有相邻兄弟结点之间加一条连线;　　⑵去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线;　　⑶层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。　　Ø森林转换为二叉树　　森林转换为二叉树的方法如下：　　⑴将森林中的每棵树转换成二叉树;　　⑵从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，所得到的二叉树就是由森林转换的二叉树。　　Ø二叉树转换为树或森林　　树和森林转换为二叉树的过程是可逆的，将一棵二叉树还原为树或森林的方法

5、如下：　　⑴加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来;　　⑵去线——删去原二叉树中所有的双亲结点与右孩子结点的连线;　　⑶层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。　　树的遍历序列与二叉树的遍历序列之间的对应关系　　根据树与二叉树的转换关系以及树和二叉树遍历的操作定义可知，树的遍历序列与由树转化成的二叉树的遍历序列之间具有如下对应关系：树的前序遍历序列等于二叉树的前序遍历序列，树的后序遍历序列等于二叉树的中序遍历序列。　　Ø哈夫曼树中叶子结点的权值　　叶子结点的权值是指对叶子结点

6、赋予的一个有意义的数值量。　　Ø二叉树的带权路径长度　　设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和称做二叉树的带权路径长度，记为：　　WPL=其中，wk为第k个叶子结点的权值;lk为从根结点到第k个叶子结点的路径长度。　　Ø哈夫曼树定义　　给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，将其中带权路径长度最小的二叉树称为哈夫曼树，也称为最优二叉树。　　Ø哈夫曼算法的基本思想　　哈夫曼算法的基本思想是：　　⑴初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个

7、二叉树集合F={T1，T2，…，Tn};　　⑵选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和;　　⑶删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中;　　⑷重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。文后寄语：book118是一个专注于电子文档的在线分享平台，用户在此平台上不但可以自由交换文档，还可以分享最新的行业资讯。book118制定了严格的文档审核策略，以保证文档来源的合法性，对有可能引起知识产权纠

8、纷的文档，网站不予收录。同时，道客巴巴采用了行业领先的文档加密及保