第8章 二叉树和其他树

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

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

3、ueSue，JohnJohn，ChrisChris n=7n=7，根为，根为JoeJoe 信息技术科学学院 家庭关系例树的描述（续）家庭关系例树的描述（续） 余下的元素余下的元素 AnnAnn单一元素子树单一元素子树 MaryMary，MarkMark，SueSue，根为，根为MaryMary的子树的子树 MarkMark和和SueSue，均为单元素的子树，均为单元素的子树 JohnJohn，ChrisChris，根为，根为JohnJohn的子树的子树 Chris Chris 也为单元素子树也为单元素子树 信息技术科学学院 相关术语相关术语 元素元素节点节点 根节点与子树的根节点的关系根节点与

4、子树的根节点的关系边边 边的两端边的两端父母父母（parentparent）和）和孩子孩子 （childrenchildren） 信息技术科学学院 相关术语（续）相关术语（续） 相同父母的节点相同父母的节点兄弟兄弟（siblingsibling） 祖父祖父孙子孙子，祖先祖先后代后代 叶叶节点节点没有孩子的节点，非叶节点没有孩子的节点，非叶节点非非 终端节点终端节点 信息技术科学学院 相关术语（续）相关术语（续） 根根没有父节点的节点没有父节点的节点 层层（levellevel）：根）：根11，根的孩子，根的孩子22，. 节点的节点的度度（degreedegree）：孩子数目，叶）：孩子数目，叶

5、00 信息技术科学学院 例例8-68-6 公司机构例公司机构例 公司雇员公司雇员节点，总裁节点，总裁根根 副总裁副总裁总裁的子节点，总裁总裁的子节点，总裁副总裁的父节点副总裁的父节点 不同副总裁不同副总裁兄弟节点兄弟节点 信息技术科学学院 例例8-6 8-6 （续）（续） 政府机构例政府机构例 联邦政府联邦政府国防部，教育部，国防部，教育部，.，税务部的父节点，税务部的父节点 国防部的子节点国防部的子节点陆军、海军、空军、海军陆战陆军、海军、空军、海军陆战 队队兄弟节点，叶节点兄弟节点，叶节点 信息技术科学学院 树的相关概念树的相关概念 树、子树树、子树 根、分支节点、叶子节点根、分支节点、叶

6、子节点 父节点、孩子节点、兄弟节点父节点、孩子节点、兄弟节点 祖父、孙子、祖先、后代祖父、孙子、祖先、后代 边边 级、深度、高度级、深度、高度 度度 19 信息技术科学学院 自由树自由树 信息技术科学学院 有根树有根树 信息技术科学学院 有序树有序树 信息技术科学学院 森林和有序森林森林和有序森林 森林森林（forestforest）：）：树的集合，通常认为是有树的集合，通常认为是有 根树的集合根树的集合 有序森林有序森林（orchardorchard，ordered forestordered forest）：）： 有序树的有序集合有序树的有序集合 有根（有序）树去掉根节点有根（有序）树去掉

7、根节点（有序）森林（有序）森林 （有序）森林添加父节点（有序）森林添加父节点有根（有序）树有根（有序）树 信息技术科学学院 森林和有序森林（续）森林和有序森林（续） 信息技术科学学院 有根树的递归定义有根树的递归定义 有根树有根树： 包含单一顶点包含单一顶点v v，称为树的，称为树的根根， 和一个森林和一个森林F F，F F的树称为的树称为根的子树根的子树 而而森林森林F F（可为空）是一个有根树的集合（可为空）是一个有根树的集合 信息技术科学学院 有序树的定义有序树的定义 一个一个有序树有序树T T： 包含一个单一节点包含一个单一节点v v，称为树的，称为树的根根， 和一个和一个有序森林有序

8、森林O O，O O的树称为的树称为v v的子树，表示为的子树，表示为 T=v, OT=v, O 信息技术科学学院 有序森林的定义有序森林的定义 一个一个有序森林有序森林O O： 或者为空集或者为空集， 或包含一个有序树或包含一个有序树T T，称为有序森林的，称为有序森林的第一树第一树， 和另一个有序森林和另一个有序森林OO（包含有序森林的其它（包含有序森林的其它 树），可表示为树），可表示为O=T, OO=T, O 有序树有序森林：间接递归定义有序树有序森林：间接递归定义 信息技术科学学院 有序森林有序森林 信息技术科学学院 课堂练习课堂练习 一棵有一棵有n n个结点的树的所有结点的度数之和个

