树

重点 树的基本概念和术语 二叉树的概念及性质 二叉树的存储结构 遍历二叉树 线索二叉树 树的应用：哈夫曼树 顺序存储 链式存储 递归算法 非递归算法 线索二叉树 树的应用：哈夫曼树

7.1 树的概念和性质 树的定义（P85） 树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件： 7.1 树的概念和性质 树的定义（P85） 树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件： ⑴ 有且仅有一个特定的称为根的结点； ⑵ 当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。 树的定义是采用递归方法

树的形式定义 D={ai | ai∈ElemSet，i=1,…,n} 二元关系S的定义： 当n=1时，S=φ； 当n>1时：

树的基本术语（P86） 结点的度：结点所拥有的子树的个数。 叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。 树的度：树中各结点度的最大值。 孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。 路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1<=i<k），则把n1, n2, …, nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。

树的基本术语（续） 祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。 结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第i层，则其孩子结点在第i+1层。 树的深度：树中所有结点的最大层数，也称高度。 有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。 森林：m (m≥0)棵互不相交的树的集合。

7.2 二叉树的概念和性质 研究二叉树的意义？ 二叉树的结构相对简单，其运算也自然简单，便于初学者入门。 7.2 二叉树的概念和性质 研究二叉树的意义？ 二叉树的结构相对简单，其运算也自然简单，便于初学者入门。 由于多叉树可以借助一定的规则转换为二叉树，因此二叉树结构在应用中具有非常重要的地位。

7.2 二叉树的概念和性质 二叉树的定义（P88） 二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

7.2 二叉树的概念和性质 二叉树的特点 每个结点的度只可能是0，1，2； 7.2 二叉树的概念和性质 二叉树的特点 每个结点的度只可能是0，1，2； 二叉树是有序树，即使某结点只有一棵子树，也要区分该子树是左子树还是右子树。

7.2 二叉树的概念和性质 二叉树的5种基本形态（P89）

7.2 二叉树的概念和性质 例：画出具有3个结点的树和具有3个结点的二叉树的形态 二叉树和树是两种树结构。

7.2 二叉树的概念和性质 特殊的二叉树 满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 7.2 二叉树的概念和性质 特殊的二叉树 满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 满二叉树的特点： 叶子只能出现在最下一层； 只有度为0和度为2的结点。 完全二叉树：深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树从编号1到n的结点一一对应是时，称为完全二叉树。

7.2 二叉树的概念和性质 p89 性质1 ：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。 性质2：二叉树的第i层上最多有2i-1个结点（i≥1）。 性质3：一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。

7.2 二叉树的概念和性质

7.2 二叉树的概念和性质 性质4 具有n个结点的完全二叉树的深度为 log2n +1。 7.2 二叉树的概念和性质 性质4 具有n个结点的完全二叉树的深度为 log2n +1。 性质5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有： (1)如果i＞1，则结点i的双亲结点的序号为 i/2；如果i＝1，则结点i是根结点，无双亲结点。 (2)如果2i≤n，则结点i的左孩子的序号为2i； 如果2i＞n，则结点i无左孩子。 (3)如果2i＋1≤n，则结点i的右孩子的序号为2i＋1 如果2i＋1＞n，则结点 i无右孩子。

7.2 二叉树的概念和性质 性质六：给定n个结点，能构成H(n)种不同的二叉树：

考研真题 具有3个结点的二叉树有( )种 有10个叶子结点的二叉树中有（ ）个度为2的结点。 具有3个结点的二叉树有( )种 有10个叶子结点的二叉树中有（ ）个度为2的结点。 二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） 一棵完全二叉树有1001个结点，其中叶子结点的个数是（ ） 高度为4的完全二叉树至少有（ ）个结点 高度为5的完全二叉树至多有（ ）个结点

7.3.1 二叉树的顺序存储结构（P91） 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系——父子关系。 如何利用数组下标来反映结点之间的逻辑关系? 二叉树的性质5为二叉树的顺序存储指明了存储规则：依照完全二叉树的结点编号次序，依次存放各个结点。 注意：C/C++中数组的起始地址为0，编号为i的结点存储在下标为i1的单元内。 完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系 。

7.3.1 二叉树的顺序存储结构 #define MAX_TREE_SIZE 100 //为最大结点数 7.3.1 二叉树的顺序存储结构 #define MAX_TREE_SIZE 100 //为最大结点数 Typedef Telemtype SqBitree(MAX_TREE_SIZE);//0号单元存储根结点， SqBitree bt;

7.3.1 二叉树的顺序存储结构 非完全二叉树修补结构不存在的结点，用特殊符号标识。

7.3.1 二叉树的顺序存储结构 顺序存储结构适用于？ 完全二叉树 7.3.1 二叉树的顺序存储结构 顺序存储结构适用于？ 完全二叉树 在最坏的情况下，一个深度为K且只有K个结点的单支树，树中不存在度为2的结点，却需要长度为2k-1的一维数组

