求树中某个指定结点的最左子结点,当指定结点为 树叶时返回特殊值 Tree leftChild( Tree t) 求树中某个指定结点的右兄弟结点,当指定结点没 有右兄弟时返回特殊值 Tree rightSibling( Tree t, Tree child) 树的周游:按某种系统方式访问树中的所有结点, 每个结点恰好访问一次。 下一顶
返回本章首页 下一页 上一页 • 求树中某个指定结点的最左子结点，当指定结点为 树叶时返回特殊值 Tree leftChild ( Tree t ) • 求树中某个指定结点的右兄弟结点，当指定结点没 有右兄弟时返回特殊值 Tree rightSibling ( Tree t, Tree child ) • 树的周游：按某种系统方式访问树中的所有结点， 每个结点恰好访问一次
8.1.5树的周游 1.周游:按某种规律系 统地访问树中所有结 点,每个结点恰好访 问一次的过程。 出: 2.周游方法:按深度周 游和按宽度周游。 (按深度(以图为例) a.先根序 1)访问根结点; 2)从左到右按先根次序周游根结点的每棵子对 道 1,2,3,5,8,9,6,10,4,7
返回本章首页 下一页 上一页 8.1.5 树的周游 1. 周游：按某种规律系 统地访问树中所有结 点，每个结点恰好访 问一次的过程。 2. 周游方法：按深度周 游和按宽度周游。 (I) 按深度（以图为例） a. 先根序 1）访问根结点； 2）从左到右按先根次序周游根结点的每棵子树 1, 2, 3, 5, 8, 9, 6, 10, 4, 7
b中根序 1)按中根次序周游根结点 的最左子树 2)访问根结点; 3)从左到右按中根次序周 游根结点的其它各子树。 产7 2,1,8,5,9,3,10,6,7,4 出号 c.后根序 1)从左到右按后根次序周游 根结点的每棵子树; 2)访问根结点。 下一顶 2895、10.63.74,1
返回本章首页 下一页 上一页 b. 中根序 1）按中根次序周游根结点 的最左子树； 2）访问根结点； 3）从左到右按中根次序周 游根结点的其它各子树。 2,1,8,5,9,3,10,6,7,4 c. 后根序 1）从左到右按后根次序周游 根结点的每棵子树; 2）访问根结点。 2,8,9,5,10,6,3,7,4,1
(Ⅱ)按宽度(层次)周游 先访问层数为0的结点,然后 从左到右逐个访问层数为1的 结点,依此类推,直到访问 完树中全部结点。 2,3,4,5,6,7,8,9,10 号连 下一顶
返回本章首页 下一页 上一页 （II）按宽度（层次）周游 先访问层数为0的结点，然后 从左到右逐个访问层数为1的 结点，依此类推，直到访问 完树中全部结点。 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
先根序周游的非递归算法 void preOrder( Tree t)i Tree c=left Child(t); visit ( root( t)); while(! Null(c))i preorder(c); c=rightSibling(t, c); 下一顶
返回本章首页 下一页 上一页 先根序周游的非递归算法 void preOrder( Tree t ) { Tree c = leftChild ( t ); visit ( root( t ) ); while ( !Null ( c ) ) { preOrder ( c ); c = rightSibling ( t, c ); } }