java樹的遍歷演算法
『壹』 java中的遍歷是什麼意思
遍歷就是把每個元素都訪問一次.比如一個二叉樹,遍歷二叉樹意思就是把二叉樹中的每個元素都訪問一次
『貳』 java二叉樹遍歷問題
二叉樹具有以下重要性質：
性質1 二叉樹第i層上的結點數目最多為2i-1(i≥1)。
證明：用數學歸納法證明：
歸納基礎：i=1時，有2i-1=20=1。因為第1層上只有一個根結點，所以命題成立。
歸納假設：假設對所有的j(1≤j<i)命題成立，即第j層上至多有2j-1個結點，證明j=i時命題亦成立。
歸納步驟：根據歸納假設，第i-1層上至多有2i-2個結點。由於二叉樹的每個結點至多有兩個孩子，故第i層上的結點數至多是第i-1層上的最大結點數的2倍。即j=i時，該層上至多有2×2i-2=2i-1個結點，故命題成立。
性質2 深度為k的二叉樹至多有2k-1個結點(k≥1)。
證明：在具有相同深度的二叉樹中，僅當每一層都含有最大結點數時，其樹中結點數最多。因此利用性質1可得，深度為k的二叉樹的結點數至多為：
20+21+…+2k-1=2k-1
故命題正確。
性質3 在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1。
證明：因為二叉樹中所有結點的度數均不大於2，所以結點總數(記為n)應等於0度結點數、1度結點(記為n1)和2度結點數之和：
n=no+n1+n2 (式子1)
另一方面，1度結點有一個孩子，2度結點有兩個孩子，故二叉樹中孩子結點總數是：
nl+2n2
樹中只有根結點不是任何結點的孩子，故二叉樹中的結點總數又可表示為：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1
滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。
1、滿二叉樹(FullBinaryTree)
一棵深度為k且有2k-1個結點的二又樹稱為滿二叉樹。
滿二叉樹的特點：
（1） 每一層上的結點數都達到最大值。即對給定的高度，它是具有最多結點數的二叉樹。
（2） 滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。
圖(a)是一個深度為4的滿二叉樹。
2、完全二叉樹(Complete BinaryTree)
若一棵二叉樹至多隻有最下面的兩層上結點的度數可以小於2，並且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。
特點：
（1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。
（2） 在滿二叉樹的最下一層上，從最右邊開始連續刪去若干結點後得到的二叉樹仍然是一棵完全二叉樹。
（3） 在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。
如圖(c)中，結點F沒有左孩子而有右孩子L，故它不是一棵完全二叉樹。
圖(b)是一棵完全二叉樹。
性質4 具有n個結點的完全二叉樹的深度為
證明：設所求完全二叉樹的深度為k。由完全二叉樹定義可得：
深度為k得完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結點。
由於完全二叉樹深度為k，故第k層上還有若干個結點，因此該完全二叉樹的結點個數：
n>2k-1-1。
另一方面，由性質2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取對數後有：
k-1≤lgn<k
又因k-1和k是相鄰的兩個整數，故有
,
由此即得：
注意：
的證明
『叄』 二叉樹的java實現與幾種遍歷
二叉樹的定義
二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.
從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5種表現形式
二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷
前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹
中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹
後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點
其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序
具體實現看下圖：
『肆』 如何用Java拼接JSON方式遍歷整個樹形節點
//是類似這種嗎
//控制層使用JSONArrayjsonObject=JSONArray.fromObject(）;轉換
Map<String,Object>map=newHashMap<String,Object>();
map.put("id","1");
map.put("text","實驗外國語學校");
List<Map<String,Object>>fatherList=newArrayList<Map<String,Object>>();
List<Map<String,Object>>list=newArrayList<Map<String,Object>>();
for(Beanbean:list){
if("1".equals(list.getParent_level())){
Map<String,Object>map2=newHashMap<String,Object>();
map2.put("id",list.getId());
map2.put("text",list.getName());
list.add(map2);
}
}
map.put("children",list);