二叉树和其他树

1、讲师：尹成 QQ:77025077 博客:http:/ 微博:http:/ Mail: 网址:http:/ C/C+ 算法算法+实战实战 传智播客传智播客 http:/ 高薪就业高薪就业 第8章 二叉树和其他树 学习内容 m简单树和二叉树 q术语 q公式化描述和链表描述 q遍历 m应用 q表达式后缀表示表达式树 8.1 树 m线性表、表：不适合描述层次结构数据 m祖先后代、上级下属、整体部分 m树结构：模仿自然界中的植物树 例8-1：家庭关系 例8-2 m公司结构 例8-3 m政府机构 例8-4 m软件工程 数据结构“树” m定义： 树（tree）t是一个非空的有限元素的集合， 一个特殊的元素

2、称为根（root）， 余下的元素（如果有的话）组成t的若干 子树（subtree） m递归！ 例8-6 家庭关系例树的描述 m数据集合 Joe，Ann，Mary，Mark，Sue，John， Chris mn=7，根为Joe 家庭关系例树的描述（续） m余下的元素 qAnn单一元素子树 qMary，Mark，Sue，根为Mary的子树 Mark和Sue，均为单元素的子树 qJohn，Chris，根为John的子树 Chris 也为单元素子树 相关术语 m元素节点 m根节点与子树的根节点的关系边 m边的两端父母（parent）和孩子（children） 相关术语（续） m相同父母的节点兄弟（si

3、bling） m祖父孙子，祖先后代 m叶节点没有孩子的节点，非叶节点非 终端节点 相关术语（续） m根没有父节点的节点 m层（level）：根1，根的孩子2，. m节点的度（degree）：孩子数目，叶0 例8-6 m公司机构例 q公司雇员节点，总裁根 q副总裁总裁的子节点，总裁副总裁的 父节点 q不同副总裁兄弟节点 例8-6 （续） m政府机构例 q联邦政府国防部，教育部，.，税务部的 父节点 q国防部的子节点陆军、海军、空军、海军 陆战队兄弟节点，叶节点 自由树 有根树 有序树 森林和有序森林 m森林（forest）：）：树的集合，通常认为是 有根树的集合 m有序森林（orchard，or

4、dered forest）：）： 有序树的有序集合 m有根树去掉根节点（有序）森林 m（有序）森林添加父节点有根树 森林和有序森林（续） 有根树的递归定义 m有根树： 包含单一顶点v，称为树的根， 和一个森林F，F的树称为根的子树 而森林F（可为空）是一个有根树的集合 有序树的定义 m一个有序树T： 包含一个单一节点v，称为树的根， 和一个有序森林O，O的树称为v的子树， 表示为T=v, O 有序森林的定义 m一个有序森林O： 或者为空集， 或包含一个有序树T，称为有序森林的第 一树， 和另一个有序森林O（包含有序森林的 其它树），可表示为O=T, O m有序树有序森林：间接递归定义 有序森林

5、 8.2 二叉树 m定义： 二叉树（binary tree）t是有限元素集合： 或者为空； 或者，有一个特殊元素根，余下的元素 构成2个二叉树（可以为空）t的左子 树和右子树 二叉树和树的根本区别 m二叉树可以为空 树不行 m二叉树每个节点都恰好有两棵子树（可 以为空） 树中每个节点可有若干子树 m二叉树每个节点的子树是有序的 “左”、“右” 树的子树间是无序的 二叉树例递归构造 m空二叉树递归的停止 m单一节点二叉树 m两个节点： 不同！不能表示为 二叉树例递归构造（续） m三个节点 q根左子树(2)右子树(0)、11、02 m类似方式，可构造更大的二叉树 二叉树例：表达式树 a)a*b +

