轉載請注明出處：http://blog.csdn.net/zhaokaiqiang1992
二叉樹是一種非常重要的資料結構，它同時具有數組和連結清單各自的特點：它可以像數組一樣快速查找，也可以像連結清單一樣快速添加。但是他也有自己的缺點：删除操作複雜。
我們先介紹一些關于二叉樹的概念名詞。
二叉樹：是每個結點最多有兩個子樹的有序樹，在使用二叉樹的時候，資料并不是随便插入到節點中的，一個節點的左子節點的關鍵值必須小于此節點，右子節點的關鍵值必須大于或者是等于此節點，是以又稱二叉查找樹、二叉排序樹、二叉搜尋樹。
完全二叉樹：若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹。
滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
深度——二叉樹的層數，就是深度。
二叉樹的特點總結：
（1）樹執行查找、删除、插入的時間複雜度都是o(logn)
（2）周遊二叉樹的方法包括前序、中序、後序
（3）非平衡樹指的是根的左右兩邊的子節點的數量不一緻
（4） 在非空二叉樹中，第i層的結點總數不超過 , i>=1；
（5）深度為h的二叉樹最多有個結點(h>=1)，最少有h個結點；
（6）對于任意一棵二叉樹，如果其葉結點數為n0，而度數為2的結點總數為n2，則n0=n2+1；
二叉樹的java代碼實作
首先是樹的節點的定義，下面的代碼中使用的是最簡單的int基本資料類型作為節點的資料，如果要使用節點帶有更加複雜的資料類型，換成對應的對象即可。
[java] view
plaincopy
/**
*
* @classname: com.tree.treenode
* @description: 節點
* @author zhaokaiqiang
* @date 2014-12-5 下午4:43:24
*/
public class treenode {
// 左節點
private treenode leftreenode;
// 右節點
private treenode rightnode;
// 資料
private int value;
private boolean isdelete;
public treenode getleftreenode() {
return leftreenode;
}
public void setleftreenode(treenode leftreenode) {
this.leftreenode = leftreenode;
public treenode getrightnode() {
return rightnode;
public void setrightnode(treenode rightnode) {
this.rightnode = rightnode;
public int getvalue() {
return value;
public void setvalue(int value) {
this.value = value;
public boolean isdelete() {
return isdelete;
public void setdelete(boolean isdelete) {
this.isdelete = isdelete;
public treenode() {
super();
public treenode(int value) {
this(null, null, value, false);
public treenode(treenode leftreenode, treenode rightnode, int value,
boolean isdelete) {
@override
public string tostring() {
return "treenode [leftreenode=" + leftreenode + ", rightnode="
+ rightnode + ", value=" + value + ", isdelete=" + isdelete
+ "]";
}
下面給出二叉樹的代碼實作。由于在二叉樹中進行節點的删除非常繁瑣，是以，下面的代碼使用的是利用節點的isdelete字段對節點的狀态進行辨別
* @classname: com.tree.tree
* @description: 二叉樹的定義
* @date 2014-12-8 上午7:51:49
public class binarytree {
// 根節點
private treenode root;
public treenode getroot() {
return root;
/**
* 插入操作
*
* @param value
*/
public void insert(int value) {
treenode newnode = new treenode(value);
if (root == null) {
root = newnode;
root.setleftreenode(null);
root.setrightnode(null);
} else {
treenode currentnode = root;
treenode parentnode;
while (true) {
parentnode = currentnode;
// 往右放
if (newnode.getvalue() > currentnode.getvalue()) {
currentnode = currentnode.getrightnode();
if (currentnode == null) {
parentnode.setrightnode(newnode);
return;
}
} else {
// 往左放
currentnode = currentnode.getleftreenode();
parentnode.setleftreenode(newnode);
}
}
}
* 查找
* @param key
* @return
public treenode find(int key) {
treenode currentnode = root;
if (currentnode != null) {
while (currentnode.getvalue() != key) {
if (currentnode.getvalue() > key) {
if (currentnode == null) {
return null;
if (currentnode.isdelete()) {
return null;
} else {
return currentnode;
return null;
* 中序周遊
* @param treenode
public void inorder(treenode treenode) {
if (treenode != null && treenode.isdelete() == false) {
inorder(treenode.getleftreenode());
system.out.println("--" + treenode.getvalue());
inorder(treenode.getrightnode());
在上面對二叉樹的周遊操作中，使用的是中序周遊，這樣周遊出來的資料是增序的。
下面是測試代碼:
public class main {
public static void main(string[] args) {
binarytree tree = new binarytree();
// 添加資料測試
tree.insert(10);
tree.insert(40);
tree.insert(20);
tree.insert(3);
tree.insert(49);
tree.insert(13);
tree.insert(123);
system.out.println("root=" + tree.getroot().getvalue());
// 排序測試
tree.inorder(tree.getroot());
// 查找測試
if (tree.find(10) != null) {
system.out.println("找到了");
system.out.println("沒找到");
// 删除測試
tree.find(40).setdelete(true);
if (tree.find(40) != null) {
}