二叉树

二叉树的基本操作

1.      插入节点：

从根节点开始查找一个相应的节点，这个节点将成为新插入的节点的父节点。当父节点找到后，通过判断新节点的值比父节点的值的大小来决定是连接到左子节点还是右子节点。

2.      查找节点：

从根节点开始查找，如果查找的节点值比当前节点的值小，则继续查找其左子树，否则查找其右子树。

代码实现：

/*
 * 二叉树节点
 */
public class Node {
	//数据项
	public long data;
	//数据项
	public String sData;
	//左子节点
	public Node leftChild;
	//右子节点
	public Node rightChild;
	
	/**
	 * 构造方法
	 * @param data
	 */
	public Node(long data,String sData) {
		this.data = data;
		this.sData = sData;
	}
	
}

/*
 * 二叉树类
 */
public class Tree {
	//根节点
	public Node root;
	
	/**
	 * 插入节点
	 * @param value
	 */
	public void insert(long value,String sValue) {
		//封装节点
		Node newNode = new Node(value,sValue);
		//引用当前节点
		Node current = root;
		//引用父节点
		Node parent;
		//如果root为null，也就是第一插入的时候
		if(root == null) {
			root = newNode;
			return;
		} else {
			while(true) {
				//父节点指向当前节点
				parent = current;
				//如果当前指向的节点数据比插入的要大,则向左走
				if(current.data > value) {
					current = current.leftChild;
					if(current == null) {
						parent.leftChild = newNode;
						return;
					}
				} else {
					current = current.rightChild;
					if(current == null) {
						parent.rightChild = newNode;
						return;
					}
				}
			}
		}
	}
	
	/**
	 * 查找节点
	 * @param value
	 */
	public Node find(long value) {
		//引用当前节点，从根节点开始
		Node current = root;
		//循环，只要查找值不等于当前节点的数据项
		while(current.data != value) {
			//进行比较，比较查找值和当前节点的大小
			if(current.data > value) {
				current = current.leftChild;
			} else {
				current = current.rightChild;
			}
			//如果查找不到
			if(current == null) {
				return null;
			}
		}
		return current;
	}
	
	/**
	 * 删除节点
	 * @param value
	 */
	public void delte(long value) {
		
	}
	
}

public class TestTree {
	public static void main(String[] args) {
		Tree tree = new Tree();
		tree.insert(10,"James");
		tree.insert(20,"YAO");
		tree.insert(15,"Kobi");
		tree.insert(3,"Mac");
		
		System.out.println(tree.root.data);
		System.out.println(tree.root.rightChild.data);
		System.out.println(tree.root.rightChild.leftChild.data);
		System.out.println(tree.root.leftChild.data);
		
		Node node = tree.find(3);
		System.out.println(node.data + ", " + node.sData);
	}
}

10
20
15
3
3, Mac

二叉树的遍历

1.      遍历树

遍历树是根据一个特定的顺序访问树的每一个节点，根据顺序的不同分为前序、中序、后序遍历三种。

2.      前序遍历

（1）      访问根节点

（2）      前序遍历左子树

（3）      前序遍历右子树

前序遍历结果：30,15,10,18,40,34,45

3.      中序遍历

（1）      中序遍历左子树

（2）      访问根节点

（3）      中序遍历右子树

中序遍历结果：10,15,18,30,34,40,45排列顺序是从小到大的

4.      后序遍历

（1）      后序遍历左子树

（2）      后序遍历右子树

（3）      访问根节点

后序遍历结果：10,18,15,34,45,40,30

/*
 * 二叉树节点
 */
public class Node {
	//数据项
	public long data;
	//数据项
	public String sData;
	//左子节点
	public Node leftChild;
	//右子节点
	public Node rightChild;
	
	/**
	 * 构造方法
	 * @param data
	 */
	public Node(long data,String sData) {
		this.data = data;
		this.sData = sData;
	}
	
}

/*
 * 二叉树类
 */
public class Tree {
	//根节点
	public Node root;
	
