第8章 二叉树和其他树

1、计算机与控制工程学院第第8 8章章 二叉树和其他树二叉树和其他树-一种具有分支层次关系的数据结构一种具有分支层次关系的数据结构计算机与控制工程学院主要内容主要内容 树的一般定义树的一般定义 二叉树的定义和操作二叉树的定义和操作 二叉树的遍历二叉树的遍历2计算机与控制工程学院树树 线性表、表：不适合描述线性表、表：不适合描述层次结构层次结构数据数据 祖先后代、上级下属、整体部分祖先后代、上级下属、整体部分3计算机与控制工程学院4计算机与控制工程学院例例8-18-1：家庭关系：家庭关系5计算机与控制工程学院例例8-28-2 公司结构公司结构6计算机与控制工程学院例例8-38-3 政府机构政府机构7

2、计算机与控制工程学院例例8-48-4 软件工程软件工程8计算机与控制工程学院9计算机与控制工程学院数据结构数据结构“树树” 定义定义：树树（treetree）t t是一个非空的有限元素的集合，是一个非空的有限元素的集合，一个特殊的元素称为一个特殊的元素称为根根（rootroot），），余下的元素（如果有的话）组成余下的元素（如果有的话）组成t t的若干的若干子树子树（subtreesubtree） 递归！递归！10计算机与控制工程学院例例8-6 8-6 家庭关系例树的描述家庭关系例树的描述 数据集合数据集合JoeJoe，AnnAnn，MaryMary，MarkMark，SueSue，JohnJ

3、ohn，ChrisChris n=7n=7，根为，根为JoeJoe11计算机与控制工程学院家庭关系例树的描述（续）家庭关系例树的描述（续） 余下的元素余下的元素 AnnAnn单一元素子树单一元素子树 MaryMary，MarkMark，SueSue，根为，根为MaryMary的子树的子树 MarkMark和和SueSue，均为单元素的子树，均为单元素的子树 JohnJohn，ChrisChris，根为，根为JohnJohn的子树的子树 Chris Chris 也为单元素子树也为单元素子树12计算机与控制工程学院相关术语相关术语 元素元素节点节点 根节点与子树的根节点的关系根节点与子树的根节点的

4、关系边边 边的两端边的两端父母父母（parentparent）和）和孩子孩子（childrenchildren）13计算机与控制工程学院相关术语（续）相关术语（续） 相同父母的节点相同父母的节点兄弟兄弟（siblingsibling） 祖父祖父孙子孙子，祖先祖先后代后代 叶叶节点节点没有孩子的节点，非叶节点没有孩子的节点，非叶节点非非终端节点终端节点14计算机与控制工程学院相关术语（续）相关术语（续） 根根没有父节点的节点没有父节点的节点 层层（levellevel）：根）：根11，根的孩子，根的孩子22，. 节点的节点的度度（degreedegree）：孩子数目，叶）：孩子数目，叶0015计

5、算机与控制工程学院例例8-68-6 公司机构例公司机构例 公司雇员公司雇员节点，总裁节点，总裁根根 副总裁副总裁总裁的子节点，总裁总裁的子节点，总裁副总裁的父节点副总裁的父节点 不同副总裁不同副总裁兄弟节点兄弟节点16计算机与控制工程学院例例8-6 8-6 （续）（续） 政府机构例政府机构例 联邦政府联邦政府国防部，教育部，国防部，教育部，.，税务部的父节点，税务部的父节点 国防部的子节点国防部的子节点陆军、海军、空军、海军陆战陆军、海军、空军、海军陆战队队兄弟节点，叶节点兄弟节点，叶节点17计算机与控制工程学院树的相关概念树的相关概念 树、子树树、子树 根、分支节点、叶子节点根、分支节点、叶

6、子节点 父节点、孩子节点、兄弟节点父节点、孩子节点、兄弟节点 祖父、孙子、祖先、后代祖父、孙子、祖先、后代 边边 级、深度、高度级、深度、高度 度度18计算机与控制工程学院自由树自由树19计算机与控制工程学院有根树有根树20计算机与控制工程学院有序树有序树21计算机与控制工程学院森林和有序森林森林和有序森林 森林森林（forestforest）：）：树的集合，通常认为是有树的集合，通常认为是有根树的集合根树的集合 有序森林有序森林（orchardorchard，ordered forestordered forest）：）：有序树的有序集合有序树的有序集合 有根（有序）树去掉根节点有根（有序）

