關(guān)于二叉樹的概念：
百度百科給的定義是：
二叉樹是一個(gè)連通的無環(huán)圖吠昭，并且每一個(gè)頂點(diǎn)的度不大于3铐然。有根二叉樹還要滿足根結(jié)點(diǎn)的度不大于2。有了根結(jié)點(diǎn)之后，每個(gè)頂點(diǎn)定義了唯一的父結(jié)點(diǎn)努隙，和最多2個(gè)子結(jié)點(diǎn)。然而费韭，沒有足夠的信息來區(qū)分左結(jié)點(diǎn)和右結(jié)點(diǎn)别垮。如果不考慮連通性，允許圖中有多個(gè)連通分量晶府，這樣的結(jié)構(gòu)叫做森林桂躏。
二叉樹是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分川陆，邏輯上二叉樹有五種基本形態(tài)：
(1)空二叉樹——如圖(a)剂习；
(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹——如圖(b)；
(3)只有左子樹——如圖(c)；
(4)只有右子樹——如圖(d)鳞绕；
(5)完全二叉樹——如圖(e)失仁。
注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形
我們來提煉一下定義中存在的信息：二叉樹是符合每個(gè)節(jié)點(diǎn)的子樹個(gè)數(shù)不能超過2的们何，且僅有一個(gè)根節(jié)點(diǎn)特征的樹的集合
關(guān)于二叉樹的先序遍歷萄焦，中序遍歷和后序遍歷：（此處只做大概的解釋，想要詳細(xì)了解的朋友可以點(diǎn)這里）
先序遍歷：先訪問根節(jié)點(diǎn)冤竹，在訪問左節(jié)點(diǎn)拂封，最后訪問右節(jié)點(diǎn)（根左右）
中序遍歷：先訪問左節(jié)點(diǎn)，在訪問根節(jié)點(diǎn)鹦蠕，最后訪問右節(jié)點(diǎn)（左根右）
后序遍歷：先訪問左節(jié)點(diǎn)烘苹，在訪問右節(jié)點(diǎn)，最后訪問根節(jié)點(diǎn)（左右根）
做了這么多的準(zhǔn)備工作片部，接下來我們來看看如何通過一個(gè)二叉樹的先序遍歷和中序遍歷確定一顆樹：
我們先分析一下：根據(jù)先序遍歷的特性镣衡，我們能知道，第一個(gè)節(jié)點(diǎn)一定是整棵樹的根節(jié)點(diǎn)档悠，知道了根節(jié)點(diǎn)后廊鸥，我們可以在中序遍歷總找到根節(jié)點(diǎn)的位置，通過中序遍歷的特性辖所，我們可以知道在根節(jié)點(diǎn)左邊的節(jié)點(diǎn)都是左子樹即根節(jié)點(diǎn)的孫子節(jié)點(diǎn)惰说，在根節(jié)點(diǎn)右邊的都是根節(jié)點(diǎn)的右子樹即根節(jié)點(diǎn)的孫子節(jié)點(diǎn)。通過下面的實(shí)例能理解更深：
先：ABDECFGHI
中：DBEAGFHIC
第一步：通過先序找到根節(jié)點(diǎn)為A,并且找到A在中序中的位置
第二步：通過A我們將序列劃分為?
? ? ? ? ? ? ? ? ?左子樹及其子節(jié)點(diǎn):DBE?
? ? ? ? ? ? ? ? ?右子樹及其節(jié)點(diǎn):GFHIC
這樣的話缘回，我們就可以對于得到的新序列進(jìn)行再一次劃分吆视，這個(gè)熟悉遞歸的朋友就能知道，接下來就是遞歸的典型使用場景了酥宴。我就不多加敘述啦吧，一切盡在代碼中。
算法流程如下：
?1.將先序序列及中序序列劃分為左區(qū)和右區(qū)域
2.重復(fù)步驟1拙寡，直到以下情況才能終止遞歸
? ? ? a.當(dāng)序列長度僅為1時(shí)授滓，只剩下一個(gè)節(jié)點(diǎn)
? ? ? b.當(dāng)序列長度為0時(shí)，返回節(jié)點(diǎn)null
本人使用java實(shí)現(xiàn)的代碼如下：（僅貼出部分重要代碼）
需要閱讀完整代碼的朋友可以移步到通過先序中序創(chuàng)建二叉樹
class TreeNode{
? ? ? ? ? ?public String nodeName;
? ? ? ? ? ?public TreeNode lchild;
? ? ? ? ? ? public TreeNode rchild;
? ? ? ? ? ? public TreeNode(String nodeName,TreeNode lchild,TreeNode rchild) {
? ? ? ? ? ? ? ? ? ? ? ? this.nodeName=nodeName;
? ? ? ? ? ? ? ? ? ? ? ? this.lchild=lchild;
? ? ? ? ? ? ? ? ? ? ? ? this.rchild=rchild;
? ? ? ? ? ?}
}
這是一個(gè)表示節(jié)點(diǎn)的類肆糕，用于存儲(chǔ)節(jié)點(diǎn)
public TreeNode creatTree(String bef,String mid) {
? ? ? ? ? ? ? ? ? ? String root=bef.substring(0, 1);
? ? ? ? ? ? ? ? ? ? int rootindex=mid.indexOf(root);
? ? ? ? ? ? ? ? ? ? System.out.println(rootindex);
? ? ? ? ? ? ? ? ? ? String leftBef=bef.substring(1, rootindex+1);
? ? ? ? ? ? ? ? ? ? ?String leftMid=mid.substring(0, rootindex);
? ? ? ? ? ? ? ? ? ? ?System.out.println("left child:"+leftBef+"? ? "+leftMid);
? ? ? ? ? ? ? ? ? ? ?TreeNode lchild=initTree(leftBef,leftMid);
? ? ? ? ? ? ? ? ? ? ?int len=mid.length();
? ? ? ? ? ? ? ? ? ? ?String rightBef=bef.substring(rootindex+1,len);
? ? ? ? ? ? ? ? ? ? ?String rightMid=mid.substring(rootindex+1,len);
? ? ? ? ? ? ? ? ? ? ?System.out.println("right child:"+rightBef+"? ? "+rightMid);
? ? ? ? ? ? ? ? ? ? ?TreeNode rchild=initTree(rightBef,rightMid);
? ? ? ? ? ? ? ? ? ? ?rootNode=new TreeNode(root, lchild, rchild);
? ? ? ? ? ? ? ? ? ? ?return rootNode;
}
/**
* 遞歸
* @param bef
* @param mid
* @return
*/
public TreeNode initTree(String bef,String mid) {
? ? ? ? ? if(bef.length()==1&&mid.length()==1) {
? ? ? ? ? ? ? ? ? ? ? ?return new TreeNode(bef, null, null);
? ? ? ? ? }
? ? ? ? String root=bef.substring(0, 1);
? ? ? ? int rootindex=mid.indexOf(root);
? ? ? ? String leftBef=bef.substring(1, rootindex+1);
? ? ? ? String leftMid=mid.substring(0, rootindex);
? ? ? ? TreeNode lchild=null;
? ? ? ? if(leftBef.length()==leftMid.length()&&leftBef.length()!=0) {? //不為空時(shí)
? ? ? ? ? ? ? ? lchild=initTree(leftBef,leftMid);
? ? ? ? }
? ? ? ?int len=mid.length();
? ? ? ?String rightBef=bef.substring(rootindex+1,len);
? ? ? ?String rightMid=mid.substring(rootindex+1,len);
? ? ? TreeNode rchild=null;
? ? ?if(rightMid.length()==rightBef.length()&&rightBef.length()!=0) {
? ? ? ? ? rchild=initTree(rightBef,rightMid);
? ? ?}
? ? ?TreeNode rootNode=new TreeNode(root, lchild, rchild);
? ? ? return rootNode;
}