	/**
	 * 插入节点
	 * @param value
	 */
	public void insert(long value,String sValue) {
		//封装节点
		Node newNode = new Node(value,sValue);
		//引用当前节点
		Node current = root;
		//引用父节点
		Node parent;
		//如果root为null，也就是第一插入的时候
		if(root == null) {
			root = newNode;
			return;
		} else {
			while(true) {
				//父节点指向当前节点
				parent = current;
				//如果当前指向的节点数据比插入的要大,则向左走
				if(current.data > value) {
					current = current.leftChild;
					if(current == null) {
						parent.leftChild = newNode;
						return;
					}
				} else {
					current = current.rightChild;
					if(current == null) {
						parent.rightChild = newNode;
						return;
					}
				}
			}
		}
	}
	
	/**
	 * 查找节点
	 * @param value
	 */
	public Node find(long value) {
		//引用当前节点，从根节点开始
		Node current = root;
		//循环，只要查找值不等于当前节点的数据项
		while(current.data != value) {
			//进行比较，比较查找值和当前节点的大小
			if(current.data > value) {
				current = current.leftChild;
			} else {
				current = current.rightChild;
			}
			//如果查找不到
			if(current == null) {
				return null;
			}
		}
		return current;
	}
	
	/**
	 * 删除节点
	 * @param value
	 */
	public void delte(long value) {
		
	}
	
	/**
	 * 前序遍历
	 */
	public void frontOrder(Node localNode) {
		if(localNode != null) {
			//访问根节点
			System.out.println(localNode.data + ", " + localNode.sData);
			//前序遍历左子树
			frontOrder(localNode.leftChild);
			//前序遍历右子树
			frontOrder(localNode.rightChild);
		}
	}
	
	/**
	 * 中序遍历
	 */
	public void inOrder(Node localNode) {
		if(localNode != null) {
			//中序遍历左子树
			inOrder(localNode.leftChild);
			//访问根节点
			System.out.println(localNode.data + ", " + localNode.sData);
			//中旬遍历右子树
			inOrder(localNode.rightChild);
		}
	}
	
	/**
	 * 后序遍历
	 */
	public void afterOrder(Node localNode) {
		if(localNode != null) {
			//后序遍历左子树
			afterOrder(localNode.leftChild);
			//后序遍历右子树
			afterOrder(localNode.rightChild);
			//访问根节点
			System.out.println(localNode.data + ", " + localNode.sData);
		}
	}
}

public class TestTree {
	public static void main(String[] args) {
		Tree tree = new Tree();
		tree.insert(10,"James");
		tree.insert(20,"YAO");
		tree.insert(15,"Kobi");
		tree.insert(3,"Mac");
		tree.insert(4, "Zhangsan");
		tree.insert(90, "Lisi");
		
		System.out.println("------前序遍历结果-------");
		tree.frontOrder(tree.root);
		System.out.println("------前序遍历结果-------");
		
		System.out.println("------中序遍历结果-------");
		tree.inOrder(tree.root);
		System.out.println("------中序遍历结果-------");
		
		System.out.println("------后序遍历结果-------");
		tree.afterOrder(tree.root);
		System.out.println("------后序遍历结果-------");
	}
}

------前序遍历结果-------
10, James
3, Mac
4, Zhangsan
20, YAO
15, Kobi
90, Lisi
------前序遍历结果-------
------中序遍历结果-------
3, Mac
4, Zhangsan
10, James
15, Kobi
20, YAO
90, Lisi
------中序遍历结果-------
------后序遍历结果-------
4, Zhangsan
3, Mac
15, Kobi
90, Lisi
20, YAO
10, James
------后序遍历结果-------

删除节点是二叉树操作中最复杂的。在删除之前首先要查找要删的节点。找到节点后，这个要删除的节点可能会有三种情况要考虑：

1.      该节点为叶子节点，没有子节点。

要删除叶节点，只需要改变该节点的父节点的引用值，将指向该节点的引用设置为null就可以了。

2.      该节点有一个子节点。

改变父节点的引用，将其直接指向要删除节点的子节点。

3.      该节点有两个子节点。

要删除有两个子节点的节点，就需要使用它的中序后继来替代该节点。

代码实现：

/*
 * 二叉树节点
 */
public class Node {
	//数据项
	public long data;
	//数据项
	public String sData;
	//左子节点
	public Node leftChild;
	//右子节点
	public Node rightChild;
	
	/**
	 * 构造方法
	 * @param data
	 */
	public Node(long data,String sData) {
		this.data = data;
		this.sData = sData;
	}
	
}

