3、二又的应用拳例 众 (色盲) 变色力缺陷遗传图 (隔代遗传) 国际 MOrse码
3、二叉树的应用举例 男 （色盲） 女 女 男 女 男 男 • ─ E T I A N M S U R W D K G O H V F L P J B X C Y Z Q • • • • • • • • • • • ─ • ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ 国际Morse码 变色力缺陷遗传图 （隔代遗传）
Init BiTree (&T) Destroy BiTree(&T) Create BiTree ( &T, definition) Clear BiTree(&T); BiTreeEmpty (T); 只树的本操 入 BiTreeDepth (T) Parent(T, e) 除 LeftChild(T,e); RightChild(T, e); Leftsibling(T, e); Right T, e); InsertChild(T, p, LR, c); Delete Child(T, p, LR) PreOrder Traverse(T, VisitO) InOrderTraverse(T, visitO PostorderTraverse(T, VisitO) LevelOrderTraverse(T, Visit(
InitBiTree(&T); DestroyBiTree(&T); CreateBiTree(&T, definition); ClearBiTree(&T); BiTreeEmpty(T); BiTreeDepth(T); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); InsertChild(T, p, LR, c); DeleteChild(T, p, LR); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit()); 二叉树的基本操作 查 找 类 插 入 类 删 除 类
、二况的性 l层与点数 3、深度与点 3、叫子与结点意 4完盒二又树与深度 5、嘉金二卫与结点号水
二、二叉树的基本性质 1、层与结点数 2、深度与结点数 3、叶子与结点数 4、完全二叉树与深度 5、完全二叉树与结点序号
已制的啥 讨论1:第层的结点数至多是多少? (利用二进制性质可轻松求出) 1.一棵非空二叉树的第i层最多有2-1个结点(i≥1)。 证明(采用归纳法) (1)当i=1时结论显然正确。非空二叉树的第1层有且仅有一个 结点即树的根结点 (2)假设对于第层(1i1)结论也正确即第层最多有个结 点 (3)有定义可知,二叉树中每个结点最多只能有两个孩子结点。 若第i-1层的每个结点都有两棵非空子树则第层的结点数目 达到最大而第层最多有22个结点已由假设证明于是应 有 2×2i2=2i1 证毕 提问:第层上至少有个结点?
1.一棵非空二叉树的第i 层最多有2 i–1个结点(i1)。 证明(采用归纳法) (1).当i=1时,结论显然正确。非空二叉树的第1层有且仅有一个 结点,即树的根结点. (2).假设对于第j层(1ji–1)结论也正确,即第j层最多有2 j-1个结 点. (3).有定义可知, 二叉树中每个结点最多只能有两个孩子结点。 若第i–1层的每个结点都有两棵非空子树,则第i层的结点数目 达到最大. 而第i–1层最多有2 i–2个结点已由假设证明,于是,应 有22 i–2 = 2i–1 证毕. 二叉树的性质 讨论1：第i层的结点数至多是多少？ （利用二进制性质可轻松求出） 提问：第i层上至少有 个结点？
三灵的验■ 讨论2:深度为k的二叉树,至多有多少个结点? (利用二进制性质可轻松求出) 2深度为h的非空二叉树最多有21个结点 证明: 由性质1可知若深度为h的二又树的每一层的结点数目都 达到各自所在层的最大值则二叉树的结点总数一定达到最大 即有 20+21+22++2i1+2h-1=2h-1 证毕 提问:深度为k时至少有个结点?
2.深度为h 的非空二叉树最多有2 h -1个结点. 证明: 由性质1可知,若深度为h的二叉树的每一层的结点数目都 达到各自所在层的最大值,则二叉树的结点总数一定达到最大。 即有 2 0+21+22+…+2i-1+ …+2h-1 = 2h -1 证毕. 二叉树的性质 讨论2：深度为k的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出） 提问：深度为k时至少有 个结点？