7、树去掉根节点（有序）森林（有序）森林 （有序）森林添加父节点（有序）森林添加父节点有根（有序）树有根（有序）树 22计算机与控制工程学院森林和有序森林（续）森林和有序森林（续）23计算机与控制工程学院有根树的递归定义有根树的递归定义 有根树有根树：包含单一顶点包含单一顶点v v，称为树的，称为树的根根，和一个森林和一个森林F F，F F的树称为的树称为根的子树根的子树而而森林森林F F（可为空）是一个有根树的集合（可为空）是一个有根树的集合24计算机与控制工程学院有序树的定义有序树的定义 一个一个有序树有序树T T：包含一个单一节点包含一个单一节点v v，称为树的，称为树的根根，和一个和一个有

8、序森林有序森林O O，O O的树称为的树称为v v的子树，表示为的子树，表示为T=v, OT=v, O25计算机与控制工程学院有序森林的定义有序森林的定义 一个一个有序森林有序森林O O：或者为空集或者为空集，或包含一个有序树或包含一个有序树T T，称为有序森林的，称为有序森林的第一树第一树，和另一个有序森林和另一个有序森林OO（包含有序森林的其它（包含有序森林的其它树），可表示为树），可表示为O=T, OO=T, O 有序树有序森林：间接递归定义有序树有序森林：间接递归定义26计算机与控制工程学院有序森林有序森林27计算机与控制工程学院课堂练习课堂练习 一棵有一棵有n n个结点的树的所有结点

9、的度数之和个结点的树的所有结点的度数之和是多少？是多少？28n-1计算机与控制工程学院课堂练习课堂练习 如果一棵树有如果一棵树有n n1 1个度为个度为1 1的节点，有的节点，有n n2 2个度为个度为2 2的节点，的节点，n nm m个度为个度为m m的节点，试问有的节点，试问有多少个度为多少个度为0 0的节点？的节点？29miimiinnin1101计算机与控制工程学院主要内容主要内容 树的一般定义树的一般定义 二叉树的定义和操作二叉树的定义和操作 二叉树的遍历二叉树的遍历30计算机与控制工程学院二叉树二叉树 定义定义： 二叉树二叉树（binary treebinary tree）t t是

10、有限元素集合：是有限元素集合：或者为空；或者为空；或者，有一个特殊元素或者，有一个特殊元素根根，余下的元素构成，余下的元素构成2 2个个二叉树（可以为空）二叉树（可以为空）tt的的左子树左子树和和右子树右子树31计算机与控制工程学院二叉树和树的根本区别二叉树和树的根本区别 二叉树可以为空二叉树可以为空树不行树不行 二叉树每个节点都恰好有两棵子树（可以为空）二叉树每个节点都恰好有两棵子树（可以为空）树中每个节点可有若干子树树中每个节点可有若干子树 二叉树每个节点的子树是有序的二叉树每个节点的子树是有序的“左左”、“右右”树的子树间是无序的树的子树间是无序的32计算机与控制工程学院二叉树例二叉树例

