算法导论上二叉查找树的实现java(二)

public TreeNode treeSuccessor(TreeNode node) {// 找出中序条件下某节点的后续节点
		if (node == null)
			return null;
		if (node == treeMaxNode(root))// 此时有一种特殊情况，就是节点是最大元素的节点，则没有后续节点
			return null;
		if (node.rchild != null) // 当此节点右子树不为空
			return treeMinNode(node.rchild);
		else {// 当此节点右子树为空
			TreeNode parentNode = node.parent;
			while (parentNode != null && node == parentNode.rchild) {
				node = parentNode;
				parentNode = parentNode.parent;
			}
			return parentNode;
		}
	}

8、中序遍历此二叉查找树：

public void inOrderTranvers(TreeNode node) { // 这是二叉查找树的中序遍历
		if (node != null) {
			inOrderTranvers(node.lchild);
			nodelist.add(node);
			inOrderTranvers(node.rchild);
		}
	}

	public List
  
    inOrderTree() { // 获取二叉查找树中序遍历的节点，存在nodelist中
		if (nodelist != null)
			nodelist.clear();
		inOrderTranvers(root);
		return nodelist;
	}
  

public String printTree() { // 打印出此二叉查找树
		List
  
    ll = inOrderTree();
		Iterator
   
     it = ll.iterator(); StringBuilder sb = new StringBuilder(); while (it.hasNext()) { TreeNode p = (TreeNode) it.next(); sb.append(p.key + " "); } return sb.toString(); }
   
  

package binaryTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/*
 * 实现一个二叉查找数，实现插入、删除、查找等操作
 */
public class BinarySearchTree {
	private TreeNode root = null;// 定义树的根节点
	private List
  
    nodelist = new ArrayList
   
    ();// 遍历链表节点 // 构造二叉查找数的内部类,这就相当于C语言中的结构体 private class TreeNode { private int key; private TreeNode lchild; // 定义二叉查找树的左孩子节点 private TreeNode rchild;// 定义二叉查找树的右孩子节点 private TreeNode parent;// 定义二叉查找树的父亲节点 public TreeNode(int key, TreeNode lchild, TreeNode rchild, TreeNode parent) { this.key = key; this.lchild = lchild; this.rchild = rchild; this.parent = parent; } public int getKey() { return key; } } public boolean isEmpty() { // 判断此二叉查找树是否为空 return root == null; } public void treeInsert(int key) {// 实现二叉查找数的插入操作 TreeNode parentNode = null; TreeNode newNode = new TreeNode(key, null, null, null); TreeNode tmpNode = root; if (root == null) { root = newNode; return; } while (tmpNode != null) { // 一般情况下，我们不会插入树中已经存在的节点 parentNode = tmpNode;// 只是作为一个中间变量的节点 if (key < tmpNode.key) tmpNode = tmpNode.lchild; else if (key > tmpNode.key) tmpNode = tmpNode.rchild; else return; } if (key < parentNode.key) { parentNode.lchild = newNode; newNode.parent = parentNode; } else { parentNode.rchild = newNode; newNode.parent = parentNode; } } public TreeNode treeSearch(int key) { // 实现二叉查找树的查找操作 TreeNode tmpNode = root; while (tmpNode != null && tmpNode.key != key) { if (key < tmpNode.key) tmpNode = tmpNode.lchild; else tmpNode = tmpNode.rchild; } return tmpNode; } public TreeNode treeMinNode(TreeNode node) { // 获取此树中最小元素的节点 if (node == null) { System.out.println("此树为空!"); return null; } TreeNode tmpNode = node; while (tmpNode.lchild != null) tmpNode = tmpNode.lchild; return tmpNode; } public TreeNode treeMaxNode(TreeNode node) { // 获取此树中最大元素的节点 if (node == null) { System.out.println("此树为空!"); return null; } TreeNode tmpNode = node; while (tmpNode.rchild != null) tmpNode = tmpNode.rchild; return tmpNode; } public TreeNode treeSuccessor(TreeNode node) {// 找出中序条件下某节点的后续节点 if (node == null) return null; if (node == treeMaxNode(root))// 此时有一种特殊情况，就是节点是最大元素的节点，则没有后续节点 return null; if (node.rchild != null) // 当此节点右子树不为空 return treeMinNode(node.rchild); else {// 当此节点右子树为空 TreeNode parentNode = node.parent; while (parentNode != null && node == parentNode.rchild) { node = parentNode; parentNode = parentNode.parent; } return parentNode; } } public TreeNode treePrevious(TreeNode node) {// 找出中序条件下某节点的前续节点 if (node == null) return null; if (node == treeMinNode(root))// 此时有一种特殊情况，就是节点是最小元素的节点，则没有前续节点 return null; if (node.lchild != null) return treeMaxNode(node.lchild); else { TreeNode parentNode = node.parent; while (parentNode != null && node == parentNode.lchild) { node = parentNode; parentNode = parentNode.parent; } return parentNode; } } public void inOrderTranvers(TreeNode node) { // 这是二叉查找树的中序遍历 if (node != null) { inOrderTranvers(node.lchild); nodelist.add(node); inOrderTranvers(node.rchild); } } public List
    
      inOrderTree() { // 获取二叉查找树中序遍历的节点，存在nodelist中 if (nodelist != null) nodelist.clear(); inOrderTranvers(root); return nodelist; } public void treeDelete(int key) { TreeNode tmpNode = treeSearch(key); if (tmpNode == null) System.out.println("此树中没有你要删除的节点!"); delete(tmpNode); // 删除某一节点 } public void delete(TreeNode node) { // 删除节点的关键的核心函数 if (node == null) return; if (node.lchild == null && node.rchild == null) {// 如果被删除节点左右节点均为空 TreeNode parentNode = node.parent; if (node == parentNode.lchild) parentNode.lchild = null; else parentNode.rchild = null; return; } if (node.lchild != null && node.rchild == null) {// 左孩子不为空，右孩子为空 TreeNode parentNode = node.parent; if (node == parentNode.lchild) { parentNode.lchild = node.lchild; node.lchild.parent = parentNode; } else { parentNode.rchild = node.lchild; node.lchild.parent = parentNode; } return; } if (node.lchild == null && node.rchild != null) {// 左孩子为空，右孩子不为空 TreeNode parentNode = node.parent; if (node == parentNode.lchild) { parentNode.lchild = node.rchild; node.rchild.parent = parentNode; } else { parentNode.rchild = node.rchild; node.rchild