6、 c/d b)a+b+c+d c)(-a+(x+y)/(+b*(c*a) 8.3 二叉树的特性 m特性1 包含n (n0)个节点的二叉树边数为 n-1 证明 二叉树中每个节点（除根节点，共n-1个 节点） 有且只有一个父节点 每个子节点与父节点间有且只有一条边 边数为n-1 特性2 m二叉树的高度（height）（深度，depth）： 二叉树的层数 m特性2 若二叉树的高度为h，h0，则它 最少有h个节点，最多有2h-1个节点 特性2的证明 证明 每层最少要有1个节点节点数最少为h 每个节点最多有2个子节点则第i层节 点最多为2i-1个，i0 节点的总数不会超过122 1 1 h h i i

7、特性3 m特性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, 1ik m即为完全二叉树，深度为 ) 1(log2n 特性4 m特性4 设完全二叉树中一节点的序号为 i, 1in。则

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

9、n-(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); BinaryTreeNode类

10、 public: BinaryTreeNode() LeftChild = RightChild = 0; BinaryTreeNode(const T LeftChild = RightChild = 0; BinaryTreeNode(const T LeftChild = l; RightChild = r; private: T data; BinaryTreeNode *LeftChild, / left subtree *RightChild; / right subtree ; 二叉树与有序森林的对应关系 m二叉树的另一种定义：一个二叉树B 或者是空集， 或者包含一个根v和两个二

11、叉树B1和B2， 可表示为B=v, B1, B2 m定理11.1：令S为任意顶点集合，则以S为 顶点集合的有序森林集合和以S为顶点集 合的二叉树集合之间存在一一映射f 任一有序森林均有任一二叉树与之对应 证明（数学归纳法） 对空集S，有序森林和二叉树均为空，映 射关系f()=，命题成立 假定对所有|S|n，命题成立，考虑|S|=n 若森林O不为空 O=T, O2 ，T第一树为有序树， O2为另一森林（森林定义）1 对应关系的证明（续） 另有T=v, O1 ，v为顶点，O1为另一森 林（有序树定义）2 由1、2O=v, O1, O2 O1和O2节点数必然 n存在一一对应的 二叉树f(O1)和f(

12、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若为数学表达式树，计算该数学表达式 m若为数学表达式树，给出对应的带括号 的表达式 m都可通过二叉树遍历（按某种顺序访问

13、 所有节点，且只访问一次）来完成 8.6 二叉树遍历 m遍历顺序 q访问根节点、左子树、右子树的顺序 q左右子树的访问（遍历）？递归！ m可能的遍历顺序 qV根，L左子树，R右子树 qVLR LVR LRV VRL RVL RLV 标准遍历顺序 m都是左子树先于右子树，关键根的 访问次序 m先序遍历（preorder）VLR m中序遍历（inorder）LVR m后序遍历（postorder）LRV 先序遍历 template void PreOrder(BinaryTreeNode *t) / Preorder traversal of *t. if (t) Visit(t); / visi

14、t 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 subtree 后序遍历 template

15、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 先序遍历表达式树 a)+*ab/cd b)+abcd c)/+-a+xy*+b*ca m前缀表达式 中序遍历表达式树 a)a*b + c/d b)a+b+c+d c)-a+x+y/+b*c*a m中缀表达式 人类习惯 m需加括号 后

16、序遍历表达式树 a)ab*cd/+ b)ab+c+d+ c)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 LevelOrd

17、er(BinaryTreeNode *t) / 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; 最坏情

