第五章 树与二叉树(二).ppt

* 4、子女指针表示 一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理。 为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（degree）。 这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费。 * 等数量的链域 A B C D E F G data child1 child2 child3 childd A B C D E F G ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 空链域2n+1个 * 5、子女-兄弟表示 也称为树的二叉树表示。结点构造为： firstChild 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。 nextSibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。 若想找某结点的所有子女，可先找firstChild,再反复用 nextSibling 沿链扫描。 data firstChild nextSibling * 树的子女 - 兄弟表示 data firstChild nextSibling A B C D E F G A B C D G F E * 树的二叉树表示 树的遍历 深度优先遍历 先根次序遍历 后根次序遍历 广度优先遍历 A B C E D A B C D E F G G F * A B C E D G F 树的先根次序遍历 当树非空时 访问根结点 依次先根遍历根的各棵 子树 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现 * A B C E D G F 树的后根次序遍历 当树非空时 依次后根遍历根的各棵 子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现 * 树的先根次序遍历的递归算法 template class T void TreeT:: PreOrder ( void (*visit) (BinTreeNodeT *t) ) { //以当前指针current为根, 先根次序遍历 if (!IsEmpty ()) { //树非空 visit (current); //访问根结点 TreeNodeT *p = current; //暂存当前指针 current = current-firstChild; //第一棵子树 while (current != NULL) { PreOrder (visit); //递归先根遍历子树 current = current-nextSibling; * } current = p; //恢复当前指针 } }; template class T void TreeT :: PostOrder (void (*visit) (BinTreeNodeT *t)) { //以当前指针current为根, 按后根次序遍历树 树的后根次序遍历的递归算法 * if ( ! IsEmpty () ) { //树非空 TreeNodeT *p = current; //保存当前指针 current = current-firstChild; //第一棵子树 while (current != NULL) { //逐棵子树 PostOrder (visit); current = current-nextSibling; } current = p; //恢复当前指针 visit (current); //访问根结点 } }; * 广度优先（层次次序）遍历 按广度优先次序遍历树的结果 ABCDEFG 遍历算法用到一个队列。 template c