9、结点的树的所有结点的度数之和 是多少？是多少？ 在树中某一结点的深度是在树中某一结点的深度是3 3，高度是，高度是4 4，该树，该树 的高度至少为几？的高度至少为几？ 29 信息技术科学学院 课堂练习课堂练习 如果一棵树有如果一棵树有n n1 1个度为个度为1 1的节点，有的节点，有n n2 2个度为个度为 2 2的节点，的节点，n nm m个度为个度为m m的节点，试问有的节点，试问有 多少个度为多少个度为0 0的节点？的节点？ 30 11 1 0 m i i nin 信息技术科学学院 主要内容主要内容 树的一般定义树的一般定义 二叉树的定义和操作二叉树的定义和操作 二叉树的遍历二叉树的遍历

10、 31 信息技术科学学院 二叉树二叉树 定义定义： 二叉树二叉树（binary treebinary tree）t t是有限元素集合：是有限元素集合： 或者为空；或者为空； 或者，有一个特殊元素或者，有一个特殊元素根根，余下的元素构成，余下的元素构成2 2个个 二叉树（可以为空）二叉树（可以为空）tt的的左子树左子树和和右子树右子树 信息技术科学学院 二叉树和树的根本区别二叉树和树的根本区别 二叉树可以为空二叉树可以为空 树不行树不行 二叉树每个节点都恰好有两棵子树（可以为空）二叉树每个节点都恰好有两棵子树（可以为空） 树中每个节点可有若干子树树中每个节点可有若干子树 二叉树每个节点的子树是有

11、序的二叉树每个节点的子树是有序的“左左”、 “右右” 树的子树间是无序的树的子树间是无序的 信息技术科学学院 二叉树例二叉树例递归构造递归构造 空二叉树空二叉树递归的停止递归的停止 单一节点二叉树单一节点二叉树 两个节点：两个节点： 不同！不能表示为不同！不能表示为 信息技术科学学院 二叉树例二叉树例递归构造（续）递归构造（续） 三个节点三个节点 根左子树根左子树(2)(2)右子树右子树(0)(0)、1 11 1、0 02 2 类似方式，可构造更大的二叉树类似方式，可构造更大的二叉树 信息技术科学学院 二叉树例：表达式树二叉树例：表达式树 a)a)a a* *b + c/db + c/d b)

12、b)a+b+c+da+b+c+d c)c)(-a+(x+y)/(+b(-a+(x+y)/(+b* *(c(c* *a)a) 信息技术科学学院 二叉树的特性二叉树的特性 特性特性1 1 包含包含n n ( (n n0)0)个节点的二叉树边数为个节点的二叉树边数为 n n-1-1 证明证明 二叉树中每个节点（除根节点，共二叉树中每个节点（除根节点，共n-1n-1个节个节 点）点） 有且只有一个父节点有且只有一个父节点 每个子节点与父节点间有且只有一条边每个子节点与父节点间有且只有一条边 边数为边数为n n-1-1 信息技术科学学院 特性特性2 2 二叉树的二叉树的高度高度（heightheight

13、）（）（深度深度，depthdepth）：）： 二叉树的层数二叉树的层数 特性特性2 2 若二叉树的高度为若二叉树的高度为h h，h h00，则它最，则它最 少有少有h h个节点，最多有个节点，最多有2 2h h-1-1个节点个节点 信息技术科学学院 特性特性2 2的证明的证明 证明证明 每层最少要有每层最少要有1 1个节点个节点节点数最少为节点数最少为h h 每个节点最多有每个节点最多有2 2个子节点个子节点则第则第i i层节点最层节点最 多为多为2 2i i-1 -1个， 个，i i11 节点的总数不会超过节点的总数不会超过 122222 110 1 1 hh h i i 信息技术科学学院

14、 特性特性2 2说明说明 深度深度该层最多节点数该层最多节点数二叉树的最多节点总数二叉树的最多节点总数 120=11 221=23 322=47 423=815 524=1631 625=3263 40 信息技术科学学院 特性特性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是

15、整数是整数 ) 1(log2n ) 1(log2nh 信息技术科学学院 满二叉树（满二叉树（full binary tree full binary tree ） 高度为高度为h h，节点数，节点数2 2h h-1-1 信息技术科学学院 完全二叉树完全二叉树 高度为高度为h h 的满二叉树中节点按从上到下，从的满二叉树中节点按从上到下，从 左到右的顺序从左到右的顺序从1 1到到2 2h h-1-1进行编号进行编号 从中删除从中删除k k个节点，编号为个节点，编号为2 2h h- -i i, 1, 1i ik k 即为即为完全二叉树，深度为完全二叉树，深度为 ) 1(log2n 信息技术科学学院

16、 另一种定义方法另一种定义方法 设二叉树设二叉树T T有有n n个节点，令个节点，令 则则k k代表最下一层，也就是二叉树的深度，代表最下一层，也就是二叉树的深度，r r代代 表第表第k k层的节点数，其中层的节点数，其中2 2k-1 k-1个节点放满第 个节点放满第1 1到到 第第k-1k-1层，则：层，则： 若若0r=20r 1 1， 则该元素父节点的编号为则该元素父节点的编号为 2)2) 当当2 2i i n n时，该元素无左孩子。否则，其左孩时，该元素无左孩子。否则，其左孩 子的编号为子的编号为2 2i i 3)3) 若若2 2i i + 1+ 1n n，该元素无右孩子。否则，其右，该

