數(shù)據(jù)結(jié)構(gòu)-二叉樹的存儲結(jié)構(gòu)和遍歷(存儲版)
【正文】 B H K G F E A 三種遍歷的比較 復制二叉樹 建立二叉樹 查詢二叉樹中某個結(jié)點 應(yīng)用舉例 統(tǒng)計二叉樹中結(jié)點的個數(shù) 遍歷訪問了每個結(jié)點一次且僅一次 設(shè)置一個全局變量 count=0 統(tǒng)計二叉樹中結(jié)點的個數(shù) 將 visit改為 :count++ 統(tǒng)計二叉樹中結(jié)點的個數(shù) void PreOrder (BiTree T){ } if (! T ) return。 // 遍歷右子樹 } 后序（根）遍歷 左 子樹 右 子樹 根 根左 子樹 右 子樹 若二叉樹為空樹，則空操作；否則， （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點。 2 visit(Tdata)。 三叉鏈表的 C 語言類型描述如下 : parent lchild data rchild 結(jié)點結(jié)構(gòu) : // 結(jié)點結(jié)構(gòu) // 左右孩子指針 //雙親指針 鏈式存儲 — 三叉鏈表 問題的提出 在實際應(yīng)用中，經(jīng)常需要在二叉樹中查找具有某些特征的結(jié)點，或者對樹中的全部結(jié)點逐一進行某種處理，這就提出了二叉樹的遍歷的問題 。 } SqBiTree。 char flag[MAX_TREE_SIZE]。 } TriTNode, *TriTree。 e)) { // 先序遍歷二叉樹 1 if (!T) return。 // 訪問結(jié)點 4 Inorder(Trchild, visit)。 三種遍歷的比較 三種遍歷的執(zhí)行過程是不一樣的（ visit的位置不一樣）。 // 訪問結(jié)點 3 Preorder(Tlchild, visit)。 return (m+n+1)。 if (Tdata==x) return (T)； if(p) //返回值不是空指針，則表示 x在左子樹中 return(p)。 prchild =pr。 if (ch = = 39。 i= high。 prchild = pr。 pl = create(pre, in, prepos + 1, low, i 1)。 // 構(gòu)造左子樹 CreateBiTree(Trchild)。ch)。 p = new BiNode。 depthval = 1 + (depthLeft depthRight ? depthLeft :depthRight)。 printf(”%d”,count)。 Preorder( Trchild)。 2 Postorder(Tlchild, visit)。 // 遍歷右子樹 } 先序遍歷 中序（根）遍歷 左 子樹 右 子樹 根 根左 子樹 右 子樹 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結(jié)點； （ 3）中序遍歷右子樹 中序（根）遍歷 A B C D E F G H K A B D C E H G K F 中序遍歷 void Inorder (BiTree T, void( *visit)(TElemTypeamp。 問題的提出 線性結(jié)構(gòu)的遍歷： 因為每個結(jié)點均只有一個后繼，所以只有一條搜索路徑。 // 左
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1