下面的方法用的就是后一种：
package test;
public class BinaryTree {
static Node root;
public Node find(int key) {
Node current = root;// 从根节点开始,用current保存正在查看的节点
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;// 空树，则作为根节点
else {
Node current = root;// 从根节点开始比对
Node parent;
while (true) {
// 用parent来存储current,目的是在current变为空的时候，
// 才知道current== null时对应的上一个节点(parent)没有子节点
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;
}
}
}
}
}
/**
* 找到要删除的节点 有三种情况：1)该节点是页节点 ,2)该节点有一个子节点 ,3)该节点有两个子节点
* (删除好复杂,于是可以这样:在每一个节点上添加一个字段isDelete,若需要删除,则置为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;
}// 找到了节点
// 判断有无子节点
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;
}
/**
* 删除一个有两个子节点的节点，就不能用它的一个子节点来代替它，而要用它的中序后继代替该节点 如何找？
* 首先，找到初始节点的右子节点rcn，然后转到rcn的左子节点(有的话)rcnl，然后转到rcnl的左子节点，直到结束。
* 这里实际上要找的是比初始节点值大的集合中最小的那一个 如果初始节点的右子节点没有左子节点，那么其本身就是后继
*/
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;
}
// 获取当前节点的中序后继
public Node getMidPostNode(Node delNode) {
Node successParent = delNode;
Node success = delNode;
Node current = delNode.rightChild;
while (current != null) {// 直到找到当前节点右子节点的最左子孙节点
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);
}
}
// 后续遍历
public void postTraverse(Node root) {
if (root != null) {
postTraverse(root.leftChild);
postTraverse(root.rightChild);
System.out.println(root.idata + " ");
}
}
// 递归地交换二叉树的左右子节点
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++)
System.out.print("|\t");
System.out.println("|-------"+root.idata);
}
else
System.out.println(root.idata);
printBinaryTree(root.leftChild, level+1);
}
}
class Node {
int idata;
Node leftChild;
Node rightChild;
}数据结构之二叉树的Java实现,布布扣,bubuko.com
原文：http://blog.csdn.net/laozhaokun/article/details/20529905