定義二叉樹結點
比如就拿這個二叉樹
前序中序創建
因為前序遍歷的順序是 根 , 左 ,右。
中序的遍歷是 左 根 右。
我們會很不好想,但我們可以用前序和中序把上面那個二叉樹的遍歷一邊
前序遍歷:ABDEHCFG中序遍歷:DBEHAFCG
然后根據這我們來想
創建的時候,值都是以數組的形式傳進來,所以找到根節點,前序和中序左子樹個數一定相等,都是r。
前序和中序創建左子樹的時候,挨個往后走就行,傳的數組長度也就是個數就是r,左子樹的個數,到右子樹時。此時左子樹創建完,所以前序要跳過r個元素,也就是創建左子樹的個數,并加上根節點,也就是r+1.,創建右子樹時個數就要減去根+左子樹的個數。中序也是如此。
程序一開始,要先找到r的大小,也就是中序遍歷和前序遍歷時根結點的位置。
中序后序創建
與之前的道理是相似的,先找到根節點所在位置,也就是左子樹個數
然后找到根的值,也就是后序數組中的最后一個,然后道理相同,先左,再右