生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法--重建二叉树
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
二叉樹
- 樹在實際編程中經常遇到地一種數據結構。上一篇中我們解釋了二叉樹及其原理，從中可以知道，樹地操作會涉及到很多指針地操作，我們一般遇到地樹相關地問題差不多都是二叉樹。二叉樹最重要地莫過于遍歷，即按照某一順序訪問樹中所有節點，通常有如下幾種遍歷方式：
- 前序遍歷：先根節點，左節點，右節點。用以上順序來訪問
- 中序遍歷：先左節點，中節點，右節點
- 后續遍歷：先左節點，右節點，中節點
- 以上三種遍歷都有遞歸和循環兩種不同地實現方式，每一種遍歷地遞歸實現都比循環實現要簡單。在上一節中已經給出了三種遞歸遍歷地實現方式。
- 二叉樹還有很多特例，二叉搜索樹左子樹中節點總數小于或者等于根節點。右子樹地節點總數大于等于根節點。
- 二叉樹特例還包括堆和紅黑樹。堆分為最大堆和最小堆。
- 一下我們利用二叉樹地三種遍歷方式地特性來解決如下算法問題：
重建二叉樹
- 題目：輸入某個二叉樹前序遍歷，中序遍歷地結果，請重建該二叉樹。我們假設駛入地前序遍歷，中序遍歷不包含重復數字。例如：前序（1，2，4，7，3，5，6，8），中序遍歷（4，7，2，1，5，3，8，6），如下圖
分析
- 二叉樹前序遍歷中，第一個數字總數樹地根節點。
- 中序遍歷中，根節點在序列中間。左子樹在根節點左邊，右子樹在根節點右邊
- 我們通過前序遍歷找到根節點
- 在中序遍歷中確認跟節點的位置后得到左右子樹的長度
- 接著將左子樹，右子樹分別執行以上流程（遞歸）
- 如下圖，在二叉樹的前序遍歷和中序遍歷的序列中確定根節點的值，左子樹的值和右子樹的值
實現
public class BinaryNode implements Comparable {private Object element
;private BinaryNode left
;private BinaryNode right
;private int height
;private int count
;public BinaryNode(Object element
, BinaryNode left
, BinaryNode right
) {this.element
= element
;this.left
= left
;this.right
= right
;this.count
= 1;this.height
= 0;}public int getHeight() {return height
;}public void setHeight(int height
) {this.height
= height
;}public Object
getElement() {return element
;}public void setElement(Object element
) {this.element
= element
;}public BinaryNode
getLeft() {return left
;}public void setLeft(BinaryNode left
) {this.left
= left
;}public BinaryNode
getRight() {return right
;}public void setRight(BinaryNode right
) {this.right
= right
;}public int getCount() {return count
;}public void setCount(int count
) {this.count
= count
;}@Overridepublic int compareTo(Object o
) {if (o
== null
) {return 1;}int flag
;if (o
instanceof Integer) {int myElement
= (int) this.element
- (int) o
;flag
= myElement
> 0 ? 1 : myElement
== 0 ? 0 : -1;} else {flag
= this.element
.toString().compareTo(o
.toString());}if (flag
== 0) {return 0;} else if (flag
> 0) {return 1;} else {return -1;}}
}
package com
.ljm
.resource
.math
.binary
;
public class RebuildBinary {public static BinaryNode
construct(int[] preOrder
, int[] inOrder
){if(preOrder
== null
|| inOrder
== null
|| preOrder
.length
!= inOrder
.length
|| preOrder
.length
<= 0){System
.out
.println("Invalid input");return null
;}return constructCore(preOrder
, inOrder
, 0, preOrder
.length
-1, 0, inOrder
.length
-1);}public static BinaryNode
constructCore(int[] preOrder
, int[] inOrder
,int preStart
, int preEnd
,int inStart
, int inEnd
){int rootValue
= preOrder
[preStart
];BinaryNode rootNode
= new BinaryNode(rootValue
, null
, null
);if(preStart
== preEnd
){if(inStart
== inEnd
&& preOrder
[preStart
] == inOrder
[inStart
]){return rootNode
;}else {System
.out
.println("Invalid input");return null
;}}int rootInOrderIndex
= inStart
;while (rootInOrderIndex
<= inEnd
&& inOrder
[rootInOrderIndex
] != rootValue
){rootInOrderIndex
++;}if(rootInOrderIndex
== inEnd
&& inOrder
[rootInOrderIndex
] != rootValue
){System
.out
.println("Invalid input");return null
;}int leftLength
= rootInOrderIndex
- inStart
;if(leftLength
> 0){int leftInOrderStart
= inStart
;int leftInOrderEnd
= inStart
+ leftLength
- 1;int leftPreOrderStart
= preStart
+ 1;int leftPreOrderEnd
= preStart
+ leftLength
;rootNode
.setLeft(constructCore(preOrder
, inOrder
, leftPreOrderStart
, leftPreOrderEnd
, leftInOrderStart
, leftInOrderEnd
));}if(leftLength
< preEnd
- preStart
){int rightInOrderStart
= rootInOrderIndex
+ 1;int rightInOrderEnd
= inEnd
;int rightPreOrderStart
= preStart
+ 1 + leftLength
;int rightPreOrderEnd
= preEnd
;rootNode
.setRight(constructCore(preOrder
, inOrder
, rightPreOrderStart
, rightPreOrderEnd
, rightInOrderStart
, rightInOrderEnd
));}return rootNode
;}public static void main(String
[] args
) {int preOrder
[] = {1,2,4,7,3,5,6,8};int inOrder
[] = {4,7,2,1,5,3,8,6};BinaryNode binaryNode
= construct(preOrder
, inOrder
);PostfixExTOTreeEx
.printMiddleFirstTree(binaryNode
);}
}
- 以上我們在函數constructCore中，我們先根據前序遍歷序列地第一個數字，創建根節點。
- 接下來在中序遍歷中找到根節點位置
- 這樣就能確定左右子樹地數量
- 在前序遍歷和中序遍歷地序列中劃分左右子樹節點后，
- 將左右子樹遞歸調用函數constructCore，分別構建左右子樹。得到最終地樹
上一篇：數據結構與算法–二叉樹實現原理
下一篇：數據結構與算法–二叉查找樹實現原理
總結
以上是生活随笔為你收集整理的数据结构与算法--重建二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