11、递归构造递归构造 空二叉树空二叉树递归的停止递归的停止 单一节点二叉树单一节点二叉树 两个节点：两个节点：不同！不能表示为不同！不能表示为33计算机与控制工程学院二叉树例二叉树例递归构造（续）递归构造（续） 三个节点三个节点 根左子树根左子树(2)(2)右子树右子树(0)(0)、1 11 1、0 02 2 类似方式，可构造更大的二叉树类似方式，可构造更大的二叉树34计算机与控制工程学院二叉树例：表达式树二叉树例：表达式树a)a)a a* *b + c/db + c/db)b)a+b+c+da+b+c+dc)c)(-a+(x+y)/(+b(-a+(x+y)/(+b* *(c(c* *a)a)35

12、计算机与控制工程学院二叉树的特性二叉树的特性 特性特性1 1 包含包含n n ( (n n0)0)个节点的二叉树边数为个节点的二叉树边数为n n-1-1证明证明二叉树中每个节点（除根节点，共二叉树中每个节点（除根节点，共n-1n-1个节个节点）点） 有且只有一个父节点有且只有一个父节点每个子节点与父节点间有且只有一条边每个子节点与父节点间有且只有一条边边数为边数为n n-1-136计算机与控制工程学院特性特性2 2 二叉树的二叉树的高度高度（heightheight）（）（深度深度，depthdepth）：）：二叉树的层数二叉树的层数 特性特性2 2 若二叉树的高度为若二叉树的高度为h h，h

13、 h00，则它最，则它最少有少有h h个节点，最多有个节点，最多有2 2h h-1-1个节点个节点37计算机与控制工程学院特性特性2 2的证明的证明证明证明每层最少要有每层最少要有1 1个节点个节点节点数最少为节点数最少为h h每个节点最多有每个节点最多有2 2个子节点个子节点则第则第i i层节点最层节点最多为多为2 2i i-1-1个，个，i i11节点的总数不会超过节点的总数不会超过12222211011hhhii38计算机与控制工程学院特性特性2 2说明说明深度深度该层最多节点数该层最多节点数二叉树的最多节点总数二叉树的最多节点总数120=11221=23322=47423=815524

14、=1631625=326339计算机与控制工程学院特性特性3 3 特性特性3 3 包含包含n n个节点的二叉树的高度最大为个节点的二叉树的高度最大为n n，最小为，最小为证明证明每层至少一个元素每层至少一个元素高度不会超过高度不会超过n n由特性由特性2 2，可知高度为，可知高度为h h，节点最多，节点最多2 2h h-1-1即即n n22h h-1-1h hloglog2 2( (n n+1)+1)且且h h是整数是整数) 1(log2n) 1(log2nh40计算机与控制工程学院满二叉树（满二叉树（full binary tree full binary tree ） 高度为高度为h h，

15、节点数，节点数2 2h h-1-141计算机与控制工程学院完全二叉树完全二叉树 高度为高度为h h 的满二叉树中节点按从上到下，从的满二叉树中节点按从上到下，从左到右的顺序从左到右的顺序从1 1到到2 2h h-1-1进行编号进行编号 从中删除从中删除k k个节点，编号为个节点，编号为2 2h h- -i i, 1, 1i ik k 即为即为完全二叉树，深度为完全二叉树，深度为) 1(log2n42计算机与控制工程学院另一种定义方法另一种定义方法 设二叉树设二叉树T T有有n n个节点，令个节点，令则则k k代表最下一层，也就是二叉树的深度，代表最下一层，也就是二叉树的深度，r r代代表第表第

16、k k层的节点数，其中层的节点数，其中2 2k-1k-1个节点放满第个节点放满第1 1到到第第k-1k-1层，则：层，则：若若0r=20r 1 1，则该元素父节点的编号为则该元素父节点的编号为2)2) 当当2 2i i n n时，该元素无左孩子。否则，其左孩时，该元素无左孩子。否则，其左孩子的编号为子的编号为2 2i i3)3) 若若2 2i i + 1+ 1n n，该元素无右孩子。否则，其右，该元素无右孩子。否则，其右孩子编号为孩子编号为2 2i i + 1+ 12/ i44计算机与控制工程学院特性特性4 4（续）（续）证明证明通过对通过对i i 进行归纳即可得证进行归纳即可得证45计算机与

17、控制工程学院特性特性5 5 设二叉树中度为设二叉树中度为2 2的节点有的节点有n n2 2个，度为个，度为1 1的节的节点有点有n n1 1个，度为个，度为0 0的节点有的节点有n n0 0个，则个，则n n0 0=n=n2 2+1+1 一棵二叉树有一棵二叉树有10241024个节点，其中个节点，其中465465个是叶个是叶节点，那么树中度为节点，那么树中度为2 2和度为和度为1 1的节点各有多的节点各有多少？少？461110miinin464,95计算机与控制工程学院思考思考 一棵二叉树有一棵二叉树有1919个节点，其中个节点，其中6 6个是叶节点个是叶节点，那么树中度为，那么树中度为2 2

