二叉树和其他树

1、第8章 二叉树和其他树学习内容m简单树和二叉树q术语q公式化描述和链表描述q遍历m应用q表达式后缀表示表达式树8.1 树m线性表、表：不适合描述层次结构数据m祖先后代、上级下属、整体部分m树结构：模仿自然界中的植物树例8-1：家庭关系例8-2m公司结构例8-3m政府机构例8-4m软件工程数据结构“树”m定义：树（tree）t是一个非空的有限元素的集合，一个特殊的元素称为根（root），余下的元素（如果有的话）组成t的若干子树（subtree）m递归！例8-6 家庭关系例树的描述m数据集合Joe，Ann，Mary，Mark，Sue，John，Chrismn=7，根为Joe家庭关系例树的描述（续）

2、m余下的元素qAnn单一元素子树qMary，Mark，Sue，根为Mary的子树Mark和Sue，均为单元素的子树qJohn，Chris，根为John的子树Chris 也为单元素子树相关术语m元素节点m根节点与子树的根节点的关系边m边的两端父母（parent）和孩子（children）相关术语（续）m相同父母的节点兄弟（sibling）m祖父孙子，祖先后代m叶节点没有孩子的节点，非叶节点非终端节点相关术语（续）m根没有父节点的节点m层（level）：根1，根的孩子2，.m节点的度（degree）：孩子数目，叶0例8-6m公司机构例q公司雇员节点，总裁根q副总裁总裁的子节点，总裁副总裁的父节点q

3、不同副总裁兄弟节点例8-6 （续）m政府机构例q联邦政府国防部，教育部，.，税务部的父节点q国防部的子节点陆军、海军、空军、海军陆战队兄弟节点，叶节点自由树有根树有序树森林和有序森林m森林（forest）：）：树的集合，通常认为是有根树的集合m有序森林（orchard，ordered forest）：）：有序树的有序集合m有根树去掉根节点（有序）森林m（有序）森林添加父节点有根树 森林和有序森林（续）有根树的递归定义m有根树：包含单一顶点v，称为树的根，和一个森林F，F的树称为根的子树而森林F（可为空）是一个有根树的集合有序树的定义m一个有序树T：包含一个单一节点v，称为树的根，和一个有序森林

4、O，O的树称为v的子树，表示为T=v, O有序森林的定义m一个有序森林O：或者为空集，或包含一个有序树T，称为有序森林的第一树，和另一个有序森林O（包含有序森林的其它树），可表示为O=T, Om有序树有序森林：间接递归定义有序森林8.2 二叉树m定义： 二叉树（binary tree）t是有限元素集合：或者为空；或者，有一个特殊元素根，余下的元素构成2个二叉树（可以为空）t的左子树和右子树二叉树和树的根本区别m二叉树可以为空树不行m二叉树每个节点都恰好有两棵子树（可以为空）树中每个节点可有若干子树m二叉树每个节点的子树是有序的“左”、“右”树的子树间是无序的二叉树例递归构造m空二叉树递归的停止

