二叉樹是樹的一種，由一個根節(jié)點和兩棵互不相交左右子樹的二叉樹組成会烙。
二叉樹有很多性質(zhì)刑巧，就不一一舉例了~
先來說一下最簡單的關(guān)于二叉樹常用的3種遍歷方式田炭。層序遍歷就略過了~
前序遍歷：根節(jié)點未妹，左節(jié)點娩贷，右節(jié)點横腿。
結(jié)果就是：ABDGHCEIF
前序遍歷
中序遍歷：左節(jié)點开缎，根節(jié)點，右節(jié)點仗岸。
結(jié)果就是：GDHBAEICF
中序遍歷
后序遍歷：左節(jié)點糊闽，右節(jié)點，根節(jié)點爹梁。
結(jié)果就是：GHDBIEFCA
后序遍歷
概念就說到這里右犹，開始敲代碼~
首先，建立數(shù)節(jié)點姚垃。
public class TreeNode {
private int index;
private String data; //數(shù)據(jù)域
private TreeNode leftChild; //左子樹
private TreeNode rightChild; //右子樹
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public TreeNodeString(String data) {
this.data = data;
}
public TreeNode(int index, String data) {
this.index = index;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
}
然后我們來構(gòu)建一個二叉樹：
/**
* 構(gòu)建二叉樹
* A
* B C
* D E F
* G H I
*/
public void createBinaryTree() {
//我們需要一個根節(jié)點
root = new TreeNode(1, "A");
TreeNode treeNodeB = new TreeNode(2, "B");
TreeNode treeNodeC = new TreeNode(3, "C");
TreeNode treeNodeD = new TreeNode(4, "D");
TreeNode treeNodeE = new TreeNode(5, "E");
TreeNode treeNodeF = new TreeNode(6, "F");
TreeNode treeNodeG = new TreeNode(7, "G");
TreeNode treeNodeH = new TreeNode(8, "H");
TreeNode treeNodeI = new TreeNode(9, "I");
//分別對應(yīng)節(jié)點的左右子樹念链。
root.leftChild = treeNodeB;
root.rightChild = treeNodeC;
treeNodeB.leftChild = treeNodeD;
treeNodeD.leftChild = treeNodeG;
treeNodeD.rightChild = treeNodeH;
treeNodeC.leftChild = treeNodeE;
treeNodeC.rightChild = treeNodeF;
treeNodeE.rightChild = treeNodeI;
}
二叉樹建立完成之后，
開始遍歷积糯，首先使用循環(huán)的方式進行前序遍歷掂墓，循環(huán)需要借助棧來實現(xiàn)遍歷。
/**
* 前序遍歷 非遞歸
* @param treeNode
*/
public void nonRecOrder(TreeNode treeNode){
if(treeNode == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
//首先把根節(jié)點放入棧中
stack.push(treeNode);
while (!stack.isEmpty()){
//彈出根結(jié)點
TreeNode node = stack.pop();
System.out.println("data:" + node.data);
//如果有右子結(jié)點看成，則壓入節(jié)點
if(node.rightChild!=null){
//如果左節(jié)點有值君编，則右節(jié)點在棧底，最后才會輸出
stack.push(node.rightChild);
}
//如果有右左結(jié)點川慌，則壓入節(jié)點
if(node.leftChild!=null){
//下次循環(huán)把左子節(jié)點當根節(jié)點繼續(xù)彈出
stack.push(node.leftChild);
}
}
}
接著來介紹使用遞歸的方式進行遍歷
/**
* 前序遍歷 遞歸
* @param treeNode
*/
public void preOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
//首先把每個節(jié)點當成根節(jié)點輸出
System.out.println("data:" + treeNode.data);
//如果左節(jié)點有值吃嘿，則輸出左節(jié)點
preOrder(treeNode.leftChild);
///如果右節(jié)點有值，輸出右節(jié)點梦重。
preOrder(treeNode.rightChild);
}
}
/**
* 中序遍歷 遞歸
* @param treeNode
*/
public void midOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
//遞歸左子樹兑燥，直到左節(jié)點為null，return琴拧。
midOrder(treeNode.leftChild);
//輸出節(jié)點降瞳。
System.out.println("data:" + treeNode.data);
//遞歸右子樹
midOrder(treeNode.rightChild);
}
}
/**
* 后序遍歷 遞歸
* @param treeNode
*/
public void postOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
//遞歸左子樹，直到左節(jié)點為null蚓胸，return挣饥。
postOrder(treeNode.leftChild);
//遞歸右子樹除师，直到左節(jié)點為null，return扔枫。
postOrder(treeNode.rightChild);
//輸出節(jié)點
System.out.println("data:" + treeNode.data);
}
}
二叉樹的遍歷理解了還是比較簡單的汛聚，下面來看一下二叉樹的重建。
已知 前序遍歷結(jié)果 ：ABDGHCEIF 中序遍歷結(jié)果：GDHBAEICF茧吊，求二叉樹贞岭。
根據(jù)前序遍歷的特性八毯，可以知道A是根節(jié)點搓侄，這種在中序中可以得出 A節(jié)點左邊的就是左節(jié)點，右邊的就是右節(jié)點话速。這個規(guī)律可以使用遞歸
整個二叉樹的
左子樹的
下面就來看看重建二叉樹的遞歸代碼讶踪，具體的在代碼中都有注釋
/**
* 已知前序和中序
* @param pre 前序集合
* @param startPre 前序集合起始點
* @param endPre 前序集合總長度
* @param in 中序集合
* @param startIn 中序集合起始點
* @param endIn 中序集合總長度
* @return
*/
public TreeNode resetBinaryTreeString(String[] pre ,int startPre,int endPre,String[] in,int startIn,int endIn){
//如果開始大于結(jié)束，就說明這個樹已經(jīng)結(jié)束了
if(startPre > endPre || startIn > endIn) {
return null;
}
//把前序的頭節(jié)點放入樹中當根節(jié)點
TreeNode node = new TreeNode(pre[startPre]);
//遍歷中序的所有節(jié)點
for (int i = startIn; i <= endIn; i++) {
//找到根節(jié)點在中序中的位置
if(pre[startPre] == in[i]){
node.leftChild = resetBinaryTreeString(
pre, //前序集合
startPre + 1, //前序左子樹起始點： startPre + 1
startPre + (i - startIn),//左子樹長度：i是root節(jié)點在中序遍歷的位置,
// (i - startIn)是中序遍歷中左子樹的長度泊交，
// 所以左子樹的總長度：前序的 startPre + 中序遍歷中左子樹的長度
in, //中序集合
startIn, //中序左子樹的起始點：startIn
i - 1); //中序左子樹的總長度：i -1
node.rightChild = resetBinaryTreeString(
pre, //前序集合
startPre + (i - startIn) + 1,//前序右子樹起始點： 前序左子樹的長度+1 , {startPre + (i - startIn)} + 1
endPre, //前序右子樹總長度： 前序的總長度
in, //中序集合
i + 1, //中序右子樹的起始點：i+1
endIn); //中序右子樹總長度： 中序的總長度
break;
}
}
return node;
}
這些是最近看二叉樹的一些收獲~簡單的分享一下乳讥。
下面貼上全部代碼：
public class BinaryTree {
private TreeNode root;
public BinaryTree() {
root = new TreeNode(1, "A");
}
/**
* 構(gòu)建二叉樹
* A
* B C
* D E F
* G H I
*/
public void createBinaryTree() {
root = new TreeNode(1, "A");
TreeNode treeNodeB = new TreeNode(2, "B");
TreeNode treeNodeC = new TreeNode(3, "C");
TreeNode treeNodeD = new TreeNode(4, "D");
TreeNode treeNodeE = new TreeNode(5, "E");
TreeNode treeNodeF = new TreeNode(6, "F");
TreeNode treeNodeG = new TreeNode(7, "G");
TreeNode treeNodeH = new TreeNode(8, "H");
TreeNode treeNodeI = new TreeNode(9, "I");
root.leftChild = treeNodeB;
root.rightChild = treeNodeC;
treeNodeB.leftChild = treeNodeD;
treeNodeD.leftChild = treeNodeG;
treeNodeD.rightChild = treeNodeH;
treeNodeC.leftChild = treeNodeE;
treeNodeC.rightChild = treeNodeF;
treeNodeE.rightChild = treeNodeI;
}
/**
* 前序遍歷 遞歸
* @param treeNode
*/
public void preOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
//首先輸出根節(jié)點。
System.out.println("data:" + treeNode.data);
//不斷的調(diào)用自身函數(shù)廓俭，把左節(jié)點輸出云石。
preOrder(treeNode.leftChild);
//根節(jié)點和左節(jié)點輸出完成，輸出右節(jié)點研乒。
preOrder(treeNode.rightChild);
}
}
/**
* 中序遍歷 遞歸
* @param treeNode
*/
public void midOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
midOrder(treeNode.leftChild);
System.out.println("data:" + treeNode.data);
midOrder(treeNode.rightChild);
}
}
/**
* 后序遍歷 遞歸
* @param treeNode
*/
public void postOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
postOrder(treeNode.leftChild);
postOrder(treeNode.rightChild);
System.out.println("data:" + treeNode.data);
}
}
/**
* 前序遍歷 非遞歸
* @param treeNode
*/
public void nonRecOrder(TreeNode treeNode){
if(treeNode == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(treeNode);
while (!stack.isEmpty()){
//彈出根結(jié)點
TreeNode node = stack.pop();
System.out.println("data:" + node.data);
//如果有右子結(jié)點汹忠，則壓入節(jié)點
if(node.rightChild!=null){
//如果左節(jié)點有值，則右節(jié)點在棧底雹熬，最后才會輸出
stack.push(node.rightChild);
}
//如果有右左結(jié)點宽菜，則壓入節(jié)點
if(node.leftChild!=null){
//下次循環(huán)把左子節(jié)點當根節(jié)點繼續(xù)彈出
stack.push(node.leftChild);
}
}
}
/**
* 已知前序和中序
* @param pre 前序集合
* @param startPre 前序集合起始點
* @param endPre 前序集合總長度
* @param in 中序集合
* @param startIn 中序集合起始點
* @param endIn 中序集合總長度
* @return
*/
public TreeNode resetBinaryTreeString(String[] pre ,int startPre,int endPre,String[] in,int startIn,int endIn){
//如果開始大于結(jié)束，就說明這個樹已經(jīng)結(jié)束了
if(startPre > endPre || startIn > endIn) {
return null;
}
//把前序的頭節(jié)點放入樹中當根節(jié)點
TreeNode node = new TreeNode(pre[startPre]);
//遍歷中序的所有節(jié)點
for (int i = startIn; i <= endIn; i++) {
//找到根節(jié)點在中序中的位置
if(pre[startIn] == in[i]){
node.leftChild = resetBinaryTreeString(
pre, //前序集合
startPre + 1, //前序左子樹起始點： startPre + 1
startPre + (i - startIn),//左子樹長度：i是root節(jié)點在中序遍歷的位置,
// (i - startIn)是中序遍歷中左子樹的長度竿报，
// 所以左子樹的總長度：前序的 startPre + 中序遍歷中左子樹的長度
in, //中序集合
startIn, //中序左子樹的起始點：startIn
i - 1); //中序左子樹的總長度：i -1
node.rightChild = resetBinaryTreeString(
pre, //前序集合
startPre + (i - startIn) + 1,//前序右子樹起始點： 前序左子樹的長度+1 , {startPre + (i - startIn)} + 1
endPre, //前序右子樹總長度： 前序的總長度
in, //中序集合
i + 1, //中序右子樹的起始點：i+1
endIn); //中序右子樹總長度： 中序的總長度
break;
}
}
return node;
}
public static void main(String[] args){
BinaryTree binaryTree= new BinaryTree();
binaryTree.createBinaryTree();
System.out.println("非遞歸前序");
binaryTree.nonRecOrder(binaryTree.root);
System.out.println("遞歸前序");
binaryTree.preOrder(binaryTree.root);
System.out.println("遞歸中序");
binaryTree.midOrder(binaryTree.root);
System.out.println("遞歸后序");
binaryTree.postOrder(binaryTree.root);
String[] pre = {"A","B","D","G","H","C","E","I","F"};
String[] mid = {"G","D","H","B","A","E","I","C","F"};
TreeNode root = binaryTree.resetBinaryTreeString(pre, 0, pre.length - 1, mid, 0, mid.length - 1);
System.out.println("重建二叉樹前序");
binaryTree.preOrder(root);
}
public class TreeNode {
/**
*
*/
private int index;
/**
* 數(shù)據(jù)域
*/
private String data;
/**
* 左子樹
*/
private TreeNode leftChild;
/**
* 右子樹
*/
private TreeNode rightChild;
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public TreeNode(int index, String data) {
this.index = index;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public TreeNode(String data) {
this.data = data;
}
}
}
