天天看點

從零開始學算法---二叉樹

什麼是樹? 

樹是n(n>=0)個結點的有限集。n=0時稱為空樹,在任意一棵非空樹中,有且僅有一個特定的稱為根(root)的結點, 當n>1時,其餘結點可分為m個互不相交的有限集。 下圖中第一張圖就不是樹, 因為d和e相交

從零開始學算法---二叉樹

樹的存儲結構?

樹的存儲結構一般有4種,

1)雙親表示法,就是在每個節點中标示出它的父節點

從零開始學算法---二叉樹

 2)孩子表示法,每個節點攜帶指針位指向自己的孩子

從零開始學算法---二叉樹

 這種方法中,每個節點除了資料域外,還要額外攜帶m個指針位(m為樹的度)

3)雙親孩子表示法

從零開始學算法---二叉樹

 4),孩子兄弟表示法

從零開始學算法---二叉樹

 二叉樹?

度<=2的樹稱為二叉樹

二叉樹的存儲結構?

1)順序存儲

從零開始學算法---二叉樹

 2, 鍊式存儲(使用孩子表示法)

從零開始學算法---二叉樹

 二叉樹的周遊?

1)前序周遊(DLR), 規則是:若二叉樹為空,則空操作傳回,否則先通路根節點,然後前序周遊左子樹,再前序周遊右子樹

從零開始學算法---二叉樹

 代碼實作:

測試代碼 

輸出結果:

從零開始學算法---二叉樹

 2)相對于前序周遊(DLR)來說, 中序周遊(LDR)就是先通路左子樹,再通路中間節點,再通路右子樹

從零開始學算法---二叉樹

 3)後續周遊(LRD)

輸出結果

從零開始學算法---二叉樹

 小結: 所謂前序後序中序其實就是 通路根節點是在通路左右節點的前面、後面還是中間

繼續閱讀