18、和度为和度为1 1的节点各有多少？的节点各有多少？ 能否构造一棵符合条件的能否构造一棵符合条件的二叉树二叉树？ 能否构造一棵符合条件的能否构造一棵符合条件的完全二叉树完全二叉树？475,8计算机与控制工程学院思考思考 有有m m个叶子的个叶子的二叉树二叉树最多有多少个节点？最多有多少个节点？ 有有m m个叶子的个叶子的完全二叉树完全二叉树最多有多少个节点？最多有多少个节点？48无穷无穷计算机与控制工程学院课堂练习课堂练习 设高度为设高度为h h的二叉树中只有度为的二叉树中只有度为0 0和度为和度为2 2的的节点，则此类二叉树所包含的节点数至少为节点，则此类二叉树所包含的节点数至少为_，至多为，

19、至多为_。492h-12h-1计算机与控制工程学院课堂练习课堂练习 设完全二叉树的第设完全二叉树的第6 6层有层有2424个叶节点，则此个叶节点，则此树最多有树最多有_个节点个节点A. 55A. 55B. 79B. 79C. 81C. 81D. 127D. 12750B计算机与控制工程学院二叉树描述二叉树描述 公式化描述公式化描述利用特性利用特性4 4 普通二叉树普通二叉树缺少部分节点的完全二叉树缺少部分节点的完全二叉树51计算机与控制工程学院公式化描述公式化描述 数组位置数组位置节点编号节点编号 父子节点关系父子节点关系特性特性4 452计算机与控制工程学院公式化描述公式化描述 n n层二叉

20、树层二叉树22n n-1-1数组保存，可能空间浪费！数组保存，可能空间浪费！53计算机与控制工程学院链表描述链表描述 树节点树节点节点类对象节点类对象 数据域、数据域、LeftChildLeftChild、RightChildRightChild n-1n-1条边条边2n-(n-1)=n+12n-(n-1)=n+1个空指针个空指针54计算机与控制工程学院BinaryTreeNodeBinaryTreeNode类类template class BinaryTreeNode public: BinaryTreeNode() LeftChild = RightChild = 0; BinaryTre

21、eNode(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 subtree *RightChild; / right subtree;55计算机与控制工程学院抽象数据类型抽象数据类型BinaryTreeBinaryTre

22、e抽象数据类型抽象数据类型BinaryTreeBinaryTree 实例实例元素集合；如果不空，则被划分为根节点、左子树和右子树；元素集合；如果不空，则被划分为根节点、左子树和右子树；每个子树仍是一个二叉树每个子树仍是一个二叉树操作操作CreateCreate()()：创建一个空的二叉树；：创建一个空的二叉树；IsEmptyIsEmpty：如果二叉树为空，则返回：如果二叉树为空，则返回truetrue，否则返回，否则返回falsefalseRootRoot( (x x) )：取：取x x为根节点；如果操作失败，则返为根节点；如果操作失败，则返回回falsefalse，否则返回，否则返回true

23、true56计算机与控制工程学院抽象数据类型（续）抽象数据类型（续）MakeTreeMakeTree( (rootroot，leftleft，rightright) )：创建一个二叉树，：创建一个二叉树，rootroot作为作为根节点，根节点，leftleft作为左子树，作为左子树，rightright作作为右子树为右子树BreakTreeBreakTree( (rootroot，leftleft，rightright) )：拆分二叉树：拆分二叉树PreOrderPreOrder：先序遍历：先序遍历InOrderInOrder：中序遍历：中序遍历PostOrderPostOrder：后序遍历：

24、后序遍历LevelOrderLevelOrder：逐层遍历：逐层遍历 57计算机与控制工程学院类类BinaryTreeBinaryTreetemplateclass 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);

