1、 Tree&Binary Tree 树的类型定义树的类型定义 n(n0)个元素的有个元素的有限集合限集合基基 本本 术术 语语结点结点结点的度结点的度树的度树的度叶子结点叶子结点分支结点分支结点数据元素数据元素+若干指向子树的分支若干指向子树的分支分支的个数分支的个数树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点度大于零的结点度大于零的结点(从根到结点的从根到结点的)路径路径孩子孩子结点、结点、双亲双亲结点结点兄弟兄弟结点、结点、堂兄弟堂兄弟结点结点祖先祖先结点、结点、子孙子孙结点结点 由从根到该结由从根到该结点所经分支和结点点所经分支和结点构成构成结点的层次结点的层
2、次树的深度树的深度假设根结点的层次为假设根结点的层次为1 1，第第l 层的结点的子树根结层的结点的子树根结点的层次为点的层次为l+1 树中叶子结点所在的最大树中叶子结点所在的最大 层次层次任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=（root，F）其中其中root 被称为根结点被称为根结点 F 被称为子树森林被称为子树森林是是m（m0）棵互）棵互不相交的树的集合不相交的树的集合()有确定的根有确定的根()树根和子树根之间为有向关系树根和子树根之间为有向关系有向树有向树有序有序树树子树之间存在确定的次序关系子树之间存在确定的次序关系无序无序树树子树之间不存在确定的次序关系子树
3、之间不存在确定的次序关系对比树型结构和线性结构对比树型结构和线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)树的抽象数树的抽象数据类型定义据类型定义数据对象数据对象 D D是具有相同特性的数据是具有相同特性的数据元素的集合元素的集合1.若若D为空集，则称为空树为空集，则称为空树2.在在D中存
4、在唯一的称为根的数据元素中存在唯一的称为根的数据元素 root3.当当n1时，其余结点可分为时，其余结点可分为m(m0)个个 互不相交的有限集互不相交的有限集T1,T2,Tm，其中，其中 每一棵子集本身又是一棵符合本定义每一棵子集本身又是一棵符合本定义 的树，称为根的树，称为根root的子树的子树 数据关系数据关系 R 基本操作基本操作查查 找找 类类 插插 入入 类类删删 除除 类类 Root(T)/求树的根结点求树的根结点 查找类查找类Value(T,cur_e)/求当前结点的元素值求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结求当前结点的双亲结点点LeftChil
5、d(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历InitTree(&T)/初始化置空树初始化置空树 插入类插入类CreateTree(&T,definition)/按定义构造按定义构造树树Assign(T,cur_e,value)/给当前结点赋给当前结点赋值值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插
6、入为结点p的第的第i棵棵子树子树 ClearTree(&T)/将树清空将树清空 删除类删除类DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子棵子树树A(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根二叉树的类型定义二叉树的类型定义 二叉树或为空树，或是由一个根结二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成的、互不交叉的二叉树组成ABCDEFGHK根结点根结点左子树左子树右子树右子树二叉树的五种基本形态二叉树的五种基本形
7、态N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树 二叉树的主要基本操作二叉树的主要基本操作查查 找找 类类插插 入入 类类删删 除除 类类 Root(T)Value(T,e)Parent(T,e)LeftChild(T,e)RightChild(T,e)LeftSibling(T,e)RightSibling(T,e)BiTreeEmpty(T)BiTreeDepth(T)PreOrderTraverse(T,Visit()InOrderTraverse(T,Visit()PostOrderTraverse(T,
8、Visit()LevelOrderTraverse(T,Visit()InitBiTree(&T)Assign(T,&e,value)CreateBiTree(&T,definition)InsertChild(T,p,LR,c)ClearBiTree(&T)DestroyBiTree(&T)DeleteChild(T,p,LR)完全二叉树完全二叉树丰满二叉树丰满二叉树排序二叉树排序二叉树平衡二叉树平衡二叉树二叉树的分类二叉树的分类满二叉树：满二叉树：指的是指的是深度为深度为k且含有且含有2k-1个个结点的二叉树结点的二叉树完全二叉树：完全二叉树：树树中所含的中所含的 n 个结点个结点和满二叉
9、树中编号和满二叉树中编号为为 1 至至 n 的结点一的结点一一对应一对应12345678910 11 12 13 14 15abcdefghij二叉树二叉树的重要特性的重要特性性性 质质 1 1 在二叉树的第在二叉树的第i(i1)i(i1)层上至多有层上至多有2 2i-1 i-1 个结点个结点用归纳法证用归纳法证明明归纳基础归纳基础归纳假设归纳假设归纳证明归纳证明i=1 层时，只有一个根结点：层时，只有一个根结点：2i-1=20=1假设对所有的假设对所有的 j，1 j i，命题成立命题成立二叉树上每个结点至多有二叉树上每个结点至多有两两棵子树，则第棵子树，则第 i 层的结点数层的结点数 2i-
10、2 2=2i-1性性 质质 2 2 深深度为度为k k（k1k1）的二叉树上至多）的二叉树上至多含含2 2k k-1-1 个结点个结点证明证明 基于上一条性质，深度为基于上一条性质，深度为 k k 的二的二叉树上的结点数至多为叉树上的结点数至多为 2 20 0+2+21 1+2+2k-1k-1=2=2k k-1-1性性 质质 3 3 对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n n0 0 个个叶子结点、叶子结点、n n2 2 个度为个度为2 2的结点，则必存的结点，则必存在关系式：在关系式：n n0 0=n=n2 2+1+1证明证明设二叉树上结点总数设二叉树上结点总数 n=nn=n0
11、 0+n+n1 1+n+n2 2又二叉树上分支总数又二叉树上分支总数 b=nb=n1 1+2n+2n2 2 而而 b=n-1=nb=n-1=n0 0+n+n1 1+n+n2 2-1-1由此，由此，n n0 0=n=n2 2+1+1性性 质质 4 4 具有具有n n个结点的完全二叉树的深度个结点的完全二叉树的深度为为 loglog2 2n n +1+1证明证明设完全二叉树的深度为设完全二叉树的深度为 k k 则根据第二条性质得则根据第二条性质得 2 2k-1k-1 n 2 n 2k k 即即 k-1 logk-1 log2 2 n k n n2in，则该结点无左孩子，否，则该结点无左孩子，否 则
12、，编号为则，编号为2i2i的结点为其左孩子的结点为其左孩子 结点结点 (3)(3)若若2i+1n2i+1n，则该结点无右孩子结，则该结点无右孩子结 点，否则，编号为点，否则，编号为2i+12i+1的结点为的结点为 其右孩子结点其右孩子结点树的存储结构树的存储结构一、广义表表示法一、广义表表示法二、双亲表示法二、双亲表示法三、孩子表示法三、孩子表示法四、孩子兄弟表示法四、孩子兄弟表示法 树的广义表表示树的广义表表示 (结点的结点的utypeutype域没有画出域没有画出)ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent双亲表示法双亲表
13、示法ABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 4 data firstchild 1 2 34 56孩子链表表示法孩子链表表示法ABCDEFG AB C E D F Groot AB C E D F G 孩子兄弟表示法孩子兄弟表示法 data firstChildnextSibling二叉树的存储结构二叉树的存储结构二、二叉树的链二、二叉树的链 式存储表示式存储表示一、二叉树的顺一、二叉树的顺 序存储表示序存储表示 完全二叉树的完全二叉树的 一般二叉树的一般二叉树的 数组表示数组表示 数组表示数组表示ABCDEF A B D C E F 0 1 2 3
14、 4 5 6 7 8 9 10 11 12 131401326 单支树单支树ADEBCF rootlchild data rchild结点结构结点结构二叉链表二叉链表ADEBCF root 三叉链表三叉链表parent lchild data rchild结点结构结点结构二叉链表的静态结构二叉链表的静态结构 顺着某一条搜索路径巡访二叉树顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一中的结点，使得每个结点均被访问一次，而且仅被访问一次次，而且仅被访问一次问题的提出问题的提出“访问访问”的含义可以很广，如：输出结的含义可以很广，如：输出结点的信息等点的信息等 “遍历遍历”是任何类型均
15、有的操作，是任何类型均有的操作，对线性结构而言，只有一条搜索路对线性结构而言，只有一条搜索路径径(因为每个结点均只有一个后继因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，线性结构，每个结点有两个后继，则存在如何遍历即按什么样的则存在如何遍历即按什么样的搜索搜索路径路径遍历的问题遍历的问题 对对“二叉树二叉树”而言，可以有三而言，可以有三条搜索路径条搜索路径1先上后下先上后下的按层次遍历的按层次遍历2先左先左（子树）（子树）后右后右（子树）的（子树）的遍历遍历3先右先右（子树）（子树）后左后左（子树）的（子树）的遍历遍历
16、设设 访问根结点访问根结点 记作记作 V 遍历根的左子树遍历根的左子树 记作记作 L 遍历根的右子树遍历根的右子树 记作记作 R 则可能的遍历次序有则可能的遍历次序有 按给定的表达式建相应二叉树按给定的表达式建相应二叉树由前缀表达式建树由前缀表达式建树例如例如:-+abc/de由中缀表达式建树由中缀表达式建树 例如：例如：(a+b)cd/e由后缀表达式建树由后缀表达式建树例如：例如：ab+cde/-/-对应前缀表达式对应前缀表达式 -+abc/de 的二叉树的二叉树abcde-+/特点特点：操作数为叶子结点操作数为叶子结点 运算符为分支结点运算符为分支结点对应中缀表达式对应中缀表达式 (a+b
17、)c-d/e 的二叉树的二叉树abcde-+/特点特点：操作数为叶子结点操作数为叶子结点 运算符为分支结点运算符为分支结点对应后缀表达式对应后缀表达式 ab+cde/-/-的二叉树的二叉树abcde-+/特点特点：操作数为叶子结点操作数为叶子结点 运算符为分支结点运算符为分支结点a+b(a+b)c d/e d/ea+bc 分析表达式和二叉树的关系分析表达式和二叉树的关系ab+abc+abc+(a+b)cabcde-+/仅知二叉树的先序序列仅知二叉树的先序序列“abcdefg”不不能唯一确定一棵二叉树，能唯一确定一棵二叉树，由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时已知二
18、叉树的中序序列如果同时已知二叉树的中序序列“cbdaegf”，则会如何？，则会如何？二叉树的先序序列二叉树的先序序列二叉树的中序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根a b c d e f gc b d a e g faab bccddeeffggabcdefg先序序列先序序列中序序列中序序列 123，!)!2(11112nnnnnbCnnn A B C DE F G H I J K 先根遍历先根遍历A B E F C D G H I J K 后根遍历后根遍历E F B C I J K H G D A 层次遍历：层次遍历：A B C D E F G H
19、I J K B C DE F G H I J K1森林中第一棵森林中第一棵树的根结点树的根结点2森林中第一棵森林中第一棵树的子树森林树的子树森林3森林中其它树森林中其它树构成的森林构成的森林森林由三部分构成森林由三部分构成template class BinTreeNode private:BinTreeNode*LChild,*RChild;Type data;template class BinaryTree private:BinTreeNode*root;template void BinaryTree:PreOrder(BinTreeNode*current)if(current!=
20、NULL)cout currentdata;PreOrder(currentLChild);PreOrder(currentRChild);template void BinaryTree:InOrder(BinTreeNode*current)if(current!=NULL)InOrder(currentLChild);cout currentdata;InOrder(currentRChild);二叉树后序遍历递归算法二叉树后序遍历递归算法template void BinaryTree:PostOrder(BinTreeNode*current)if(current!=NULL)Pos
21、tOrder(currentLChild);PostOrder(currentRChild);cout currentdata;template void BinaryTree:PreOrder(BinTreeNode*p)do while(p!=NULL)cout pdata;Push(s,p);p=pLChild;if(!Empty(s)p=pop(s);p=pRChild;while(!Empty(s)|(p!=NULL)template void BinaryTree:PreOrder(BinTreeNode*p)do while(p!=NULL)Push(s,p);p=pLChild
22、;if(!Empty(s)p=pop(s);cout pdata;p=pRChild;while(!Empty(s)|(p!=NULL)计算二叉树结点个数的一种方法计算二叉树结点个数的一种方法template int BinaryTree:Size(BinTreeNode *t)if(t=NULL)return 0;else return 1+Size(tLChild)+Size(tRChild);计算二叉树的高度计算二叉树的高度template int BinaryTree:Depth(BinTreeNode *t)if(t=NULL)return 0;else return 1+Max(D
23、epth(tLChild),Depth(tRChild);线索二叉树线索二叉树遍历二叉树的结果是，遍历二叉树的结果是，求得结点的一个线性序列求得结点的一个线性序列ABCDEFGHK先序序列先序序列 A B C D E F G H K中序序列中序序列 B D C A H G K F E后序序列后序序列 D C B H K G F E A指向该线性序列中的指向该线性序列中的“前驱前驱”和和 “后继后继”的指针，称作的指针，称作“线线索索”与其相应的二叉树，与其相应的二叉树，称作称作“线索二叉树线索二叉树”包含包含“线索线索”的存储的存储结构，称作结构，称作“线索链线索链表表”A B C D E F
24、 G H K D C B E 对线索链表中结点的约定对线索链表中结点的约定在二叉链表的结点中增加两个标志域在二叉链表的结点中增加两个标志域LTag和和RTag,并作如下规定并作如下规定:若该结点的左子树不空，若该结点的左子树不空，则则LChild域的指针指向其左孩子，域的指针指向其左孩子，且左标志且左标志LTag的值为的值为0 否则，否则，LChild域的指针指向其域的指针指向其“前前驱驱”，且左标志且左标志LTag的值为的值为1若该结点的右子树不空，若该结点的右子树不空，则则RChild域的指针指向其右孩子，域的指针指向其右孩子，且右标志且右标志RTag的值为的值为0否则，否则，RChild
25、域的指针指向其域的指针指向其“后继后继”，且右标志且右标志RTag的值为的值为1 如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”猜一猜猜一猜,是哪一种线索二叉树是哪一种线索二叉树 带表头结点的中序线索二叉树带表头结点的中序线索二叉树 if(pRTag=1)if(pRChild!=T.root)后继为后继为 pRChild else 无后继无后继else /pRTag=0 if(pRChild!=T.root)后继为当前结点右后继为当前结点右 子树的中序下的第子树的中序下的第 一个结点一个结点 else 出错情况出错情况ABDECFHIKGJL if(pLTag
26、=1)if(pLChild!=T.root)前驱为前驱为pLChild else 无前驱无前驱else/pLTag=0 if(pLChild!=T.root)前驱为当前结点左前驱为当前结点左 子树的中序下的最子树的中序下的最 后一个结点后一个结点 else 出错情况出错情况ABDECFHIKGJLtemplate class MinPQ public:Virtual void Insert(const Type&)=0;Virtual Type*RemoveMin(Type&)=0;最小优先级队列类的定义最小优先级队列类的定义&template class MinHeap:public Min
27、PQ public:MinHeap(int maxSize)const;MinHeap(Type arr,int n);MinHeap()delete heap;const MinHeap&operator=(const MinHeap&R);int Insert(const Type&x);int RemoveMin(Type&x);int IsEmpty()const return CurrentSize=0;int IsFull()const return CurrentSize=MaxHeapSize;void MakeEmpty()CurrentSize=0;private:enum
28、 DefaultSize=10;Type*heap;int CurrentSize;int MaxHeapSize;void FilterDown(int i,int m);void FilterUp(int i);template MinHeap:MinHeap(int maxSize)/根据给定大小根据给定大小maxSize,建立堆对象建立堆对象 MaxHeapSize=DefaultSize maxSize?maxSize:DefaultSize;/确定堆大小确定堆大小 heap=new Type MaxHeapSize;/创建堆空间创建堆空间 CurrentSize=0;/初始化初始化
29、template MinHeap:MinHeap(Type arr,int n)/根据给定数组中的数据和大小根据给定数组中的数据和大小,建立堆对象建立堆对象 MaxHeapSize=DefaultSize=0)/从下到上逐步扩大从下到上逐步扩大,形成堆形成堆 FilterDown(currentPos,CurrentSize);/从从currentPos开始开始,到到CurrentSize为止为止,调整调整 currentPos-;自下向上逐步调整为最小堆自下向上逐步调整为最小堆template void MinHeap:FilterDown(const int start,const int
30、 EndOfHeap)int i=start,j=2*i+1;/j 是是 i 的左子女的左子女 Type temp=heapi;while(j=EndOfHeap)if(j heapj+1.key)j+;/两子女中选小者两子女中选小者 if(temp.key=heapj.key)break;else heapi=heapj;i=j;j=2*j+1;heapi=temp;template int MinHeap:Insert(const Type&x)/在堆中插入新元素在堆中插入新元素 x if(CurrentSize=MaxHeapSize)/堆满堆满 cout 堆已满堆已满 endl;ret
31、urn 0;heapCurrentSize=x;/插在表尾插在表尾 FilterUp(CurrentSize);/向上调整为堆向上调整为堆 CurrentSize+;/堆元素增一堆元素增一 return 1;template void MinHeap:FilterUp(int start)/从从 start 开始开始,向上直到向上直到0,调整堆调整堆 int j=start,i=(j-1)/2;/i 是是 j 的双亲的双亲 Type temp=heapj;while(j 0)if(heapi.key=temp.key)break;else heapj=heapi;j=i;i=(i-1)/2;h
32、eapj=temp;template int MinHeap:RemoveMin(Type&x)if(!CurrentSize)cout “堆已空堆已空 endl;return 0;x=heap0;/最小元素出队列最小元素出队列 heap0=heapCurrentSize-1;CurrentSize-;/用最小元素填补用最小元素填补 FilterDown(0,CurrentSize-1);/从从0 0号位置开始自顶向下调整为堆号位置开始自顶向下调整为堆 return 1;哈哈 夫夫 曼曼 树树 与与哈哈 夫夫 曼曼 编编 码码 结点的路径长度结点的路径长度 从根结点到该结点的路径上分从根结点到
33、该结点的路径上分 支的数目支的数目树的路径长度树的路径长度 树中每个结点的路径长度之和树中每个结点的路径长度之和10niiilwWPL 在所有含在所有含n n个叶子结点、并带相同个叶子结点、并带相同权值的权值的m m叉树中，必存在一棵其带权路叉树中，必存在一棵其带权路径长度取最小值的树，称为径长度取最小值的树，称为“最优树最优树”,或或“哈夫曼树哈夫曼树”具有不同带权路径长度的二叉树具有不同带权路径长度的二叉树WPL(T)=7 2+5 2+2 3+4 3+9 2 =60WPL(T)=7 4+9 4+5 3+4 2+2 1 =89 根据给定的根据给定的 n 个权值个权值 w1,w2,wn，造，造
34、 n 棵二叉树的集合棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权其中每棵二叉树中均只含一个带权 值为值为 wi 的根结点，其左、右子树为的根结点，其左、右子树为 空树；空树；在在 F 中选取其根结点的权值为最中选取其根结点的权值为最 小的两棵二叉树，分别作为左、小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之为其左、右子树根结点的权值之 和；和；从从F中删去这两棵树，同时加入中删去这两棵树，同时加入 刚生成的新树刚生成的新树 重复重复 和和 两步，
35、直至两步，直至 F 中只中只 含一棵树为止含一棵树为止00001111 哈夫曼树的应用哈夫曼树的应用（1）判定树）判定树在解决某些判定问题时，利用哈夫曼树可以得到最在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。佳判定算法。例例1 将学生百分成绩按分数段分级的程序。将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图（若学生成绩分布是均匀的，可用图（a)二叉树结构二叉树结构来实现。来实现。a60 a70 a80 a90 不及格不及格中等中等良好良好优秀优秀及格及格YNYNYNYN(a)输入输入10000个个数据，则需进数据，则需进行行31500次比次比较。较。分数分数0-5
36、960-6970-7980-8990-100比例数比例数0.050.150.400.300.1010000个学生成绩转换成五分制的判定个学生成绩转换成五分制的判定A60A70A80A90不及格优秀及格中等良好YNYYYNNN500*1+1500*2+4000*3+3000*4+1000*4=31500分数分数0596069707980899099比例比例0.050.150.40.30.10 70a 80 a60 及格及格中等中等良好良好 80a90 60a70 不及格不及格优秀优秀YNYYYNNN(b)不及格不及格Y a90 a80 a70 a60 优秀优秀中等中等及格及格良好良好YNNN(c
37、)YYY 学生成绩分布不是均匀的情况：学生成绩分布不是均匀的情况：以比例数为权构造一棵哈夫曼树，以比例数为权构造一棵哈夫曼树，如（如（b)判断树所示。判断树所示。再将每一比较框的两次比较改为一再将每一比较框的两次比较改为一次，可得到（次，可得到（c)判定树。判定树。输入输入10000个个数据，仅需进数据，仅需进行行22000次比次比较。较。A60A70A80A90不及格优秀及格中等良好YNYYYNNN用此形式比较次数为：用此形式比较次数为：500*3+1500*3+4000*2+3000*2+1000*2=22000146833442200001111T;ACS各字符编码是各字符编码是 T ；
38、A C S 00 01 10 110 111上述电文编码：上述电文编码：11010111011101000011111000011000方法：方法：（1）用）用 2，4，2，3，3 作为叶子结点的权值生成一棵哈作为叶子结点的权值生成一棵哈夫曼树，并将对应权值夫曼树，并将对应权值wi的叶子结点注明对应的字符；的叶子结点注明对应的字符；（2）约定左分支表示字符）约定左分支表示字符“0”，右分支表示字符，右分支表示字符1（3）从叶子结点开始，顺着双亲反推上去，直到根结点，路）从叶子结点开始，顺着双亲反推上去，直到根结点，路径上的径上的0或或1连接的序列就是结点对应的字符的二进制连接的序列就是结点对应
39、的字符的二进制编码的逆序。编码的逆序。（2）哈夫曼编码）哈夫曼编码-利用哈夫曼树构造通讯中电文编码（前缀码）利用哈夫曼树构造通讯中电文编码（前缀码）例例2：要传输的电文是：要传输的电文是CAS；CAT；SAT；AT要传输的字符集是要传输的字符集是 D=C，A，S，T，；每个字符出现的频率是每个字符出现的频率是W=2，4，2，3，3 注意：编码的总长度恰好为哈夫曼树的带权路径长。注意：编码的总长度恰好为哈夫曼树的带权路径长。1.熟练掌握二叉树的结构特性二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构存储结构的特点及适用范围。3.遍历二叉树遍历二叉树是二叉树各种操作的基础。实现二
40、叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算递归算法法，灵活运用遍历算法灵活运用遍历算法实现二叉树的其它操作。层次遍历层次遍历是按另一种搜索策略进行的遍历。4.理解二叉树线索化的实质线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索线索化过程化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索线索化过程化过程是基于基于对二叉树进行遍历遍历，而线索二叉树上的线索又为相应的遍历提供线索又为相应的遍历提供了方便方便。5.熟悉树的树的各种存储结构存储结构及其特点，掌握树和森林与二叉树的转换树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握掌握 1 至 2 种建立建立二叉树和树的存储结存储结构的方法构的方法。6.学会编写实现树的各种操作实现树的各种操作的算法。7.了解最优树的特性最优树的特性，掌握建立最优树建立最优树和哈夫曼编码和哈夫曼编码的方法。