5、m单一节点二叉树m两个节点：不同！不能表示为二叉树例递归构造（续）m三个节点q根左子树(2)右子树(0)、11、02m类似方式，可构造更大的二叉树二叉树例：表达式树ma*b + c/dma+b+c+dm(-a+(x+y)/(+b*(c*a)8.3 二叉树的特性m特性1 包含n (n0)个节点的二叉树边数为n-1证明二叉树中每个节点（除根节点，共n-1个节点） 有且只有一个父节点每个子节点与父节点间有且只有一条边边数为n-1特性2m二叉树的高度（height）（深度，depth）：二叉树的层数m特性2 若二叉树的高度为h，h0，则它最少有h个节点，最多有2h-1个节点特性2的证明证明每层最少要有

6、1个节点节点数最少为h每个节点最多有2个子节点则第i层节点最多为2i-1个，i0节点的总数不会超过12211hhii特性3m特性3 包含n个节点的二叉树的高度最大为n，最小为证明每层至少一个元素高度不会超过n由特性2，可知高度为h，节点最多2h-1即n2h-1hlog2(n+1)且h是整数) 1(log2n) 1(log2nh满二叉树（full binary tree ）m高度为h，节点数2h-1完全二叉树(complete binary tree)m高度为h 的满二叉树中节点按从上到下，从左到右的顺序从1到2h-1进行编号m从中删除k个节点，编号为2h-i, 1ikm即为完全二叉树，深度为)

7、 1(log2n特性4m特性4 设完全二叉树中一节点的序号为i, 1in。则有以下关系成立：m当i = 1时，该元素为二叉树的根。若i 1，则该元素父节点的编号为1)当2in时，该元素无左孩子。否则，其左孩子的编号为2i2/ i特性4（续）m若2i + 1n，该元素无右孩子。否则，其右孩子编号为2i + 1证明通过对i 进行归纳即可得证8.4 二叉树描述m8.4.1 公式化描述利用特性4q普通二叉树缺少部分节点的完全二叉树公式化描述m数组位置节点编号m父子节点关系特性4公式化描述mn层二叉树2n-1数组保存，可能空间浪费！8.4.2 链表描述m树节点节点类对象q数据域、LeftChild、Ri

8、ghtChildqn-1条边2n-(n-1)=n+1个空指针BinaryTreeNode类template class BinaryTreeNode friend void Visit(BinaryTreeNode *); friend void InOrder(BinaryTreeNode *); friend void PreOrder(BinaryTreeNode *); friend void PostOrder(BinaryTreeNode *); friend void LevelOrder(BinaryTreeNode *); friend void main(void); Bi

9、naryTreeNode类public: BinaryTreeNode() LeftChild = RightChild = 0; BinaryTreeNode(const T& e) data = e; LeftChild = RightChild = 0; BinaryTreeNode(const T& e, BinaryTreeNode *l, BinaryTreeNode *r) data = e; LeftChild = l; RightChild = r; private: T data; BinaryTreeNode *LeftChild, / left subt

10、ree *RightChild; / right subtree;二叉树与有序森林的对应关系m二叉树的另一种定义：一个二叉树B或者是空集，或者包含一个根v和两个二叉树B1和B2，可表示为B=v, B1, B2m定理11.1：令S为任意顶点集合，则以S为顶点集合的有序森林集合和以S为顶点集合的二叉树集合之间存在一一映射f任一有序森林均有任一二叉树与之对应证明（数学归纳法）对空集S，有序森林和二叉树均为空，映射关系f()=，命题成立假定对所有|S|n，命题成立，考虑|S|=n若森林O不为空O=T, O2 ，T第一树为有序树，O2为另一森林（森林定义）1对应关系的证明（续）另有T=v, O1 ，v为

11、顶点，O1为另一森林（有序树定义）2由1、2O=v, O1, O2O1和O2节点数必然 n存在一一对应的二叉树f(O1)和f(O2)定义：f(O)=f(v, O1, O2)=v, f(O1), f(O2)因此，f(O)表示一棵二叉树，对|S|=n命题成立命题得证用二叉树类型描述树（森林）mLeftChild指向第一个孩子节点mRightChild指向下一个兄弟节点m显然，遍历函数应修改用二叉树类型描述树（森林）用二叉树类型描述树（森林）8.5 二叉树常用操作m确定高度m确定节点数目m复制m显示或打印二叉树m确定两棵二叉树是否一样二叉树常用操作（续）m删除整棵树m若为数学表达式树，计算该数学表达

12、式m若为数学表达式树，给出对应的带括号的表达式m都可通过二叉树遍历（按某种顺序访问所有节点，且只访问一次）来完成8.6 二叉树遍历m遍历顺序q访问根节点、左子树、右子树的顺序q左右子树的访问（遍历）？递归！m可能的遍历顺序qV根，L左子树，R右子树qVLR LVR LRV VRL RVL RLV标准遍历顺序m都是左子树先于右子树，关键根的访问次序m先序遍历（preorder）VLRm中序遍历（inorder）LVRm后序遍历（postorder）LRV先序遍历template void PreOrder(BinaryTreeNode *t)/ Preorder traversal of *t.

13、 if (t) Visit(t); / visit tree root PreOrder(t-LeftChild); / do left subtree PreOrder(t-RightChild); / do right subtree 中序遍历template void InOrder(BinaryTreeNode *t)/ Inorder traversal of *t. if (t) InOrder(t-LeftChild); / do left subtree Visit(t); / visit tree root InOrder(t-RightChild); / do right

14、subtree 后序遍历template void PostOrder(BinaryTreeNode *t)/ Postorder traversal of *t. if (t) PostOrder(t-LeftChild); / do left subtree PostOrder(t-RightChild); / do right subtree Visit(t); / visit tree root 先序遍历表达式树+*ab/cd+abcd/+-a+xy*+b*cam前缀表达式中序遍历表达式树a*b + c/da+b+c+d-a+x+y/+b*c*am中缀表达式人类习惯m需加括号后序遍历表

15、达式树ab*cd/+ab+c+d+a-xy+b+ca*/m后缀表达式计算机计算非常方便输出完全括号化的中缀表达式template void Infix(BinaryTreeNode *t)/ Output infix form of expression. if (t) cout LeftChild); / left operand cout data; / operator Infix(t-RightChild); / right operand cout );逐层遍历（宽度优先）m根叶逐层，同层由左至右template void LevelOrder(BinaryTreeNode *t)/