17、元素无右孩子。否则，其右 孩子编号为孩子编号为2 2i i + 1+ 1 2/ i 信息技术科学学院 特性特性4 4（续）（续） 证明证明 通过对通过对i i 进行归纳即可得证进行归纳即可得证 信息技术科学学院 特性特性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的节点各有

18、多的节点各有多 少？少？ 47 11 1 0 m i i nin 信息技术科学学院 思考思考 有有m m个叶子的个叶子的二叉树二叉树最多有多少个节点？最多有多少个节点？ 有有m m个叶子的个叶子的完全二叉树完全二叉树最多有多少个节点？最多有多少个节点？ 48 信息技术科学学院 课堂练习课堂练习 设高度为设高度为h h的二叉树中只有度为的二叉树中只有度为0 0和度为和度为2 2的的 节点，则此类二叉树所包含的节点数至少为节点，则此类二叉树所包含的节点数至少为 _，至多为，至多为_。 49 信息技术科学学院 课堂练习课堂练习 设完全二叉树的第设完全二叉树的第6 6层有层有2424个叶节点，则此个叶

19、节点，则此 树最多有树最多有_个节点个节点 A. 55A. 55 B. 79B. 79 C. 81C. 81 D. 127D. 127 50 信息技术科学学院 二叉树描述二叉树描述 公式化描述公式化描述利用特性利用特性4 4 普通二叉树普通二叉树缺少部分节点的完全二叉树缺少部分节点的完全二叉树 信息技术科学学院 公式化描述公式化描述 数组位置数组位置节点编号节点编号 父子节点关系父子节点关系特性特性4 4 信息技术科学学院 公式化描述公式化描述 n n层二叉树层二叉树22n n-1-1数组保存，可能空间浪费！数组保存，可能空间浪费！ 信息技术科学学院 链表描述链表描述 树节点树节点节点类对象节