7.3.2 二叉树的链式存储结构（P92） 基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。 结点结构： lchild data rchild 其中，data：数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。

二叉链表结构定义 lchild data rchild 左孩子结点 右孩子结点 struct BiNode { T data; // 结点数据 BiNode<T> *lchild; // 左孩子的指针 BiNode<T> *rchild; // 右孩子的指针 };

7.3.2 二叉树的链式存储结构 A B C D E F G 具有n个结点的二叉链表中，有多少个空指针？ A B C ∧ D E F ∧ ∧ 7.3.2 二叉树的链式存储结构 A B C D E F G A B C ∧ D E F ∧ ∧ ∧ G ∧ 具有n个结点的二叉链表中，有多少个空指针？

7.3.2 二叉树的链式存储结构 A B C D E F G 具有n个结点的二叉链表中，有n+1个空指针。 A B C ∧ D E F ∧ 7.3.2 二叉树的链式存储结构 A B C D E F G A B C ∧ D E F ∧ ∧ ∧ G ∧ 具有n个结点的二叉链表中，有n+1个空指针。

7.4 二叉树的遍历 二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。 前序遍历 7.4 二叉树的遍历 二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。 前序遍历 中序遍历 后序遍历 层序遍历 抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。 二叉树遍历操作的结果？ 非线性结构线性化

7.4 二叉树的遍历 二叉树 根结点D 考虑二叉树的组成： 左子树L 右子树R 如果限定先左后右，则二叉树遍历方式有三种： 前序：DLR 7.4 二叉树的遍历 根结点D 左子树L 右子树R 二叉树 考虑二叉树的组成： 如果限定先左后右，则二叉树遍历方式有三种： 前序：DLR 中序：LDR 后序：LRD 层序遍历：按二叉树的层序编号的次序访问各结点。

7.4 二叉树的遍历 前序遍历的概念 A B C D E F G 前序遍历序列：A B D G C E F ①若二叉树为空，则空操作返回； 7.4 二叉树的遍历 前序遍历的概念 ①若二叉树为空，则空操作返回； （否则） ②访问根结点； ③前序遍历根结点的左子树； ④前序遍历根结点的右子树。 A B C D E F G 前序遍历序列：A B D G C E F

前序遍历——递归算法 Void trave (BTNode *p) { if (p!=Null) visit(p); Trave (p->lchild); Trave (p->rchild); }// 假设 visit()已定义过，包含对结点P的各种访问操作，如打印出P对应的数值 // States printelem( Telemtype e) { Print(e); return OK; }

7.4 二叉树的遍历 中序遍历的概念 A B C D E F G 中序遍历序列：D G B A E C F ①若二叉树为空，则空操作返回； 7.4 二叉树的遍历 中序遍历的概念 ①若二叉树为空，则空操作返回； （否则） ②中序遍历根结点的左子树； ③访问根结点； ④中序遍历根结点的右子树。 A B C D E F G 中序遍历序列：D G B A E C F

中序遍历——递归算法 void inorder (BTNode *p) { if (p==NULL) return; // ① InOrder(p->lchild); // ③ cout << p->data; // ② InOrder(p->rchild); // ④ }

7.4 二叉树的遍历 A 后序遍历的概念 B C D E F G 后序遍历序列：G D B E F C A ①若二叉树为空，则空操作返回； 7.4 二叉树的遍历 后序遍历的概念 ①若二叉树为空，则空操作返回； （否则） ②后序遍历根结点的左子树； ③后序遍历根结点的右子树。 ④访问根结点； A B C D E F G 后序遍历序列：G D B E F C A

后序遍历——递归算法 Void PostOrder (BTNode *p) { if (p==NULL) return; // ① PostOrder(p->lchild); // ③ PostOrder(p->rchild); // ④ cout << p->data; // ② } Void trave (BTNode *p) { if (p!=Null) {// (1) Trave (p->lchild); // (2) Trave (p->rchild); // (3) }//假设 visit()已定义过， visit(p);放在不同的位置，表示不同的遍历方式。

7.4 二叉树的非递归遍历 思想： Void inorder(BTNode *bt) { BTNode *stack[maxsize];Int top=-1; BTNode *p; If(bt!=NULL) { p=bt; While (top!=-1|| P!=NULL) { while(P!=NULL)//左孩子存在，则左孩子入栈，即各层结点的所有左孩子进栈 { stack[++top]=p; p=p->lchild; } If(top!=-1) //在栈不空的情况下出栈左孩子 { p=stack[top--]; cout <<p->data<<" "; p=p->rchild; } } 7.4 二叉树的非递归遍历 中序遍历二叉树的非递归算法： 指向根结点的指针，当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈 若栈顶记录中的指针值为空，则应退到上一层，若是从左子树返回，则应访问当前层，即栈顶记录中指针所指的根结点； 若是从右子树返回，则表明当前层的遍历结束，则应继续退栈。 思想： 开始根结点入栈， 循环执行如下操作：如果栈顶结点左孩子存在，则左孩子入栈，如果栈顶结点左孩子不存在，则出栈并输出栈顶结点，然后检查其右孩子是否存在，如果存在，则右孩子入栈。 当栈空时且已遍历完时算法结束。

7.4 二叉树的非递归遍历 用自己申请的栈来代替系统栈，先序遍历： Void preorder(BTNode *bt) 7.4 二叉树的非递归遍历 用自己申请的栈来代替系统栈，先序遍历： Void preorder(BTNode *bt) { BTNode *stack[maxsize]; Int top=-1; BTNode *p; If(bt!=NULL) { stack[++top]=bt; //根结点先入栈 While (top!=-1) { p=stack[top--]; cout <<p->data<<" ";// 出栈并输入栈点结点 If (p->rchild!=NULL) { stack[++top]= p->rchild; } If (p->lchild!=NULL) { stack[++top]= p->lchild; } }

7.4 二叉树的遍历 层次遍历的概念 二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 A B C D E F G 层序遍历序列：A B C D E F G

二叉树的层次遍历算法 队列Q初始化； 2. 如果二叉树非空，将根指针入队； 3. 循环直到队列Q为空 3.1 p=队列Q的队头元素出队；

7.4 二叉树的遍历 层次遍历 A B C D E F G A B C D E F G 遍历序列： A B C D E F G

层次遍历——非递归算法 void level(BTNode *p) // 层次遍历二叉树 { int front, rear; BTNode *que[maxsize] // 定义一个循环队列，用于记录将要访问的层次上的结点 front=rear=0; //初始化循环队列 BTNode *q; If(p!=Null) { rear=(rear+1)%maxsize; Que[rear]=p; //根结点入队 While(front!=rear) //当队列为空时循环 { front=(front+1)%maxsize; Q=que[front];//队头结点出队 Visit(q); If(q->lchild!=Null) { rear=(rear+1)%maxsize; Que[rear]=q->lchild; } If(q->rchild!=Null) { rear=(rear+1)%mazsize; Que[rear]=q->rchild; } }

二叉树的遍历的应用 若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？ 例：已知前序序列为ABC，则可能的二叉树有5种。 A B C A B C

若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？ 例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。 A B C A B C

若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢?

前序：A B C D E F G H I中序：B C A E D G H F I

前序：F G H I 中序：G H F I FG HI 前序： D E F G H I 中序： E D G H F I A B C D E

试题例： 试找出分别满足下列条件的所有二叉树 ①先序序列和中序序列相同 ②中序序列和后序序列相同 ③先序序列和后序序列相同 ④前序和后序遍历正好相反： 根据二叉树的前序和中序、中序和后序两对遍历序列都可以唯一确定这棵二叉树。

考研真题： 一棵二叉树的先序遍历序列是A，B，C，D，E，F，中序遍历序列为C，B，A，E，D，F，则后序遍历序列为： C，B，E，F，D，A

E F D G A B / + * - C 考研真题3 1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( ) 【北京航空航天大学 1999 一、3 （2分)】 2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、 3. 设有一表示算术表达式的二叉树（见下图），【南京理工大学1999 一、20（2分）】它所表示的算术表达式是（ ） 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）【南京理工大学 2000 一、8 （1.5分）】 5. 在下述结论中，正确的是（ ）【南京理工大学 99 一4 （1分） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树 A．①②③ B．②③④ C．②④ D．①④

考研真题4 27. 利用二叉链表存储树，则根结点的右指针是（ ）。【青岛大学 2001 五、5 （2分）】 27. 利用二叉链表存储树，则根结点的右指针是（ ）。【青岛大学 2001 五、5 （2分）】 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 28．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。【北京理工大学 2000 一、4 （2分）】 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 29．树的后根遍历序列等同于该树对应的二叉树的( ). 【北京理工大学 2001 六、6 （2分）】 A. 先序序列 B. 中序序列 C. 后序序列

考研真题5 4. 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？ 【中国人民大学2001二、3(4分）】 5．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。【东北大学 2000 三、1 （4分）】

小结 树的基本概念和术语 二叉树的概念 二叉树的性质 二叉树的存储：顺序、链式 二叉树的遍历

倒装 Ｐ222，2008年阅读1P3S1 Adding to a woman’s increased dose of stress chemicals , are her increased “opportunities” for stress. Ｐ240，2008　Ｐart A P2S4 And only over the past 30years have scholars examined history form the bottom up. 女性承受越来越多的压力的机会使她们因压力而产生的化学物质不断增加。 仅仅是在过去30年里，学者们才开始从头仔细研究历史。

复习： 树的基本概念和术语 二叉树的概念、满二叉树，完全二叉树 二叉树的性质 二叉树的存储：顺序、链式 二叉树的遍历

第二节：线索二叉树、森林、树的应用 二叉树遍历的应用 线索二叉树 树和森林 树的三种存储结构 森林与二叉树的转换 树和森林的遍历 Huffman树

7.4 二叉树的遍历的应用 二叉树的建立 如何由一种遍历序列生成该二叉树？ 7.4 二叉树的遍历的应用 二叉树的建立 遍历是二叉树各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。 如何由一种遍历序列生成该二叉树？ 为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“*”，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。

* D B A C D B A C 扩展二叉树的前序遍历序列：A B * D * * C * *

由带空指针标记的先序序列构造二叉树的算法 D B A C 前序遍历 ①若二叉树为空，则空操作返回； （否则） ②访问根结点； ③前序遍历根结点的左子树； ④前序遍历根结点的右子树。 前序创建 ①若输入为*(空)，则root=NULL （否则） ②创建根结点； ③前序创建根结点的左子树； ④前序创建根结点的右子树。

按先序序列建立二叉树的二叉链表的过程 Status CreateBitree(Bitree &T){ //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树 //构造二叉链表表示的二叉树T Scan(&ch); if (ch=='*') T= NULL; // 特殊数据标记空指针 Else { if(!(T(BiTNode *)malloc(sizeof(BITNode))) exit(overflow); // 创建新结点 T->data=ch;//生成根结点 CreateBitree( T->lchild);// 创建左子树 CreateBitree( T->lchild);// // 创建右子树 }return OK; }CreateBitree

7.5 二叉树的其他操作算法 遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。 计算二叉树的结点数 （P104） 计算二叉树的叶子节点数 计算二叉树的高度（P105）

计算一棵给定二叉树的所有结点数 方法一：思想：遍历二叉树的时候，设全局变量n计数。 方法二：先数左子树的结点，再计算右子数的结点 Int n; Void count(BTNode *p) { If(p!=NULL) { ++n; count(P->lchild); count(p->rchild); } } int count(BTNode *p) { int n1,n2; If(p=NULL) return 0; else { n1= count(P->lchild); n2= count(p->rchild); return(n1+n2+1); } }

统计所有叶子点数 思想：加一个判断条件，叶子结点左右子树都为空 Int n; Void count(BTNode *p) { If(p!=NULL) { ++n; count(P->lchild); count(p->rchild); } } Int n; Void count(BTNode *p) { If(p!=NULL) { if (P->lchild==NULL&&p->rchild==NULL) ++n; count(P->lchild); count(p->rchild); }

统计所有叶子点数 int count(BTNode *p) { int n1,n2; If(p=NULL) return 0; else { n1= count(P->lchild); n2= count(p->rchild); return(n1+n2+1); } } { int left,right; if(p==NULL) return(0); if(root->lchild==NULL && root->rchild==NULL) return 1; left= LeafCount(p->lchild); right=LeafCount(p->rchild); return left+right; }// 统计叶子结点的个数

求某个结点的层号 思想：用遍历查找结点，在遍历的过程中，用L记录层号，当P第一次来某结点或P将要由这个结点走向下层结点时，++L；当P第三次来到这个结点或P将要由这个结点返回到上层结点时--L Int L; Void leno( BTNode *p, char x) { If(p !=NULL) { If(P->data==x) { cout<<L<<endl ; } ++L; Leno(P->lchild,x); Leno(P->rchild,x); --L; }

求二叉树的深度 int Height（BTNode *p) { int left,right; if(p==NULL) return(0); left =Height(p->lchild); right=Height(p->rchild); if (left>right) return left+1; return right+1; }

7.6.1 线索二叉树的概念 二叉树各种遍历算法，其本质是将树形结构转换为线性序列，便于简化问题。 7.6.1 线索二叉树的概念 二叉树各种遍历算法，其本质是将树形结构转换为线性序列，便于简化问题。 在遍历序列中，每个结点都有自己的前驱和后继，求结点的前驱和后继属于基本操作。快速地实现这个基本操作，对二叉树许多算法的性能有重要意义。 最简单的方法是在遍历过程中寻求答案，缺点是时间复杂度等同遍历算法的时间复杂度O(n)，这对于基本操作而言，显然效率太低。 为了实现在遍历序列中快速查找结点的前驱、后继，可以利用二叉链表中空的指针域，指向结点在遍历序列中的前驱、后继，这些指向前驱和后继的指针称为线索。

7.6.1 线索二叉树的概念 线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索； 7.6.1 线索二叉树的概念 线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索； 线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化； 线索二叉树：加上线索的二叉树称为线索二叉树。

7.6.1 线索二叉树的概念 Ltag data rtag rchild 结点结构 0: lchild指向该结点的左孩子 7.6.1 线索二叉树的概念 lchild Ltag data rtag rchild 结点结构 0: lchild指向该结点的左孩子 1: lchild指向该结点的前驱结点 0: rchild指向该结点的右孩子 1: rchild指向该结点的后继结点 ltag= rtag=

7.6.1 线索二叉树的概念 Typedef struct TBTNode { char data; Int ltag,rtag; 7.6.1 线索二叉树的概念 lchild Ltag data rtag rchild 结点结构 Typedef struct TBTNode { char data; Int ltag,rtag; Struct TBTNode *lchild; Struct TBTNode *rchild; };

7.6.1 线索二叉树的概念 二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树： ⑴ 前序线索二叉树 7.6.1 线索二叉树的概念 二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树： ⑴ 前序线索二叉树 ⑵ 中序线索二叉树 ⑶ 后序线索二叉树 ⑷ 层序线索二叉树

线索二叉树的画法 前序线索二叉树： 前序序列为：ABCD

线索二叉树的画法 中序线索二叉树： 中序序列为：BADC

线索二叉树的画法 后序线索二叉树： 后序序列为：BDCA

中序线索链表上查找结点P的后继 对于中序线索二叉树上的任一结点，寻找其中序的后继结点，有以下两种情况： 1）如果该结点的右标志为1，即无右孩子，那么其右指针域所指向的结点便是它的后继结点； 2）如果该结点的右标志为0，表明该结点有右孩子，根据中序遍历的定义，它的后继结点是以该结点的右孩子为根结点的子树的最左结点，即沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继结点。

对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况： 中序线索链表上查找结点P的前驱 对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况： 1）如果该结点的左标志为1，即无左孩子，那么其左指针域所指向的结点便是它的前驱结点； 2）如果该结点的左标志为0，即有左孩子，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。

中序遍历对二叉树线索化的递归算法 Void Inthread (TBTNode *p, TBTNode *&pre) { if(p!=NULL) { TBTNode *pre=NULL; //前驱结点指针 inthread(p->lchild, pre);//递归，左子树线索化 If(p->lchild==NULL) { p->lchild=pre; P->ltag=1;}//建立前驱线索 If(pre->rchild==NULL &&pre!=NULL ) {Pre->rchild=p;Pre->rtag=1;}//建立后继线索 Pre=p; //前驱跟上，当前指针向前遍历 Inthread(p->rchild,pre); //递归，右子树线索化 Pre->rchild=NULL;Pre->rtag=1; }

7.7.1 树的逻辑结构 树的遍历 如何理解访问? 遍历的实质? 如何理解次序? 7.7.1 树的逻辑结构 树的遍历 从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。 如何理解访问? 抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。 遍历的实质? 树结构（非线性结构）→线性结构。 如何理解次序? 树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。

A C B G F E D H I 树的先根遍历操作定义为： 若树为空，则空操作返回；否则 ⑴ 访问根结点； ⑵ 按照从左到右的顺序前序遍历根结点的每一棵子树。 先根遍历序列： A B D E H I F C G

A C B G F E D H I 树的后根遍历操作定义为： 若树为空，则空操作返回；否则 ⑴ 按照从左到右的顺序后序遍历根结点的每一棵子树； ⑵ 访问根结点。 后根遍历序列： D H I E F B G C A

7.7.2 树的存储结构 实现树的存储结构，关键是什么? 如何表示树中结点之间的逻辑关系。 思考问题的出发点 如何表示结点的双亲和孩子

7.7.2 树的存储结构 1）双亲表示法 以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。

7.7.2 树的存储结构 2）多叉链表表示法 二叉树的二叉链表结构采用两个指针域存储结点可能有的孩子指针。树的多叉链表表示法延伸了这种结构设计：若树的度为K，则在结点结构中设置K个孩子指针域，使所有结点同构。

7.7.2 树的存储结构 3）孩子链表表示法 每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。

7.7.2 树的存储结构 4）孩子兄弟表示法 以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。

森林与二叉树的转换 树与二叉树的转换 森林转换成二叉树 二叉树转换成森林

森林转换成二叉树

森林的遍历

树与森林 树与二叉树的转换：给定一棵树，可以有唯一的二叉树与之对应，物理结构上，他们的二叉链表相同。结点的左子树保留，结点的第一个右子树变成该结点左子树的右孩子。 森林与二叉树的转换：是以孩子兄弟存储结构为基础的。 先将森林中的树分别转换为二叉树，再将第二棵二叉树作为第一棵二叉树的右子树，将第三棵二叉树作为第二棵二叉树的右子树…… 树与森林的遍历： 树的先根遍历，相当于对应二叉树的先根遍历 树的后根遍历，相当于对应二叉树的中序遍历 森林的先序遍历，对当二叉树的先序遍历 森林的中序遍历，相当于对应二叉树的中序遍历

考研真题十 森林转为二叉树的三步： （１）连线（将兄弟结点相连，各树的根看作兄弟）； （２）切线（保留最左边子女为独生子女，将其它子女分枝切掉）； （３）旋转（以最左边树的根为轴，顺时针向下旋转45度）。 其实经过（１）和（２），已转为二叉树， 执行（３）只是为了与平时的二叉树的画法一致。

7.8 Huffman树与Huffman编码 问题的提出： 例：编制一个将百分制转换为五级分制的程序。 如： if (a<60) b=”bad”; else if (a<70) b=”pass” else if (a<80) b=”general” else if (a<90) b=”good” else b=”excellent”;

显然，此程序很简单，只要利用条件语句便可完成。如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如下表所示： 分数 0－59 60－69 70－79 80－89 90－100 比例数 0.05 0.15 0.40 0.30 0.10 则80%以上的数据需进行三次或三次以上的比较才能得出结果。

相关概念 å l w 叶子结点的权值：对叶子结点赋予的一个有意义的数值量。 二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。 记为： å = n k l w 1 WPL= 第k个叶子的权值； 从根结点到第k个叶子的路径长度

相关概念 编码：给每一个对象标记一个二进制位串来表示一组对象。例：ASCII，指令系统 等长编码：表示一组对象的二进制位串的长度相等。 不等长编码：表示一组对象的二进制位串的长度不相等。 等长编码什么情况下空间效率高？ 不等长编码什么情况下空间效率高？

相关概念 前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀 。 前缀编码保证了在解码时不会有多种可能。

7.8.1 Huffman树 2 3 4 7 哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。 例：给定4个叶子结点，其权值分别为{2，3，4，7}，可以构造出形状不同的多个二叉树。 2 3 4 7 WPL=32 WPL=41 WPL=30

7.8.1 Huffman树 哈夫曼树的特点： 1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点. 7 2 4 3 2 3 4 7 4 2 3 7

7.8.2 Huffman树的构造 W＝{2，3，4，5} 哈夫曼树的构造过程 3 5 2 4 3 2 5 5 4 3 2 第1步：初始化 第2步：选取与合并 3 2 5 5 4 3 2 第3步：删除与加入

W＝{2，3，4，5} 哈夫曼树的构造过程 4 5 5 重复第2步 2 3 5 4 9 5 4 9 3 2 重复第3步

W＝{2，3，4，5} 哈夫曼树的构造过程 5 4 9 3 2 重复第2步 5 4 9 3 2 14 重复第3步

7.8.3 Huffman树的应用 ——Huffman编码 例：一组字符{A, B, C, D, E, F, G}出现的频率分别是{9, 11, 5, 7, 8, 2, 3}，设计最经济的编码方案。

9 5 2 3 10 19 11 26 8 7 15 45 1 编码方案： A：00 B：10 C：010 D：110 E：111 F：0110 G：0111 A B D C E F G

考研真题： 6．要求二叉树按二叉链表形式存储， （1）写一个建立二叉树的算法。 （2）写一个判别给定的二叉树是否是完全二叉树的算法。 完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。【西北大学 2000 六 (12分)】 类似本题的另外叙述有： （1）试写一算法判断某二叉树是否是完全二叉树。【青岛海洋大学 1999 六(15分)】 （2）编程，判断一棵二叉链表表示的二叉树是否是完全二叉树。【南京航空航天大学2001十(10分)】 （3）编写算法判断一棵二叉树BT是否是完全二叉树。【北方交通大学 1997 八 (20分)】 （4）假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树？ 【哈尔滨工业大学 2000 十一 (14分)】 （5）设二叉树以二叉链表为存储结构，试给出判断一棵二叉树是否为满二叉树的算法，用类pascal语言 写为函数形式。【南开大学 1997 四 (16分)】 （6）试写一算法判别某二叉树是否是完全二叉树。【北京邮电大学 1994 九 (20分)】 [题目分析]二叉树是递归定义的，以递归方式建立最简单。 BiTree Creat() //建立二叉树的二叉链表形式的存储结构 { ElemType x；BiTree bt; scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0) { bt=(BiNode *)malloc(sizeof(BiNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } else error(“输入错误”)； return(bt); }//结束 BiTree

考研真题： [算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。 6．要求二叉树按二叉链表形式存储， （1）写一个建立二叉树的算法。 （2）写一个判别给定的二叉树是否是完全二叉树的算法。 完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。【西北大学 2000 六 (12分)】 类似本题的另外叙述有： （1）试写一算法判断某二叉树是否是完全二叉树。【青岛海洋大学 1999 六(15分)】 （2）编程，判断一棵二叉链表表示的二叉树是否是完全二叉树。【南京航空航天大学2001十(10分)】 （3）编写算法判断一棵二叉树BT是否是完全二叉树。【北方交通大学 1997 八 (20分)】 （4）假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树？ 【哈尔滨工业大学 2000 十一 (14分)】 （5）设二叉树以二叉链表为存储结构，试给出判断一棵二叉树是否为满二叉树的算法，用类pascal语言 写为函数形式。【南开大学 1997 四 (16分)】 （6）试写一算法判别某二叉树是否是完全二叉树。【北京邮电大学 1994 九 (20分)】 思想：判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。 int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 {int tag=0; BiTree p=bt, Q[ ]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1); QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q)) { p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队 else {if (p->lchild) return 0; //前边已有结点为空，本结点不空 else tag=1; //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0; else tag=1; } //while return 1; } //JudgeComplete

考研真题 24．对于二叉树的链接实现,完成非递归的中序遍历过程。 【中山大学 1999 五、 (15分)】 类似本题的另外叙述有： （1）写出中序遍历二叉树的非递归算法及递推算法。【大连海事大学1996 六、2 （10分)】。 （2）设计一个中序遍历算法，应用栈来存储树结点，要求结点仅能进栈和出栈一次。（本题指中序遍历 二叉树）【西安电子科技大学1999计应用 四 (10分)】 （3）用非递归方式写出二叉树中序遍历算法。【山东科技大学 2002 六、2 (9分)】 24. void InOrder(BiTree bt) {BiTree s[ ],p=bt; //s是元素为二叉树结点指针的栈，容量足够大 int top=0; while(p &&top>0) {while(p) {s[++top]=p; bt=p->lchild;} //中序遍历左子树 if(top>0) {p=s[top--]; printf(p->data); p=p->rchild;} //退栈，访问，转右子树 }

考研真题1 3．线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。 树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。 广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。 1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。【西安电子科技大学2001软件 二、1（5分）】 2．树和二叉树之间有什么样的区别与联系？ 【西北工业大学1998一、3(4分)】【厦门大学2000五、2(3分)】【燕山大学2001三、1(5分)】 3．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。 【大连海事大学2001三(10分)】 1．树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。 树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空

第二节小结 遍历二叉树 前序、中序、后序 线索二叉树 树和森林 树的三种存储结构 森林与二叉树的转换 树和森林的遍历 哈夫曼树 有关树的算法

测试题目 79．给定集合{15,3,14,2,6,9,16,17} (1)（3分）用□表示外部结点，用○表示内部结点，构造相应的huffman树： (2) (2分)计算它的带权路径长度： (3)（3分)写出它的huffman编码： (4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。 【山东大学 1998 七、】【山东工业大学 2000 七、 (11分)】 (4) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。

测试题目：算法 假设二叉树采用二叉链存储结构，设计一个算法，计算一棵给定二叉树的所有叶子结点数。

虚拟、复合谓语 Ｐ281，2007阅读1　P1S1 If you were to examine the birth certificates of every soccer player in 2006’s World Cup tournament, you would most likely find a noteworthy quirk: elite soccer players are more likely to have been born in the earlier months of the year than in the later months. 如果你检查参加2006年世界杯足球锦标赛所有参赛运动员的出生证，很可能会发现一个值得注意的怪现象：优秀的足球运动员更可能出生于上半年，而不是下半年。

你的抱怨 一、没良师？ 二、没益友？ 三、没时间？ 四、没环境？

一、没良师？ 你的抱怨 学习自修之道，学习基础知识，培养自学能力。 教育家B. F. Skinner斯金纳说“如果我们将学过的东西忘得一干二净时，最后剩下来的东西就是教育的本质了。” 老师只是引路人 中学与大学的区别 要求高一点：例如，美国麻省理工学院(MIT)的开放式课程 网上资源无限丰富。选好方向学习。讲座？肥皂剧？生活大爆炸？老友记？

你的抱怨 一、没良师？ 二、没益友？ 三、没时间？ 四、没环境？ 你自己是否优秀？ 与外界接触 上课时间太多？ 学英语？学计算机语言？备考？学应用软件？ 四、没环境？ 图书馆满有人占座？ 大家都在玩，自己学不下去？ 找借口？

如何达成目标？ 周密的计划 坚毅的追求： 管理时间： 马上执行：动起来，做下去。 重要的事和紧急的事。 给自己一个合理的最后期限 有远期，中期和近期目标 分解目标 差距分析：有针对性的改善，如英语听力， 坚毅的追求： 管理时间： 重要的事和紧急的事。 给自己一个合理的最后期限 马上执行：动起来，做下去。

考研真题2 6. 一棵有n(n>0)个结点的d度树, 若用多重链表表示, 树中每个结点都有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么? 【长沙铁道学院 1998 四、1 (6分)】 7. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。 【南京理工大学 1998 六、 (3分)】

考研真题 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）【北京工商大学2001一.7(3分)】 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）【北京工商大学2001一.7(3分)】 9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个【哈工大学 2001 二、2 （2分）】 11．具有10个叶结点的二叉树中有（ ）个度为2的结点，【北京航空航天大学2000 一、5（2分)】 A．8 B．9 C．10 D．ll 12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）【西安交通大学 1996 三、2 (3分)】 A． 250 B． 500 C．254 D．505 E．以上答案都不对

考研真题 16. 有关二叉树下列说法正确的是（ ）【南京理工大学 2000 一、11 （1.5分）】 16. 有关二叉树下列说法正确的是（ ）【南京理工大学 2000 一、11 （1.5分）】 A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 17．二叉树的第I层上最多含有结点数为（ ） 【中山大学1998二、7 （2分）】【北京理工大学 2001 六、5（2分）】 A．2I B． 2I-1-1 C． 2I-1 D．2I -1 18. 一个具有1025个结点的二叉树的高h为（ ）【南京理工大学 1999 一、19 （2分）】 A．11 B．10 C．11至1025之间 D．10至1024之间 19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点 A．2h B．2h-1 C．2h+1 D．h+1 【南京理工大学2001一、11(1.5分）】 20．对于有n 个结点的二叉树, 其高度为（ ）【武汉交通科技大学 1996 一、5 (4分)】 A．nlog2n B．log2n C．log2n|+1 D．不确定

考研真题 21. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）【南京理工大学 1996一、8 （2分）】 A．logn+1 B．logn+1 C．logn D．logn-1 22．深度为h的满m叉树的第k层有（ ）个结点。(1=<k=<h)【北京航空航天大学2000一、4（2分）】 A．mk-1 B．mk-1 C．mh-1 D．mh-1 23．在一棵高度为k的满二叉树中，结点总数为（ ）【北京工商大学 2001 一、3 (3分)】 A．2k-1 B．2k C．2k-1 D．log2k+1 24．高度为 K的二叉树最大的结点数为（ ）。【山东大学 2001 二、3 (1分)】 A．2k B．2k-1 C．2k -1 D．2k-1-1 25. 一棵树高为K的完全二叉树至少有（ ）个结点【南京理工大学 1998 一、3 （2分）】 A．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k 26. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（） A．4 B．5 C．6 D．7 【南京理工大学2000一、5 1.5分）】

考研真题： 79．给定集合{15,3,14,2,6,9,16,17} (1)（3分）用□表示外部结点，用○表示内部结点，构造相应的huffman树： (2) (2分)计算它的带权路径长度： (3)（3分)写出它的huffman编码： (4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。 【山东大学 1998 七、】【山东工业大学 2000 七、 (11分)】 类似本题的另外叙述有： （1） 如果通信字符a,b,c,d出现频度分别为：7，5，2，4请画出哈夫曼树并给出相应的哈夫曼编码。【青岛大学 2001 七、1 （5分)】 （2）给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。 【青岛大学 2000 七、 (10分)】 （3）设通信中出现5中字符A、B、C、D、E对应的频率为0.2,0.1,0.5,0.15,0.25构造哈夫曼树，并给出对应字符的编码。【青岛大学 2002 四、2 （10分）】 （4） 设A、B、C、D、E、F六个字母出现的概率分别为7,19,2,6,32,3。试写出为这六个字母设计的HUFFMAN编码, 并画出对应的HUFFMAN树.【山东工业大学 1995 四(10分)】 （5）设用于通信的电文由8个字母组成, 字母在电文中出现的频率分别为:7,19,2,6,32,3,21,10。试为这8个字母设计哈夫曼编码.使用0-7的二进制表示形式是另一种编码方案,试比较这两种方案的优缺点。【南京航空航天大学 1999 四、 (10分)】 (4) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。

考研真题： 类似本题的另外叙述有： （6）假设用于通讯的电文由8个字符组成，其出现的频率为5,29,7,8,14,23,3,11。试为这8个字符设计哈夫曼编码。【燕山大学 1999 五、 (5分)】 （7）假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,,0.20,0.04}, 1) 为这7个字母设计哈夫曼编码； 2）对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？【北京邮电大学 2001 四、2 （5分)】 （8）试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10个终端结点,且具有最小的加权路径长度WPL。【北方交通大学 1993年 五（12分)】 （9）带权结点为{5,6,7,8,9}，构造Huffman树，计算带权路径长度。【西北大学2001年三、3】 （10）以数据集{2,5,7,9,13}为权值构造一棵哈夫曼树，并计算其带权路径长度。 【西安电子科技大学1999计应用 一、4 （5分）】 （11）假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3，21,10。试为这8个字母设计哈夫曼编码。使用0∽7的二进制表示形式是另一 种编码方案。对于上述实例，比较两种方案的优缺点。【大连海事大学 1996 五、2 (8分)】。 （12）设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.06,0.22，0.02，试设计哈夫曼树及其编码。使用0---7的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点。【厦门大学 1999 三、3】 (13) 给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，试画出用Huffman算法建造的Huffman树。【吉林大学 2000 一、2 （4分)】 (14) 以数据集{3,4,5,8,12,18,20,30}为叶结点，构造一棵哈夫曼树，并求其带权路径长度。【山东师范大学 1996 五 5(2分)】

考研真题八 41. 证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。【浙江大学 1996 六、 (8分)】 类似本题的另外叙述有： (1) 证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。 【长沙铁道学院1997五、2(10分)】 （2）证明：由二叉树的中序遍历序列和后序遍历序列可唯一地确定出该二叉树。 【华南理工大学 2001 一、3 （4分)】 （3）二叉树已知其中序扫描序列和后序扫描序列如何确定这一棵二叉树,并举例说明. 【山东大学 2001软件与理论 二 、1 （4分）】