什麼是樹?
樹是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)
輸出結果
小結: 所謂前序後序中序其實就是 通路根節點是在通路左右節點的前面、後面還是中間