16、 Level-order traversal of *t. LinkedQueueBinaryTreeNode* Q; while (t) Visit(t); / visit t 逐层遍历（宽度优先） / put ts children on queue if (t-LeftChild) Q.Add(t-LeftChild); if (t-RightChild) Q.Add(t-RightChild); / get next node to visit try Q.Delete(t); catch (OutOfBounds) return; 最坏情况空间复杂性O(n)时间复杂性(n)8.7 抽

17、象数据类型BinaryTree抽象数据类型BinaryTree实例元素集合；如果不空，则被划分为根节点、左子树和右子树；每个子树仍是一个二叉树操作Create()：创建一个空的二叉树；IsEmpty：如果二叉树为空，则返回true，否则返回falseRoot(x)：取x为根节点；如果操作失败，则返回false，否则返回true抽象数据类型（续） MakeTree(root，left，right)：创建一个二叉树，root作为根节点，left作为左子树，right作为右子树BreakTree(root，left，right)：拆分二叉树PreOrder：先序遍历InOrder：中序遍历PostO

18、rder：后序遍历LevelOrder：逐层遍历8.8 类BinaryTreetemplateclass BinaryTree public: BinaryTree() root = 0; BinaryTree(); bool IsEmpty() const return (root) ? false : true); bool Root(T& x) const; void MakeTree(const T& element, BinaryTree& left, BinaryTree& right); void BreakTree(T& element,

19、 BinaryTree& left, BinaryTree& right); void PreOrder(void(*Visit)(BinaryTreeNode *u) PreOrder(Visit, root);类BinaryTree（续） void InOrder(void(*Visit)(BinaryTreeNode *u) InOrder(Visit, root); void PostOrder(void(*Visit)(BinaryTreeNode *u) PostOrder(Visit, root); void LevelOrder(void(*Visit)(Bin

20、aryTreeNode *u);private: BinaryTreeNode *root; / pointer to root void PreOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void InOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void PostOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t);获取根节点数据templatebool BinaryTree:R

21、oot(T& x) const/ Return root data in x. / Return false if no root. if (root) x = root-data; return true; else return false; / no root创建树templatevoid BinaryTree:MakeTree(const T& element, BinaryTree& left, BinaryTree& right)/ Combine left, right, and element to make new tree. / left,

22、right, and this must be different trees. / create combined tree root = new BinaryTreeNode (element, left.root, right.root); / deny access from trees left and right left.root = right.root = 0;缺陷：允许MakeTree(e, X, X)且X不为空为什么置为空？不会造成空悬指针吗？分裂树templatevoid BinaryTree:BreakTree(T& element, BinaryTree&a

23、mp; left, BinaryTree& right)/ left, right, and this must be different trees. / check if empty if (!root) throw BadInput(); / tree empty / break the tree element = root-data; left.root = root-LeftChild; right.root = root-RightChild; delete root; root = 0;与上例相同的道理先序遍历templatevoid BinaryTree:PreOrd

24、er(void(*Visit)(BinaryTreeNode *u),BinaryTreeNode *t)/ Preorder traversal. if (t) Visit(t); PreOrder(Visit, t-LeftChild); PreOrder(Visit, t-RightChild); 中序遍历template void BinaryTree:InOrder(void(*Visit)(BinaryTreeNode *u),BinaryTreeNode *t)/ Inorder traversal. if (t) InOrder(Visit, t-LeftChild); Vis

25、it(t); InOrder(Visit, t-RightChild); 后序遍历template void BinaryTree:PostOrder(void(*Visit)(BinaryTreeNode *u),BinaryTreeNode *t)/ Postorder traversal. if (t) PostOrder(Visit, t-LeftChild); PostOrder(Visit, t-RightChild); Visit(t); 逐层遍历template void BinaryTree:LevelOrder(void(*Visit)(BinaryTreeNode *u)

26、/ Level-order traversal. LinkedQueueBinaryTreeNode* Q; BinaryTreeNode *t; t = root; while (t) Visit(t); if (t-LeftChild) Q.Add(t-LeftChild); if (t-RightChild) Q.Add(t-RightChild); try Q.Delete(t); catch (OutOfBounds) return; 由遍历顺序推导二叉树结构m一棵二叉树先序遍历结果1, 2, 4, 7, 3, 5, 6, 8, 9中序遍历结果4, 7, 2, 1, 5, 3, 8,

27、 6, 9能推导出其结构吗？m可以！第一步1, 2, 4, 7, 3, 5, 6, 8, 94, 7, 2, 1, 5, 3, 8, 6, 9m先序遍历根左子树右子树“1”必为根节点m中序遍历左子树根右子树，且1为根节点4, 7, 2为左子树，5, 3, 8, 6, 9为右子树下面怎么办？递归！m左子树先序遍历2, 4, 7中序遍历4, 7, 2m右子树先序遍历3, 5, 6, 8, 9中序为5, 3, 8, 6, 9m利用相同方法构造左、右子树，直至列表长度为0空子树，无需构造遍历顺序二叉树结构（续）遍历顺序二叉树结构（续）先序3, 5, 6, 8, 9，中序5, 3, 8, 6, 9遍历顺

28、序二叉树结构（续）先序6, 8, 9中序8, 6, 9使用BinaryTreeint count = 0;BinaryTree a,x,y,z;templatevoid ct(BinaryTreeNode *t) count+;void main(void) y.MakeTree(1,a,a); z.MakeTree(2,a,a); x.MakeTree(3,y,z); y.MakeTree(4,x,a); y.PreOrder(ct); cout count endl;8.9 抽象数据类型及类的扩充m增加如下二叉树操作：PreOutput()：按前序方式输出数据域InOutput()：按中序

29、方式输出数据域PostOutput()：按后序方式输出数据域LevelOutput()：逐层输出数据域Delete()：删除一棵二叉树，释放其节点Height()：返回树的高度Size()：返回树中节点数8.9.1 输出函数m私有辅助函数static void Output(BinaryTreeNode *t) cout data ;m输出函数 void PreOutput() PreOrder(Output, root); cout endl; void InOutput() InOrder(Output, root); cout endl; void PostOutput() PostOr

30、der(Output, root); cout endl; void LevelOutput() LevelOrder(Output); cout endl;8.9.2 销毁二叉树m删除所有节点m后序遍历：删除左子树、删除右子树、删除根m辅助函数删除单个节点 static void Free(BinaryTreeNode *t) delete t;m删除二叉树void Delete() PostOrder(Free, root); root = 0;8.9.3 计算高度m后序遍历q左子树高度、右子树高度较大者+1（根节点）树的高度q递归公式：h=maxhl, hr + 1递归函数m公共接口in

31、t Height() const return Height(root);计算高度的递归函数Heighttemplate int BinaryTree:Height(BinaryTreeNode *t) const/ Return height of tree *t. if (!t) return 0; / empty tree int hl = Height(t-LeftChild); / height of left int hr = Height(t-RightChild); / height of right if (hl hr) return +hl; else return +hr

32、;8.9.4 统计节点数目m任意一种遍历方法，每个节点将统计计数加1m私有辅助函数Add1static void Add1(BinaryTreeNode *t) _count+;m节点数统计函数int Size() _count = 0; PreOrder(Add1, root); return _count;统计节点数目方法二m利用递归公式：s=sl+sr+1template int BinaryTree:Size(BinaryTreeNode *t) const if (!t) return 0; else return Size(t-LeftChild)+Size(t-RightChil

33、d)+1;8.10 应用m中缀表达式后缀表达式表达式树m后缀（postfix），逆波兰（reverse Polish）m不需要括号、优先级，运算符顺序体现计算顺序m计算机运算非常方便栈q遇到运算数pushq遇到运算符pop栈顶两个运算数，运算结果pushq最终，栈中的数即为最终计算结果利用栈计算后缀表达式m6*(5+(2+3)*8+3)6 5 2 3 + 8 * + 3 + *m6、5、2、3压栈($ 6 5 2 3 $)m+：2、3弹出，5压栈($ 6 5 5 $)m8压栈： ($ 6 5 5 8 $)m*：5、8弹出，40压栈 ($ 6 5 40 $)利用栈计算后缀表达式（续）m6 5 2

34、 3 + 8 * + 3 + *m+：5、40弹出，45压栈 ($ 6 45 $)m3压栈： ($ 6 45 3 $)m+：45、3弹出，48压栈($ 6 48 $)m*：6、48弹出，288压栈($ 288 $)中缀后缀m先看个例子，a+b*c+(d*e+f)*gm由左至右扫描，利用栈qa，一个运算数，怎么做？无论中缀、后缀还是前缀，运算对象的顺序都是一样的，输出即可($ $)，O: aq+，一个运算符，直接输出可以吗？运算符应在两个运算对象之后，显然不行压栈：($ + $)，O: aa+b*c+(d*e+f)*g（续）qb，输出已输出两个运算对象了，能输出栈中的“+”吗？运算顺序还不确定，

35、或者说，“+”的两个运算对象是否a、b还不确定，应分析后面运算符后确定q*如前所述，应考虑是否输出“+” ？不应该！ *的优先级高于+ +的运算对象不是a、b，而是a、b*c，未输出完若*在前（栈顶），+在后，显然应该输出*因此应该压栈：($ + * $)，O: a b a+b*c+(d*e+f)*g（续）q第二个+优先级比*低，*弹出栈，输出 ($ + $)，O: a b c *两个+优先级相等，怎么办？看结合顺序！左结合第一个+先计算，出栈，输出 ($ + $)，O: a b c * a+b*c+(d*e+f)*g（续）q(括号内子表达式先进行计算前面的运算符不应该再输出了，处理完括号中内

36、容再说怎么体现出来？压栈，把前面运算符屏蔽 ($ + ( $)，O: a b c * 完全可以从优先级角度描述，(的优先级最高，)的优先级最低a+b*c+(d*e+f)*g（续）q*前面是(，相当于遇到栈底，压栈 ($ + ( * $)，O: a b c * + dq+：*输出，+压栈 ($ + ( + $)，O: a b c * + d e *q)：括号内剩余运算都给执行了，不断出栈输出，直到遇到( ($ + $)，O: a b c * + d e * f +a+b*c+(d*e+f)*g（续）q*：压栈 ($ + * $)，O: a b c * + d e * f +q符号串处理完毕：不断

37、出栈输出，直至栈空 ($ $)，O: a b c * + d e * f + g * +中缀后缀算法描述m由左至右扫描表达式，利用一个栈q遇到运算数：输出q遇到运算符op：与栈顶运算符op比较栈空、op=(、op优先级高、优先级相等但是右结合运算：op压栈op优先级低、优先级相等左结合：op出栈，输出，重复此步骤op为)：栈中(之后的所有运算符依次出栈，输出，(也弹出q表达式处理完，栈中剩余运算符依次出栈、输出后缀表达式表达式树m表达式树运算顺序、运算符与运算对象的父子关系m扫描后缀表达式，就像是计算后缀表达式一样的方式，但计算结果不是一个值，而是一棵表达式树q运算对象：构造单节点树，压栈q运

38、算符：出栈两棵树，作为左右子树，运算符作为根节点，构造一棵新树，压栈q最终栈中的唯一一棵树即为最后结果后缀表达式表达式树例ma b + c d e + * *qa、b构造单节点树，压栈后缀表达式表达式树例（续）m+ c d e + * *q+：a、b两棵树出栈，作为左右子树，+作为根，构造新树，压栈后缀表达式表达式树例（续）mc d e + * *qc、d、e构造单节点树，压栈后缀表达式表达式树例（续）m+ * *q+：子树d、e构造“+”树，压栈后缀表达式表达式树例（续）m* *q*后缀表达式表达式树例（续）m*q*8.10.1 设置信号放大器*q资源，生产地使用地，通过输送网络qsigna

39、l资源q传输过程中，性能损失、衰减，噪声增加q信号衰减不超过阈值信号放大器q信号放大器放置在何处？数量最少且信号衰减不超过给定阈值问题详细描述m传输网络树形，源根节点m信号流向，节点孩子节点m边标记信号衰减量m除根外的节点可放置放大器问题详细描述（续）md(i)父节点节点i的信号衰减量md(i)阈值无解mD(i)qii为根的子树的任一节点的衰减量和的最大值qi为叶节点D(i)=0q其他节点q后序遍历计算)()()(maxijdjDiDj的孩子节点为放大器放置算法m节点i，子节点j，D(j)+d(j)阈值m不在j仿真放大器i叶的衰减阈值m应在j放置放大器，D(i)=d(j)m伪代码：D(i)=0

40、;for (i的每个孩子j)if (D(j)+d(j)tolerance)在j放置放大器;elseD(i)=maxD(i)，D(j)+d(j);定理8.1m定理8.1 上述算法所需放大器数目最少证明对树的节点数n 进行归纳当n=1时，定理显然成立设nm时，定理成立，m为任意的自然数tm+1个节点的树，X上述算法所确定的放置放大器的节点的集合，W最少节点集合，只需证明|X|=|W|若|X|=0，显然|X|=|W|考虑|X|0定理8.1考虑|X|0，设z为上述算法放置放大器的第一个节点，tz为以z为根的子树D(z)+d(z)阈值W至少包含tz中某个节点u若W还包含其它节点，则W-类似u的节点+z也

41、满足要求W不是最优方案因此W中包含的tz中节点只有u令W=W-u，t=t-tzW是t的最优方案X=X-z也是t的一个方案，且|t|m+1|X|=|W|X|=|X| + 1=|W| + 1=|W|类Boosterclass Booster / 作为二叉树节点的数据域 friend void main(void); friend void PlaceBoosters(BinaryTreeNode *); public: void Output(ostream& out) const out boost D d ; private: int D, / degradation to leaf

42、d; / degradation from parent bool boost; / true iff booster here;/ overload ostream& operator(ostream& out, Booster x) x.Output(out); return out;计算D值、放置放大器函数/ 作为PostOrder的参数void PlaceBoosters(BinaryTreeNode *x)/ Compute degradation at *x. Place booster / here if degradation exceeds tolerance

43、. BinaryTreeNode *y = x-LeftChild; int degradation; x-data.D = 0; / initialize degradation at x if (y) / compute from left child degradation = y-data.D + y-data.d; if (degradation tolerance) y-data.boost = true; x-data.D = y-data.d; else x-data.D = degradation; PlaceBoosters函数（续） y = x-RightChild; i

44、f (y) / compute from right child degradation = y-data.D + y-data.d; if (degradation tolerance) y-data.boost = true; degradation = y-data.d; if (x-data.D data.D = degradation; 8.10.2 在线等价类问题m合并/搜索（union-find）问题m等价类树指针，孩子父树的描述m模拟指针m节点索引元素值，parent域操作实现int *parent;void Initialize(int n)/ One element per

45、 set/class/tree. parent = new intn+1; for (int e = 1; e um每次合并Q(1)，每次查找由树高决定m最坏情况，树高=元素数目Union(2, 1), Union(3, 2), Union(4,3), .m每次查找Q(q)，q为之前合并操作次数性能改进m定义重量规则：若树i 节点数少于树j 节点数，则将j 作为i 的父节点，否则将i 作为j 的父节点m定义高度规则：若树i 的高度小于树j 的高度，则将j 作为i 的父节点，否则将i 作为j 的父节点重量规则实现mroot：标记根，根的parent保存节点数目int *parent;bool *root;void