資料結構之二叉樹的遍歷
基本概念:
每個結點最多有兩棵子樹,左子樹和右子樹。
性質:
1、非空二叉樹的第n層上至多有2^(n-1)個元素。
2、深度為h的二叉樹至多有2^h-1個結點。
滿二叉樹:所有終端都在同一層次,且非終端結點的度數為2。
在滿二叉樹中若其深度為h,則其所包含的結點數必為2^h-1。
完全二叉樹:除了最大的層次即成為一顆滿二叉樹且層次最大那層所有的結點均向左靠齊,即集中在左面的位置上,不能有空位置。
對於完全二叉樹,設一個結點為i則其父節點為i/2,2i為左子節點,2i+1為右子節點。
存儲結構
二叉樹的存儲結構可以採用順序存儲,也可以採用鏈式存儲,其中鏈式存儲更加靈活。
在鏈式存儲結構中,與線性鏈表類似,二叉樹的每個結點採用結構體表示,結構體包含三個域:資料欄、左指針、右指針。
在C語言中的定義
定義二叉樹
二叉樹的遍歷
遍歷即將樹的所有結點訪問且僅訪問一次。按照根節點位置的不同分為前序遍歷,中序遍歷,
前序遍歷:根節點->左子樹->右子樹
中序遍歷:左子樹->根節點->右子樹
後序遍歷:左子樹->右子樹->根節點
遍歷下面這個二叉樹
前序遍歷:abdefgc
中序遍歷:debgfac
後序遍歷:edgfbca
代碼實現( q是頭指針)
前序遍歷
中序遍歷
後序遍歷