第6章树与二叉树

第6章树与二叉树内容摘要：

；否则其左孩子 LCHILD(i)是节点 2i。 ③ 如果 2i+1n，则节点 i无右孩子；否则其右孩子 RCHILD(i) 是节点 2i+1。 二叉树的存储结构 • 顺序存储 以节点在向量中的相对位置来表示节点间的关系。 不足：一般的二叉树也必须按完全二叉树的形式来存储，势必会造成存储的浪费。 53214( a ) 二叉树T∧22∧1 14 ∧∧5 ∧345∧3 ∧ ∧214 ∧∧5 ∧∧3 ∧∧( b ) 二叉树T 的单指针存储 ( c ) 二叉树T 的双指针存储 ( d ) 二叉树T 的三指针存储图6 . 6 二叉树链式存储结构示例root root root• 链式存储 单叉链表 三叉链表 二叉链表 常用链式存储结构：二叉链表 二叉树操作的实现 • 遍历（周游）算法 深度优先遍历： 先序遍历：若二叉树为空 ， 则空操作；否则 (1)访问根节点； (2)先序遍历左子树； (3)先序遍历右子树。 中序遍历：若二叉树为空 ， 则空操作；否则 (1)中序遍历左子树； (2)访问根节点； (3)中序遍历右子树。 后序遍历：若二叉树为空 ， 则空操作；否则 (1)后序遍历左子树； (2)后序遍历右子树； (3)访问根节点。 二叉树遍历的典型应用－－表达式树 cba*cba*cba*cba*(a)a*(bc)的 表达式树T ( b ) 先序遍历表达式树T ( c ) 中序遍历表达式树T ( d ) 后序遍历表达式树T图6 . 7 表达式树与三种遍历 先序遍历此二叉树 ， 得到的二叉树的先序序列为： *abc； 中序遍历此二叉树 ， 得到该二叉树的中序序列为： a*bc； 后序遍历此二叉树，得到该二叉树的后序序列为： abc*； 前缀表示（波兰式） 后缀表示（逆波兰式） 中缀表示（中缀式） 非递归实现树的深度优先遍历 利用栈 非递归实现树的广度优先遍历 利用队列 •遍历算法 时间 复杂度： O(N) •遍历算法 空间 复杂度：至多为 O(N) 树和森林 • 树的存储结构 三种典型的表示法： 第一种是 双亲表示法。 第二种是孩子表示法。 第三种是孩子兄弟表示法。 RL M NP QWR 1L 0M 0N 0P 1Q 1W 30654321数组下标数据域 父节点域( a ) 树的逻辑结构 ( b ) 树的双亲表示法示例data c 1 c Dc 2 „degree c 1 c dc 2 „dataRLM ∧NP ∧Q ∧W ∧∧∧∧∧∧∧∧∧∧∧∧32010 00RLMNP QWrootroot节点的结构节点的结构( c ) 树的一种孩子表示法示例( d ) 树的另一种孩子表示法示例RLM ∧NP ∧Q ∧W ∧0654321数据域 子节点域L M N ∧P Q ∧W ∧RLM ∧NP ∧Q ∧W ∧0654321数据域 子节点域L M N ∧P Q ∧W ∧1000113父节点域( e ) 树的孩子链表 ( e ) 树的带双亲的孩子链表 树的双 亲表示法与孩子表示法R ∧LP∧ M∧N ∧Q ∧∧W ∧∧data nextSiblingfirstChild节点的数据域节点的下一个兄弟域节点的第一个孩子域( a ) 树节点的存储。