18、况空间复杂性O(n) 时间复杂性(n) 8.7 抽象数据类型BinaryTree 抽象数据类型BinaryTree 实例 元素集合；如果不空，则被划分为根节点、左 子树和右子树；每个子树仍是一个二叉树 操作 Create()：创建一个空的二叉树； IsEmpty：如果二叉树为空，则返回true，否则 返回false Root(x)：取x为根节点；如果操作失败，则返 回false，否则返回true 抽象数据类型（续） MakeTree(root，left，right)：创建一个二叉树， root作为根节点，left作为左子树，right作 为右子树 BreakTree(root，left，rig

19、ht)：拆分二叉树 PreOrder：先序遍历 InOrder：中序遍历 PostOrder：后序遍历 LevelOrder：逐层遍历 8.8 类BinaryTree template class BinaryTree public: BinaryTree() root = 0; BinaryTree(); bool IsEmpty() const return (root) ? false : true); bool Root(T void MakeTree(const T void BreakTree(T void PreOrder(void(*Visit)(BinaryTreeNode

20、*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)(BinaryTreeNode *u); private: BinaryTreeNode *root; / pointer to root void PreOrder(void(*Vi

21、sit) (BinaryTreeNode *u), BinaryTreeNode *t); void InOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void PostOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); ; 获取根节点数据 template bool BinaryTree:Root(T return true; else return false; / no root 创建树 template void BinaryTree:MakeT

22、ree(const T / deny access from trees left and right left.root = right.root = 0; 缺陷：允许 MakeTree(e, X, X)且X 不为空 为什么置为空？不会造成空 悬指针吗？ 分裂树 template void BinaryTree:BreakTree(T / tree empty / break the tree element = root-data; left.root = root-LeftChild; right.root = root-RightChild; delete root; root = 0

23、; 与上例相同的道理 先序遍历 template void BinaryTree:PreOrder(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) / Inorde

24、r traversal. if (t) InOrder(Visit, t-LeftChild); Visit(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 vo

25、id BinaryTree:LevelOrder(void(*Visit)(BinaryTreeNode *u) / 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一棵二叉

26、树 先序遍历结果1, 2, 4, 7, 3, 5, 6, 8, 9 中序遍历结果4, 7, 2, 1, 5, 3, 8, 6, 9 能推导出其结构吗？ m可以！ 第一步 1, 2, 4, 7, 3, 5, 6, 8, 9 4, 7, 2, 1, 5, 3, 8, 6, 9 m先序遍历 根左子树右子树“1”必为根节点 m中序遍历 左子树根右子树，且1为根节点 4, 7, 2为左子树，5, 3, 8, 6, 9为右子树 下面怎么办？递归！ m左子树 先序遍历2, 4, 7 中序遍历4, 7, 2 m右子树 先序遍历3, 5, 6, 8, 9 中序为5, 3, 8, 6, 9 m利用相同方法构造左、

27、右子树，直至列 表长度为0空子树，无需构造 遍历顺序二叉树结构（续） 遍历顺序二叉树结构（续） 先序3, 5, 6, 8, 9， 中序5, 3, 8, 6, 9 遍历顺序二叉树结构（续） 先序6, 8, 9 中序8, 6, 9 使用BinaryTree int count = 0; BinaryTree a,x,y,z; template void 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.

28、PreOrder(ct); cout count endl; 8.9 抽象数据类型及类的扩充 m增加如下二叉树操作： PreOutput()：按前序方式输出数据域 InOutput()：按中序方式输出数据域 PostOutput()：按后序方式输出数据域 LevelOutput()：逐层输出数据域 Delete()：删除一棵二叉树，释放其节点 Height()：返回树的高度 Size()：返回树中节点数 8.9.1 输出函数 m私有辅助函数 static void Output(BinaryTreeNode *t) cout data ; m输出函数 void PreOutput() PreO

29、rder(Output, root); cout endl; void InOutput() InOrder(Output, root); cout endl; void PostOutput() PostOrder(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 De

30、lete() PostOrder(Free, root); root = 0; 8.9.3 计算高度 m后序遍历 q左子树高度、右子树高度较大者+1（根节点） 树的高度 q递归公式：h=maxhl, hr + 1递归函数 m公共接口 int Height() const return Height(root); 计算高度的递归函数Height template int BinaryTree:Height(BinaryTreeNode *t) const / Return height of tree *t. if (!t) return 0; / empty tree int hl = Hei

31、ght(t-LeftChild); / height of left int hr = Height(t-RightChild); / height of right if (hl hr) return +hl; else return +hr; 8.9.4 统计节点数目 m任意一种遍历方法，每个节点将统计计 数加1 m私有辅助函数Add1 static void Add1(BinaryTreeNode *t) _count+; m节点数统计函数 int Size() _count = 0; PreOrder(Add1, root); return _count; 统计节点数目方法二 m利用递

32、归公式：s=sl+sr+1 template int BinaryTree:Size(BinaryTreeNode *t) const if (!t) return 0; else return Size(t-LeftChild)+Size(t-RightChild)+1; 8.10 应用 m中缀表达式后缀表达式表达式树 m后缀（postfix），逆波兰（reverse Polish） m不需要括号、优先级，运算符顺序体现 计算顺序 m计算机运算非常方便栈 q遇到运算数push q遇到运算符pop栈顶两个运算数，运算 结果push q最终，栈中的数即为最终计算结果 利用栈计算后缀表达式 m6*

33、(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 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)*g m由左至右扫描，利

34、用栈 qa，一个运算数，怎么做？ 无论中缀、后缀还是前缀，运算对象的顺序都是 一样的，输出即可 ($ $)，O: a q+，一个运算符，直接输出可以吗？ 运算符应在两个运算对象之后，显然不行 压栈：($ + $)，O: a a+b*c+(d*e+f)*g（续） qb，输出 已输出两个运算对象了，能输出栈中的“+”吗？ 运算顺序还不确定，或者说，“+”的两个运算对 象是否a、b还不确定，应分析后面运算符后确定 q* 如前所述，应考虑是否输出“+” ？不应该！ *的优先级高于+ +的运算对象不是a、b，而是a、b*c，未输出完 若*在前（栈顶），+在后，显然应该输出* 因此应该压栈：($ + *

35、$)，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( 括号内子表达式先进行计算前面的运算符不 应该再输出了，处理完括号中内容再说 怎么体现出来？压栈，把前面运算符屏蔽 ($ + ( $)，O: a b c * 完全可以从优先级角度描述，(的优先级最高，) 的优先级最低 a+b*c+(d*e+f)*g（续） q* 前面是(，相当于遇到栈底，压栈 ($ + (

36、* $)，O: a b c * + d q+：*输出，+压栈 ($ + ( + $)，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符号串处理完毕：不断出栈输出，直至栈 空 ($ $)，O: a b c * + d e * f + g * + 中缀后缀算法描述 m由左至右扫描表达式，利用一个栈 q遇到运算数：输出 q遇到运算符op：与栈顶运算符op比较 栈空、op=

37、(、op优先级高、优先级相等但是右 结合运算：op压栈 op优先级低、优先级相等左结合：op出栈，输 出，重复此步骤 op为)：栈中(之后的所有运算符依次出栈，输出， (也弹出 q表达式处理完，栈中剩余运算符依次出栈、 输出 后缀表达式表达式树 m表达式树运算顺序、运算符与运算 对象的父子关系 m扫描后缀表达式，就像是计算后缀表达 式一样的方式，但计算结果不是一个值， 而是一棵表达式树 q运算对象：构造单节点树，压栈 q运算符：出栈两棵树，作为左右子树，运算 符作为根节点，构造一棵新树，压栈 q最终栈中的唯一一棵树即为最后结果 后缀表达式表达式树例 ma b + c d e + * * qa、

38、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资源，生产地使用地，通过输送网络 qsignal资源 q传输过程中，性能损失、衰减，噪声增加 q信号衰减不超过阈值信号放大器 q信号放大器放置在何处？ 数量最少 且信号衰减

39、不超过给定阈值 问题详细描述 m传输网络树形，源根节点 m信号流向，节点孩子节点 m边标记信号衰减量 m除根外的节点可放置放大器 问题详细描述（续） md(i)父节点节点i的信号衰减量 md(i)阈值无解 mD(i) qii为根的子树的任一节点的衰减量和的最 大值 qi为叶节点D(i)=0 q其他节点 q后序遍历计算 )()()( max i jdjDiD j 的孩子节点为 放大器放置算法 m节点i，子节点j，D(j)+d(j)阈值 m不在j仿真放大器i叶的衰减阈值 m应在j放置放大器，D(i)=d(j) m伪代码： D(i)=0; for (i的每个孩子j) if (D(j)+d(j)tol

40、erance) 在j放置放大器; else D(i)=maxD(i)，D(j)+d(j); 定理8.1 m定理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 也满足要求W不是最优方

41、案 因此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| 类Booster class Booster / 作为二叉树节点的数据域 friend void main(void); friend void PlaceBoosters(BinaryTreeNode *); public: void Output(ostream private: int D, / degradation to leaf d; / degradation from parent bool

42、boost; / true iff booster here ; / overload ostream return out; 计算D值、放置放大器函数 / 作为PostOrder的参数 void PlaceBoosters(BinaryTreeNode *x) / Compute degradation at *x. Place booster / here if degradation exceeds tolerance. BinaryTreeNode *y = x-LeftChild; int degradation; x-data.D = 0; / initialize degrada

43、tion 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; if (y) / compute from right child degradation = y-data.D + y-data.d; if (degradation to

44、lerance) 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 set/class/tree. parent = new intn+1; for (int e = 1; e u m每次合并Q(1)，每次查找由树高决定

45、 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 Initialize(int n) / One element per set/class/tree. root = new booln+1; parent = new intn