樹由邊連接的節(jié)點(diǎn)構(gòu)成。節(jié)點(diǎn)一般代表實(shí)體數(shù)據(jù)，如代表某一類數(shù)據(jù)。windows文件系統(tǒng)就可以看成是一棵樹，比如C盤下有一些文件夾，這些文件夾下面又分別有一些文件夾，這樣的關(guān)系其實(shí)就是一棵樹。
根：樹頂端的節(jié)點(diǎn)稱為樹的根，一棵樹只有一個(gè)根。
父節(jié)點(diǎn)：每一個(gè)節(jié)點(diǎn)（除了根）都有一條邊向上連接到另一個(gè)節(jié)點(diǎn)，上面的這個(gè)節(jié)點(diǎn)就稱為下面節(jié)點(diǎn)的父節(jié)點(diǎn)。
子節(jié)點(diǎn)：與父節(jié)點(diǎn)相反雅思答案 www.tygj123.com
子樹：每個(gè)節(jié)點(diǎn)都可以作為子樹的根，它和它所有的子節(jié)點(diǎn)，還有子節(jié)點(diǎn)的子節(jié)點(diǎn)都在子樹中。
二叉樹：如果樹中每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，這樣的樹就稱為二叉樹。
二叉樹的兩個(gè)節(jié)點(diǎn)分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。
Java中表示二叉樹，可以用數(shù)組表示樹，常用的方法是將節(jié)點(diǎn)存在無關(guān)聯(lián)的容器中，再通過每個(gè)節(jié)點(diǎn)指向自己的子節(jié)點(diǎn)的引用來連接。
下面的方法用的就是后一種：
package test;
public class BinaryTree {
static Node root;
public Node find（int key） {
Node current = root;// 從根節(jié)點(diǎn)開始，用current保存正在查看的節(jié)點(diǎn)
while （current.idata != key） {
if （key < current.idata）
current = current.leftChild;
else
current = current.rightChild;
if （current == null）
return null;
}
return current;
}
public void insert（int key） {
// 首先要找到插入的地方
Node inode = new Node（）；
inode.idata = key;// 賦值
if （root == null）
root = inode;// 空樹，則作為根節(jié)點(diǎn)
else {
Node current = root;// 從根節(jié)點(diǎn)開始比對(duì)
Node parent;
while （true） {
// 用parent來存儲(chǔ)current,目的是在current變?yōu)榭盏臅r(shí)候，
// 才知道current== null時(shí)對(duì)應(yīng)的上一個(gè)節(jié)點(diǎn)（parent）沒有子節(jié)點(diǎn)
parent = current;
if （key < current.idata） {
current = current.leftChild;
if （current == null） {
parent.leftChild = inode;
return;
}
} else {
current = current.rightChild;
if （current == null） {
parent.rightChild = inode;
return;
}
}
}
}
}
/**
* 找到要?jiǎng)h除的節(jié)點(diǎn) 有三種情況：1）該節(jié)點(diǎn)是頁節(jié)點(diǎn) ,2）該節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn) ,3）該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
* （刪除好復(fù)雜，于是可以這樣：在每一個(gè)節(jié)點(diǎn)上添加一個(gè)字段isDelete,若需要?jiǎng)h除，則置為true）
*/
public boolean delete（int key） {
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while （current.idata != key） {
parent = current;
if （key < current.idata） {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if （current == null）
return false;
}// 找到了節(jié)點(diǎn)
// 判斷有無子節(jié)點(diǎn) www.wx-jr.com
if （current.leftChild == null && current.rightChild == null） {
if （current == root）
root = null;
else if （isLeftChild）
parent.leftChild = null;
else
parent.rightChild = null;
} else if （current.rightChild == null） {
if （current == root）
root = current.leftChild;
else if （isLeftChild）
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
} else if （current.leftChild == null） {
if （current == root）
root = current.rightChild;
else if （isLeftChild）
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
}
/**
* 刪除一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)，就不能用它的一個(gè)子節(jié)點(diǎn)來代替它，而要用它的中序后繼代替該節(jié)點(diǎn) 如何找？
* 首先，找到初始節(jié)點(diǎn)的右子節(jié)點(diǎn)rcn,然后轉(zhuǎn)到rcn的左子節(jié)點(diǎn)（有的話）rcnl,然后轉(zhuǎn)到rcnl的左子節(jié)點(diǎn)，直到結(jié)束。
* 這里實(shí)際上要找的是比初始節(jié)點(diǎn)值大的集合中最小的那一個(gè) 如果初始節(jié)點(diǎn)的右子節(jié)點(diǎn)沒有左子節(jié)點(diǎn)，那么其本身就是后繼
*/
else {
Node success = getMidPostNode（current）；
if （current == root）
root = success;
else if （isLeftChild）
parent.leftChild = success;
else
parent.rightChild = success;
success.leftChild = current.leftChild;
}
return true;
}
// 獲取當(dāng)前節(jié)點(diǎn)的中序后繼 www.sd-gw.com
public Node getMidPostNode（Node delNode） {
Node successParent = delNode;
Node success = delNode;
Node current = delNode.rightChild;
while （current != null） {// 直到找到當(dāng)前節(jié)點(diǎn)右子節(jié)點(diǎn)的最左子孫節(jié)點(diǎn)
successParent = success;
success = current;
current = current.leftChild;
}
if （success != delNode.rightChild） {
successParent.leftChild = success.rightChild;
success.rightChild = delNode.rightChild;
}
return success;
}
// 前序遍歷
public void preTraverse（Node root） {
if （root != null） {
System.out.println（root.idata + " "）；
preTraverse（root.leftChild）；
preTraverse（root.rightChild）；
}
}
// 中序遍歷
public void midTraverse（Node root） {
if （root != null） {
midTraverse（root.leftChild）；
System.out.println（root.idata + " "）；
midTraverse（root.rightChild）；
}
}
// 后續(xù)遍歷
public void postTraverse（Node root） {
if （root != null） {
postTraverse（root.leftChild）；
postTraverse（root.rightChild）；
System.out.println（root.idata + " "）；
}
}
// 遞歸地交換二叉樹的左右子節(jié)點(diǎn)
public void swap（Node root） {
if（root == null）
return;
Node tmp = root.leftChild;
root.leftChild = root.rightChild;
root.rightChild = tmp;
swap（root.leftChild）；
swap（root.rightChild）；
}
public static void main（String[] args） {
BinaryTree bt = new BinaryTree（）；
bt.insert（1）；
bt.insert（2）；
bt.insert（3）；
bt.insert（0）；
bt.insert（5）；
// Node f = bt.find（2）；
// System.out.println（"find = " + f.idata）；
// bt.delete（3）；
// bt.preTraverse（root）；
// System.out.println（"----------"）；
// bt.midTraverse（root）；
// System.out.println（"----------"）；
// bt.postTraverse（root）；
// System.out.println（"---------->"）；
bt.printBinaryTree（root, 0）；
bt.swap（root）；
bt.printBinaryTree（root, 0）；
}
//遞歸打印樹形二叉樹
public static void printBinaryTree（Node root, int level）{
if（root==null）
return;
printBinaryTree（root.rightChild, level+1）；
if（level!=0）{
for（int i=0;i<LEVEL-1;I++） pre }< rightChild; Node leftChild; idata; int { } level+1）； printBinaryTree（root.leftChild, System.out.println（root.idata）； else System.out.println（？|-------?+root.idata）； System.out.print（？|\t?）；><BR>
<BR>
<P></P>