20、点类对象 数据域、数据域、LeftChildLeftChild、RightChildRightChild n-1n-1条边条边2n-(n-1)=n+12n-(n-1)=n+1个空指针个空指针 信息技术科学学院 BinaryTreeNodeBinaryTreeNode类类 template class BinaryTreeNode public: BinaryTreeNode() LeftChild = RightChild = 0; BinaryTreeNode(const T LeftChild = RightChild = 0; BinaryTreeNode(const T LeftChi

21、ld = l; RightChild = r; private: T data; BinaryTreeNode *LeftChild, / left subtree *RightChild; / right subtree ; 信息技术科学学院 抽象数据类型抽象数据类型BinaryTreeBinaryTree 抽象数据类型抽象数据类型BinaryTreeBinaryTree 实例实例 元素集合；如果不空，则被划分为根节点、左子树和右子树；元素集合；如果不空，则被划分为根节点、左子树和右子树； 每个子树仍是一个二叉树每个子树仍是一个二叉树 操作操作 CreateCreate()()：创建一个空的

22、二叉树；：创建一个空的二叉树； IsEmptyIsEmpty：如果二叉树为空，则返回：如果二叉树为空，则返回truetrue，否则返回，否则返回falsefalse RootRoot( (x x) )：取：取x x为根节点；如果操作失败，则返为根节点；如果操作失败，则返 回回falsefalse，否则返回，否则返回truetrue 信息技术科学学院 抽象数据类型（续）抽象数据类型（续） MakeTreeMakeTree( (rootroot，leftleft，rightright) )：创建一个二叉树，：创建一个二叉树，rootroot作为作为 根节点，根节点，leftleft作为左子树，作为

23、左子树，rightright作作为右子树为右子树 BreakTreeBreakTree( (rootroot，leftleft，rightright) )：拆分二叉树：拆分二叉树 PreOrderPreOrder：先序遍历：先序遍历 InOrderInOrder：中序遍历：中序遍历 PostOrderPostOrder：后序遍历：后序遍历 LevelOrderLevelOrder：逐层遍历：逐层遍历 信息技术科学学院 类类BinaryTreeBinaryTree template class BinaryTree public: BinaryTree() root = 0; BinaryTre

24、e(); bool IsEmpty() const return (root) ? false : true); bool Root(T void MakeTree(const T void BreakTree(T void PreOrder(void(*Visit)(BinaryTreeNode *u) PreOrder(Visit, root); 信息技术科学学院 类类BinaryTreeBinaryTree（续）（续） void InOrder(void(*Visit)(BinaryTreeNode *u) InOrder(Visit, root); void PostOrder(voi

25、d(*Visit)(BinaryTreeNode *u) 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

26、(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); ; 信息技术科学学院 获取根节点数据获取根节点数据 template bool BinaryTree:Root(T return true; else return false; / no root 信息技术科学学院 创建树创建树 template void BinaryTree:MakeTree(const T / deny access from trees left and right left.root = right.root = 0; 缺陷：允许MakeTree(e, X,

27、 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; 信息技术科学学院 思考思考 在上述存储方式下，寻找某一节点孩子的复在上述存储方式下，寻找某一节点孩子的复 杂度是杂度是O(1)O(1)，寻找其父亲的复杂度是，寻找其父亲的复杂度是O(n)O(n)， 为什么？为什

28、么？ 如果希望将寻找父节点的效率提高到如果希望将寻找父节点的效率提高到O(1)O(1)， 如何做？如何做？ 63 信息技术科学学院 主要内容主要内容 树的一般定义树的一般定义 二叉树的定义和操作二叉树的定义和操作 二叉树的遍历二叉树的遍历 64 信息技术科学学院 二叉树遍历二叉树遍历 按照某种顺序访问树中的每个节点，按照某种顺序访问树中的每个节点， 要求每个节点被访问一次且仅被访问一次要求每个节点被访问一次且仅被访问一次 这就是这就是二叉树遍历问题二叉树遍历问题 信息技术科学学院 二叉树遍历二叉树遍历 遍历顺序遍历顺序【关键关键】 访问根节点、左子树、右子树的顺序访问根节点、左子树、右子树的顺

29、序 左右子树的访问（遍历）？左右子树的访问（遍历）？递归！递归！ 可能的遍历顺序可能的遍历顺序 V V根，根，L L左子树，左子树，R R右子树右子树 VLR LVR LRV VRL RVL RLVVLR LVR LRV VRL RVL RLV 信息技术科学学院 标准遍历顺序标准遍历顺序 都是左子树先于右子树，关键都是左子树先于右子树，关键根的访问次根的访问次 序序 先序遍历（先序遍历（preorderpreorder）VLRVLR 中序遍历（中序遍历（inorderinorder）LVRLVR 后序遍历（后序遍历（postorderpostorder）LRVLRV V LR 信息技术科学学院

30、 先序遍历先序遍历 template void PreOrder(BinaryTreeNode *t) / Preorder traversal of *t. 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(

31、t-LeftChild); / do left subtree Visit(t); / visit tree root InOrder(t-RightChild); / do right 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); / vis

32、it 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需加括号 信息技术科学学院 后序遍历表达式树后序遍历表达式树 a)ab*cd/+ b)ab+c+d+ c)a-xy+b+ca*/ m后缀表达式 计算机计算非常 方便 信息技术科学学院 输出完全括号化的中缀表达式输出完全括号化的中缀表达式 template void Infix(Bina

33、ryTreeNode *t) / Output infix form of expression. if (t) cout LeftChild); / left operand cout data; / operator Infix(t-RightChild); / right operand cout ); 信息技术科学学院 逐层遍历（宽度优先）逐层遍历（宽度优先） 根根叶逐层，同层由左至右叶逐层，同层由左至右 template void LevelOrder(BinaryTreeNode *t) / Level-order traversal of *t. LinkedQueueBinar

34、yTreeNode* 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; 出队次序即是遍历次序； 同时控制t移向下一节点。 信息技术科学学院 由遍历顺序推导二叉树结构由遍历顺序推导

35、二叉树结构 一棵二叉树一棵二叉树 先序遍历结果先序遍历结果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 能推导出其结构吗？能推导出其结构吗？ 可以！可以！ 信息技术科学学院 第一步第一步 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 先序遍历先序遍历 根左子树

36、右子树根左子树右子树“1”1”必为根节点必为根节点 中序遍历中序遍历 左子树根右子树，且左子树根右子树，且1 1为根节点为根节点 4, 7, 24, 7, 2为左子树，为左子树，5, 3, 8, 6, 95, 3, 8, 6, 9为右子树为右子树 信息技术科学学院 下面怎么办？递归！下面怎么办？递归！ 左子树左子树 先序遍历先序遍历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 利用相同方法构造左、右子树，直至列表长度

37、利用相同方法构造左、右子树，直至列表长度 为为00空子树，无需构造空子树，无需构造 信息技术科学学院 遍历顺序遍历顺序二叉树结构（续）二叉树结构（续） 信息技术科学学院 遍历顺序遍历顺序二叉树结构（续）二叉树结构（续） 先序3, 5, 6, 8, 9，中序 5, 3, 8, 6, 9 信息技术科学学院 遍历顺序遍历顺序二叉树结构（续）二叉树结构（续） 先序6, 8, 9 中序8, 6, 9 信息技术科学学院 抽象数据类型及类的扩充抽象数据类型及类的扩充 增加如下二叉树操作：增加如下二叉树操作： PreOutputPreOutput()()：按前序方式输出数据域：按前序方式输出数据域 InOut

38、putInOutput()()：按中序方式输出数据域：按中序方式输出数据域 PostOutputPostOutput()()：按后序方式输出数据域：按后序方式输出数据域 LevelOutputLevelOutput()()：逐层输出数据域：逐层输出数据域 DeleteDelete()()：删除一棵二叉树，释放其节点：删除一棵二叉树，释放其节点 HeightHeight()()：返回树的高度：返回树的高度 SizeSize()()：返回树中节点数：返回树中节点数 信息技术科学学院 销毁二叉树销毁二叉树 删除所有节点删除所有节点 后序遍历后序遍历：删除左子树、删除右子树、删除：删除左子树、删除右子

39、树、删除 根根 辅助函数辅助函数删除单个节点删除单个节点 static void Free(BinaryTreeNode *t) delete t; 删除二叉树删除二叉树 void Delete() PostOrder(Free, root); root = 0; 信息技术科学学院 计算高度计算高度 后序遍历后序遍历 左子树高度、右子树高度较大者左子树高度、右子树高度较大者+1+1（根节点）（根节点） 树的高度树的高度 递归公式：递归公式：h=maxhl, hr + 1h=maxhl, hr + 1递归函数递归函数 公共接口公共接口 int Height() const return Heig

40、ht(root); 信息技术科学学院 计算高度的递归函数计算高度的递归函数HeightHeight template 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; 信息技术科学学院 统计节点数目统计节点数目 任意一种遍历方法任意一种遍历方法，每个节点将统计计数加，每个节点将统计计数加1 1 私有辅助函数私有辅助函数Add1Add1 static void Add1(BinaryTreeNode *t) _count+; 节点数统计