數(shù)據(jù)結構與算法分析lecture6(二叉樹)(編輯修改稿)
2024-11-15 19:46 本頁面
【文章內容簡介】 中序遍歷 posterorder traversal 后序遍歷 前序遍歷 (D L R): 訪問根結點，按前序遍歷左子樹，按前序遍歷右子樹。 A B D C E G F H I 中序遍歷 (L D R): 按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。 B D A G E C H F I 后序遍歷 (L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。 二叉樹為空時 ， 執(zhí)行空操作 ， 即空二叉樹已遍歷完 。 D B G E H I F C A A C H M B E L K D （ 2） 遍歷算法 先序遍歷： D L R 中序遍歷： L D R 后序遍歷： L R D A D B C T1 T2 T3 D L R A D L R D L R B D C D L R 以先序遍歷 D L R為例演示遍歷過程 ABDC BDAC DBCA templateclass Elem void PreOder (BinNodeElem* subroot){ if(subroot ==NULL) return。 visit(subroot)。 PreOrder (subrootleft())。 PreOrder (subrootright())。 }/*前序遍歷 */ 主程序 Pre( T ) 返回 返回 pre(S R)。 返回 返回 pre(S R)。 A C B D S B visit(B)。 pre(S L)。 S A visit(A)。 pre(S L)。 S D visit(D)。 pre(S L)。 S C visit(C)。 pre(S L)。 返回 S 左是空返回 pre(S R)。 S 左是空返回 S 右是空返回 S 左是空返回 S 右是空返回 pre(S R)。 templateclass Elem void PreOder (BinNodeElem* subroot){ if(subroot ==NULL) return。 visit(subroot)。 PreOrder (subrootleft())。 PreOrder (subrootright())。 }/*前序遍歷 */ templateclass Elem void PreOder (BinNodeElem* subroot){ if(subroot ==NULL) return。 visit(subroot)。 PreOrder (subrootleft())。 PreOrder (subrootright())。 }/*前序遍歷 */ ? 中序遍歷二叉樹的遞歸算法： templateclass Elem void InOder (BinNodeElem* subroot){ if(subroot ==NULL) return。 InOrder (subrootleft())。 visit(subroot)。 InOrder (subrootright())。 } }/*中序遍歷 */ 后序遍歷二叉樹
教學課件相關推薦
鄂ICP備17016276號-1