25、void BreakTree(T& element, BinaryTree& left, BinaryTree& right); void PreOrder(void(*Visit)(BinaryTreeNode *u) PreOrder(Visit, root);58计算机与控制工程学院类类BinaryTreeBinaryTree（续）（续） void InOrder(void(*Visit)(BinaryTreeNode *u) InOrder(Visit, root); void PostOrder(void(*Visit)(BinaryTreeNode *u)

26、PostOrder(Visit, root); void LevelOrder(void(*Visit)(BinaryTreeNode *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

27、*u), BinaryTreeNode *t);59计算机与控制工程学院获取根节点数据获取根节点数据templatebool BinaryTree:Root(T& x) const/ Return root data in x. / Return false if no root. if (root) x = root-data; return true; else return false; / no root60计算机与控制工程学院创建树创建树templatevoid BinaryTree:MakeTree(const T& element, BinaryTree&

28、 left, BinaryTree& right)/ Combine left, right, and element to make new tree. / left, 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,

29、 X)且X不为空61计算机与控制工程学院分裂树分裂树templatevoid BinaryTree:BreakTree(T& element, BinaryTree& 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.

30、root = root-RightChild; delete root; root = 0;62计算机与控制工程学院思考思考 在上述存储方式下，寻找某一节点孩子的复在上述存储方式下，寻找某一节点孩子的复杂度是杂度是O(1)O(1)，寻找其父亲的复杂度是，寻找其父亲的复杂度是O(n)O(n)，为什么？为什么？ 如果希望将寻找父节点的效率提高到如果希望将寻找父节点的效率提高到O(1)O(1)，如何做？如何做？63计算机与控制工程学院主要内容主要内容 树的一般定义树的一般定义 二叉树的定义和操作二叉树的定义和操作 二叉树的遍历二叉树的遍历64计算机与控制工程学院二叉树遍历二叉树遍历 按照某种顺序访问

31、树中的每个节点，按照某种顺序访问树中的每个节点， 要求每个节点被访问一次且仅被访问一次要求每个节点被访问一次且仅被访问一次 这就是这就是二叉树遍历问题二叉树遍历问题65计算机与控制工程学院二叉树遍历二叉树遍历 遍历顺序遍历顺序【关键关键】 访问根节点、左子树、右子树的顺序访问根节点、左子树、右子树的顺序 左右子树的访问（遍历）？左右子树的访问（遍历）？递归！递归！ 可能的遍历顺序可能的遍历顺序 V V根，根，L L左子树，左子树，R R右子树右子树 VLR LVR LRV VRL RVL RLVVLR LVR LRV VRL RVL RLV66计算机与控制工程学院标准遍历顺序标准遍历顺序 都是

32、左子树先于右子树，关键都是左子树先于右子树，关键根的访问次根的访问次序序 先序遍历（先序遍历（preorderpreorder）VLRVLR 中序遍历（中序遍历（inorderinorder）LVRLVR 后序遍历（后序遍历（postorderpostorder）LRVLRVVLR67计算机与控制工程学院先序遍历先序遍历template void PreOrder(BinaryTreeNode *t)/ Preorder traversal of *t. if (t) Visit(t); / visit tree root PreOrder(t-LeftChild); / do left su

33、btree PreOrder(t-RightChild); / do right subtree 68计算机与控制工程学院中序遍历中序遍历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 69计算机与控制工程学院后序遍历后序遍历template void PostOrder(Bin

34、aryTreeNode *t)/ Postorder traversal of *t. if (t) PostOrder(t-LeftChild); / do left subtree PostOrder(t-RightChild); / do right subtree Visit(t); / visit tree root 70计算机与控制工程学院先序遍历表达式树先序遍历表达式树a)+*ab/cdb)+abcdc)/+-a+xy*+b*cam前缀表达式71计算机与控制工程学院中序遍历表达式树中序遍历表达式树a)a*b + c/db)a+b+c+dc)-a+x+y/+b*c*am中缀表达式人

35、类习惯m需加括号72计算机与控制工程学院后序遍历表达式树后序遍历表达式树a)ab*cd/+b)ab+c+d+c)a-xy+b+ca*/m后缀表达式计算机计算非常方便73计算机与控制工程学院输出完全括号化的中缀表达式输出完全括号化的中缀表达式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 );74

