二叉樹結構
/**
* 二叉樹的特點：
* 性質1：在二叉樹的第i層上至多有2^(i-1)個節點(i >= 1)
* 性質2：深度為k的二叉樹至多有2^k-1個節點(k >=1)
* 性質3：對於任意一棵二叉樹T而言，其葉子節點數目為N0,度為2的節點數目為N2，則有N0 = N2 + 1。
* 性質4：具有n個節點的完全二叉樹的深度
*/
public class Tree {
private Node root;
private List
public Tree(){
init();
}
//樹的初始化，先從葉節點開始
public void init(){
Node x = new Node("x",null,null);
Node y = new Node("y",null,null);
Node d=new Node("d",x,y);
Node e=new Node("e",null,null);
Node f=new Node("f",null,null);
Node c=new Node("c",e,f);
Node b=new Node("b",d,null);
Node a=new Node("a",b,c);
root =a;
}
//定義樹節點類
public class Node{
private String data; //定義節點名稱
private Node lchild;//定義指向左支數的指針
private Node rchild;//定義指向右支數的指針
public Node(String data,Node lchild,Node rchild){
this.data = data;
this.lchild = lchild;
this.rchild = rchild;
}
}
//前序遍歷，將遍歷的結果存到list中 遍歷結果：abdxycef
public void preOrder(Node node){
//先將根節點存入list
list.add(node);
//如果左子樹不為空繼續往左找，在遞歸調用方法的時候一直會將子樹的根存入list，這就做到了先遍歷根節點
if(node.lchild != null){
preOrder(node.lchild);
}
//無論走到哪一層，只要當前節點左子樹為空，那麼就可以在右子樹上遍歷，保證了根左右的遍歷順序
if(node.rchild != null){
preOrder(node.rchild);
}
}
//中序遍歷，將遍歷的結果存到list中 遍歷結果：xdybaecf
public void inOrder(Node node){
if(node.lchild != null){
inOrder(node.lchild);
}
list.add(node);
if(node.rchild !=null){
inOrder(node.rchild);
}
}
//後序遍歷，將遍歷的結果存到list中 遍歷結果：xydbefca
public void lastOrder(Node node){
if(node.lchild != null){
lastOrder(node.lchild);
}
if(node.rchild != null){
lastOrder(node.rchild);
}
list.add(node);
}
/**
* 返回當前數的深度
* 說明:
* 1、如果一棵樹只有一個結點，它的深度為1。
* 2、如果根結點只有左子樹而沒有右子樹，那麼樹的深度是其左子樹的深度加1；
* 3、如果根結點只有右子樹而沒有左子樹，那麼樹的深度應該是其右子樹的深度加1；
* 4、如果既有右子樹又有左子樹，那該樹的深度就是其左、右子樹深度的較大值再加1。
*/
public int getTreeDepth(Node node){
if(node.lchild == null && node.rchild == null){
return 1;
}
int left = 0;
int right =0;
if(node.lchild != null){
left = getTreeDepth(node.lchild);
}
if(node.rchild != null){
right = getTreeDepth(node.rchild);
}
return left>right?left+1:right+1;
}
//得到遍歷結果
public List
return list;
}
public static void main(String[] args){
Tree tree = new Tree();
System.out.println("根節點是："+tree.root);
tree.preOrder(tree.root);
//tree.inOrder(tree.root);
//tree.lastOrder(tree.root);
for(Node node : tree.getResult()){
System.out.println(node.data);
}
System.out.println("樹的深度："+tree.getTreeDepth(tree.root));
}
}
閱讀更多 Java技術之路 的文章