/*
 * 二叉树类
 */
public class Tree {
	//根节点
	public Node root;
	
	/**
	 * 插入节点
	 * @param value
	 */
	public void insert(long value,String sValue) {
		//封装节点
		Node newNode = new Node(value,sValue);
		//引用当前节点
		Node current = root;
		//引用父节点
		Node parent;
		//如果root为null，也就是第一插入的时候
		if(root == null) {
			root = newNode;
			return;
		} else {
			while(true) {
				//父节点指向当前节点
				parent = current;
				//如果当前指向的节点数据比插入的要大,则向左走
				if(current.data > value) {
					current = current.leftChild;
					if(current == null) {
						parent.leftChild = newNode;
						return;
					}
				} else {
					current = current.rightChild;
					if(current == null) {
						parent.rightChild = newNode;
						return;
					}
				}
			}
		}
	}
	
	/**
	 * 查找节点
	 * @param value
	 */
	public Node find(long value) {
		//引用当前节点，从根节点开始
		Node current = root;
		//循环，只要查找值不等于当前节点的数据项
		while(current.data != value) {
			//进行比较，比较查找值和当前节点的大小
			if(current.data > value) {
				current = current.leftChild;
			} else {
				current = current.rightChild;
			}
			//如果查找不到
			if(current == null) {
				return null;
			}
		}
		return current;
	}
	
	/**
	 * 删除节点
	 * @param value
	 */
	public boolean delete(long value) {
		//引用当前节点，从根节点开始
		Node current = root;
		
		//应用当前节点的父节点
		Node parent = root;
		//是否为左节点
		boolean isLeftChild = true;
		
		while(current.data != value) {
			parent = current;
			//进行比较，比较查找值和当前节点的大小
			if(current.data > value) {
				current = current.leftChild;
				isLeftChild = true;
			} else {
				current = current.rightChild;
				isLeftChild = false;
			}
			//如果查找不到
			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;
			}
		} else {
			Node successor = getSuccessor(current);
			if(current == root) {
				root = successor;
			} else if(isLeftChild) {
				parent.leftChild = successor;
			} else{
				parent.rightChild = successor;
			}
			successor.leftChild = current.leftChild;
		}
		
		return true;
		
		
	}
	
	public Node getSuccessor(Node delNode) {
		Node successor = delNode;
		Node successorParent = delNode;
		Node current = delNode.rightChild;
		
		while(current != null) {
			successorParent = successor;
			successor = current;
			current = current.leftChild;
		}
		
		if(successor != delNode.rightChild) {
			successorParent.leftChild = successor.rightChild;
			successor.rightChild = delNode.rightChild;
		}
		return successor;
	}
	
	/**
	 * 前序遍历
	 */
	public void frontOrder(Node localNode) {
		if(localNode != null) {
			//访问根节点
			System.out.println(localNode.data + ", " + localNode.sData);
			//前序遍历左子树
			frontOrder(localNode.leftChild);
			//前序遍历右子树
			frontOrder(localNode.rightChild);
		}
	}
	
	/**
	 * 中序遍历
	 */
	public void inOrder(Node localNode) {
		if(localNode != null) {
			//中序遍历左子树
			inOrder(localNode.leftChild);
			//访问根节点
			System.out.println(localNode.data + ", " + localNode.sData);
			//中旬遍历右子树
			inOrder(localNode.rightChild);
		}
	}
	
	/**
	 * 后序遍历
	 */
	public void afterOrder(Node localNode) {
		if(localNode != null) {
			//后序遍历左子树
			afterOrder(localNode.leftChild);
			//后序遍历右子树
			afterOrder(localNode.rightChild);
			//访问根节点
			System.out.println(localNode.data + ", " + localNode.sData);
		}
	}
}

public class TestTree {
	public static void main(String[] args) {
		Tree tree = new Tree();
		tree.insert(10,"James");
		tree.insert(20,"YAO");
		tree.insert(15,"Kobi");
		tree.insert(3,"Mac");
		tree.insert(4, "Zhangsan");
		tree.insert(90, "Lisi");
		
		tree.delete(90);
		tree.inOrder(tree.root);
	}
}

运行结果：

3, Mac
4, Zhangsan
10, James
15, Kobi
20, YAO