36、计算机与控制工程学院逐层遍历（宽度优先）逐层遍历（宽度优先） 根根叶逐层，同层由左至右叶逐层，同层由左至右template void LevelOrder(BinaryTreeNode *t)/ Level-order traversal of *t. LinkedQueueBinaryTreeNode* Q; while (t) Visit(t); / visit t 75计算机与控制工程学院逐层遍历（宽度优先）逐层遍历（宽度优先） / put ts children on queue if (t-LeftChild) Q.Add(t-LeftChild); if (t-RightChild

37、) Q.Add(t-RightChild); / get next node to visit try Q.Delete(t); catch (OutOfBounds) return; 出队次序即是遍历次序；同时控制t移向下一节点。76计算机与控制工程学院由遍历顺序推导二叉树结构由遍历顺序推导二叉树结构 一棵二叉树一棵二叉树先序遍历结果先序遍历结果1, 2, 4, 7, 3, 5, 6, 8, 91, 2, 4, 7, 3, 5, 6, 8, 9中序遍历结果中序遍历结果4, 7, 2, 1, 5, 3, 8, 6, 94, 7, 2, 1, 5, 3, 8, 6, 9能推导出其结构吗？能推导出

38、其结构吗？ 可以！可以！77计算机与控制工程学院第一步第一步1, 2, 4, 7, 3, 5, 6, 8, 91, 2, 4, 7, 3, 5, 6, 8, 94, 7, 2, 1, 5, 3, 8, 6, 94, 7, 2, 1, 5, 3, 8, 6, 9 先序遍历先序遍历根左子树右子树根左子树右子树“1”1”必为根节点必为根节点 中序遍历中序遍历左子树根右子树，且左子树根右子树，且1 1为根节点为根节点4, 7, 24, 7, 2为左子树，为左子树，5, 3, 8, 6, 95, 3, 8, 6, 9为右子树为右子树78计算机与控制工程学院下面怎么办？递归！下面怎么办？递归！ 左子树左子

39、树先序遍历先序遍历2, 4, 72, 4, 7中序遍历中序遍历4, 7, 24, 7, 2 右子树右子树先序遍历先序遍历3, 5, 6, 8, 93, 5, 6, 8, 9中序为中序为5, 3, 8, 6, 95, 3, 8, 6, 9 利用相同方法构造左、右子树，直至列表长度利用相同方法构造左、右子树，直至列表长度为为00空子树，无需构造空子树，无需构造79计算机与控制工程学院遍历顺序遍历顺序二叉树结构（续）二叉树结构（续）80计算机与控制工程学院遍历顺序遍历顺序二叉树结构（续）二叉树结构（续）先序3, 5, 6, 8, 9，中序5, 3, 8, 6, 981计算机与控制工程学院遍历顺序遍历

40、顺序二叉树结构（续）二叉树结构（续）先序6, 8, 9中序8, 6, 982计算机与控制工程学院抽象数据类型及类的扩充抽象数据类型及类的扩充 增加如下二叉树操作：增加如下二叉树操作：PreOutputPreOutput()()：按前序方式输出数据域：按前序方式输出数据域InOutputInOutput()()：按中序方式输出数据域：按中序方式输出数据域PostOutputPostOutput()()：按后序方式输出数据域：按后序方式输出数据域LevelOutputLevelOutput()()：逐层输出数据域：逐层输出数据域DeleteDelete()()：删除一棵二叉树，释放其节点：删除一棵

41、二叉树，释放其节点HeightHeight()()：返回树的高度：返回树的高度SizeSize()()：返回树中节点数：返回树中节点数83计算机与控制工程学院销毁二叉树销毁二叉树 删除所有节点删除所有节点 后序遍历后序遍历：删除左子树、删除右子树、删除：删除左子树、删除右子树、删除根根 辅助函数辅助函数删除单个节点删除单个节点 static void Free(BinaryTreeNode *t) delete t; 删除二叉树删除二叉树void Delete() PostOrder(Free, root); root = 0;84计算机与控制工程学院计算高度计算高度 后序遍历后序遍历 左子树

42、高度、右子树高度较大者左子树高度、右子树高度较大者+1+1（根节点）（根节点）树的高度树的高度 递归公式：递归公式：h=maxhl, hr + 1h=maxhl, hr + 1递归函数递归函数 公共接口公共接口int Height() const return Height(root);85计算机与控制工程学院计算高度的递归函数计算高度的递归函数HeightHeighttemplate 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;86计算机与控制工程学院统