《java实现树和二叉树》

桃扇骨 2022-02-28 03:56 216阅读 0赞

### 《java实现树和二叉树》 ###

*  父节点表示树
 *  子节点表示树(未掌握)
 *  顺序存储二叉树
 *  链式存储二叉树
 *  三叉链表存储的二叉树
 *  哈夫曼树(带权路径最短的树) 未掌握
 *  排序二叉树(未掌握 重点)
 *  红黑树(未掌握)

# 父节点表示树 #

树中除根结点外每个结点都有一个父节点，要记录树中结点与结点直接的关系，只需要给每一个结点增加一个parent的父节点索引，根节点的parent索引为-1，如此将所有的结点存储于结点数组中，结点数组就是相当于一颗树。新增一个树结点只需要存入数据和parent索引，查找某个结点的所有子节点，只需要遍历所有结点的parent索引，相等即用List存储。  
  **如何遍历父节点表示树的深度(难点)**？遍历所有的结点数组array，得到结点的parent索引后p，看array\[p\]是否为空，或者p == -1，那么该次深度遍历结果结束，进行下一个结点自下而上计算深度，遍历出最大深度即是树的深度。

import java.util.ArrayList;
    import java.util.List;
    
    public class TreeParent<E>
    { 
    	public static class Node<T>
    	{ 
    		T data;
    		// 记录其父节点的位置
    		int parent;
    		public Node()
    		{ 
    		}
    		public Node(T data)
    		{ 
    			this.data = data;
    		}
    		public Node(T data , int parent)
    		{ 
    			this.data = data;
    			this.parent = parent;
    		}
    		public String toString()
    		{ 
    			return "TreeParent$Node[data=" + data
    				+ ", parent=" + parent + "]";
    		}
    	}
    	private final int DEFAULT_TREE_SIZE = 100;
    	private int treeSize = 0;
    	// 使用一个Node[]数组来记录该树里的所有节点
    	private Node<E>[] nodes;
    	// 记录节点数
    	private int nodeNums;
    	// 以指定根节点创建树
    	@SuppressWarnings("unchecked")
    	public TreeParent(E data)
    	{ 
    		treeSize = DEFAULT_TREE_SIZE;
    		nodes = new Node[treeSize];
    		nodes[0] = new Node<E>(data , -1);
    		nodeNums++;
    	}
    	// 以指定根节点、指定treeSize创建树
    	@SuppressWarnings("unchecked")
    	public TreeParent(E data ,int treeSize)
    	{ 
    		this.treeSize = treeSize;
    		nodes = new Node[treeSize];
    		nodes[0] = new Node<E>(data , -1);
    		nodeNums++;
    	}
    	// 为指定节点添加子节点
    	public void addNode(E data , Node parent)
    	{ 
    		for (int i = 0 ; i < treeSize ; i++)
    		{ 
    			// 找到数组中第一个为null的元素，该元素保存新节点
    			if (nodes[i] == null)
    			{ 
    				//创建新节点，并用指定的数组元素保存它
    				nodes[i] = new Node<E>(data , pos(parent));;
    				nodeNums++;
    				return;
    			}
    		}
    		throw new RuntimeException("该树已满，无法添加新节点");
    	}
    	// 判断树是否为空。
    	public boolean empty()
    	{ 
    		// 根节点是否为null
    		return nodes[0] == null;
    	}
    	// 返回根节点
    	public Node<E> root()
    	{ 
    		// 返回根节点
    		return nodes[0];
    	}
    	// 返回指定节点（非根节点）的父节点。
    	public Node<E> parent(Node node)
    	{ 
    		// 每个节点的parent记录了其父节点的位置
    		return nodes[node.parent];
    	}
    	// 返回指定节点（非叶子节点）的所有子节点。
    	public List<Node<E>> children(Node parent)
    	{ 
    		List<Node<E>> list = new ArrayList<Node<E>>();
    		for (int i = 0 ; i < treeSize  ; i++)
    		{ 
    			// 如果当前节点的父节点的位置等于parent节点的位置
    			if (nodes[i] != null &&
    				nodes[i].parent == pos(parent))
    			{ 
    				list.add(nodes[i]);
    			}
    		}
    		return list;
    	}
    	// 返回该树的深度。
    	public int deep()
    	{ 
    		// 用于记录节点的最大深度
    		int max = 0;
    		for(int i = 0 ; i < treeSize && nodes[i] != null
    			; i++)
    		{ 
    			// 初始化本节点的深度
    			int def = 1;
    			// m记录当前节点的父节点的位置
    			int m = nodes[i].parent;
    			// 如果其父节点存在
    			while(m != -1 && nodes[m] != null)
    			{ 
    				// 向上继续搜索父节点
    				m = nodes[m].parent;
    				def++;
    			}
    			if(max < def)
    			{ 
    				max = def;
    			}
    		}
    		// 返回最大深度
    		return max;
    	}
    	// 返回包含指定值的节点。
    	public int pos(Node node)
    	{ 
    		for (int i = 0 ; i < treeSize ; i++)
    		{ 
    			// 找到指定节点
    			if (nodes[i] == node)
    			{ 
    				return i;
    			}
    		}
    		return -1;
    	}
    	public static void main(String[] args)
    	{ 
    		TreeParent<String> tp = new TreeParent<String>("root");
    		TreeParent.Node root = tp.root();
    		System.out.println(root);
    		tp.addNode("节点1" , root);
    		System.out.println("此树的深度:" + tp.deep());
    		tp.addNode("节点2" , root);
    		// 获取根节点的所有子节点
    		List<TreeParent.Node<String>> nodes = tp.children(root);
    		System.out.println("根节点的第一个子节点：" + nodes.get(0));
    		// 为根节点的第一个子节点新增一个子节点
    		tp.addNode("节点3" , nodes.get(0));
    		System.out.println("此树的深度:" + tp.deep());
    	}
    }

运行结果：  
              ![在这里插入图片描述][20190324161854683.png]

# 子节点表示树(未掌握) #

父节点表示法思想是让每个节点都“记住”它父节点的索引，而子节点表示法，每个节点要记住多个子节点，则需要采用“子节点链”表示法。  
需要注意：

1.  TreeChild需要有两个内部类，SonNode与Node，其中SonNode是链表，只存储当前结点的index
2.  TreeChild中底层还是使用Node\[\]数组，Node中还有变量data存储数值
3.  TreeChild中添加一个结点时，add()函数要传入该结点值与结点的父节点，添加时要遍历所有的Node\[\]数组，如果有空，则新建Node存储于该位置，接下来需要看parent是否有子节点链，有则遍历子节点链到最后，维护该结点与父节点的关系。
4.  **递归求深度(难)：当每个结点的子树用链式存储，递归求树的深度比较复杂，每棵子树的深度为其所有子树的最大深度 + 1**

import java.util.*;
    
    public class TreeChild<E>
    { 
    	private static class SonNode
    	{ 
    		// 记录当前节点的位置
    		private int pos;
    		private SonNode next;
    		public SonNode(int pos , SonNode next)
    		{ 
    			this.pos = pos;
    			this.next = next;
    		}
    	}
    	public static class Node<T>
    	{ 
    		T data;
    		// 记录第一个子节点
    		SonNode first;
    		public Node(T data)
    		{ 
    			this.data = data;
    			this.first = null;
    		}
    		public String toString()
    		{ 
    			if (first != null)
    			{ 
    				return "TreeChild$Node[data=" + data
    					+ ", first=" + first.pos + "]";
    			}
    			else
    			{ 
    				return "TreeChild$Node[data=" + data + ", first=-1]";
    			}
    		}
    	}
    	private final int DEFAULT_TREE_SIZE = 100;
    	private int treeSize = 0;
    	// 使用一个Node[]数组来记录该树里的所有节点
    	private Node<E>[] nodes;
    	// 记录节点数
    	private int nodeNums;
    	// 以指定根节点创建树
    	@SuppressWarnings("unchecked")
    	public TreeChild(E data)
    	{ 
    		treeSize = DEFAULT_TREE_SIZE;
    		nodes = new Node[treeSize];
    		nodes[0] = new Node<E>(data);
    		nodeNums++;
    	}
    	// 以指定根节点、指定treeSize创建树
    	@SuppressWarnings("unchecked")
    	public TreeChild(E data ,int treeSize)
    	{ 
    		this.treeSize = treeSize;
    		nodes = new Node[treeSize];
    		nodes[0] = new Node<E>(data);
    		nodeNums++;
    	}
    	// 为指定节点添加子节点
    	public void addNode(E data , Node parent)
    	{ 
    		for (int i = 0 ; i < treeSize ; i++)
    		{ 
    			// 找到数组中第一个为null的元素，该元素保存新节点
    			if (nodes[i] == null)
    			{ 
    				// 创建新节点，并用指定数组元素来保存它
    				nodes[i] = new Node<E>(data);
    				if (parent.first == null)
    				{ 
    					parent.first = new SonNode(i , null);
    				}
    				else
    				{ 
    					SonNode next = parent.first;
    					while (next.next != null)
    					{ 
    						next = next.next;
    					}
    					next.next = new SonNode(i , null);
    				}
    				nodeNums++;
    				return;
    			}
    		}
    		throw new RuntimeException("该树已满，无法添加新节点");
    	}
    	// 判断树是否为空。
    	public boolean empty()
    	{ 
    		// 根节点是否为null
    		return nodes[0] == null;
    	}
    	// 返回根节点
    	public Node<E> root()
    	{ 
    		// 返回根节点
    		return nodes[0];
    	}
    	// 返回指定节点（非叶子节点）的所有子节点。
    	public List<Node<E>> children(Node parent)
    	{ 
    		List<Node<E>> list = new ArrayList<Node<E>>();
    		// 获取parent节点的第一个子节点
    		SonNode next = parent.first;
    		// 沿着孩子链不断搜索下一个孩子节点
    		while (next != null)
    		{ 
    			// 添加孩子链中的节点
    			list.add(nodes[next.pos]);
    			next = next.next;
    		}
    		return list;
    	}
    	// 返回指定节点（非叶子节点）的第index个子节点。
    	public Node<E> child(Node parent , int index)
    	{ 
    		// 获取parent节点的第一个子节点
    		SonNode next = parent.first;
    		// 沿着孩子链不断搜索下一个孩子节点
    		for (int i = 0 ; next != null  ; i++)
    		{ 
    			if (index == i)
    			{ 
    				return nodes[next.pos];
    			}
    			next = next.next;
    		}
    		return null;
    	}
    	// 返回该树的深度。
    	public int deep()
    	{ 
    		// 获取该树的深度
    		return deep(root());
    	}
    	// 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1
    	private int deep(Node node)
    	{ 
    		if (node.first == null)
    		{ 
    			return 1;
    		}
    		else
    		{ 
    			// 记录其所有子树的最大深度
    			int max = 0;
    			SonNode next = node.first;
    			// 沿着孩子链不断搜索下一个孩子节点
    			while (next != null)
    			{ 
    				// 获取以其子节点为根的子树的深度
    				int tmp = deep(nodes[next.pos]);
    				if (tmp > max)
    				{ 
    					max = tmp;
    				}
    				next = next.next;
    			}
    			// 最后返回其所有子树的最大深度 + 1
    			return max + 1;
    		}
    	}
    	// 返回包含指定值的节点。
    	public int pos(Node node)
    	{ 
    		for (int i = 0 ; i < treeSize ; i++)
    		{ 
    			// 找到指定节点
    			if (nodes[i] == node)
    			{ 
    				return i;
    			}
    		}
    		return -1;
    	}
    	public static void main(String[] args)
    	{ 
    		TreeChild<String> tp = new TreeChild<String>("root");
    		TreeChild.Node root = tp.root();
    		System.out.println("根节点：" + root);
    		tp.addNode("节点1" , root);
    		tp.addNode("节点2" , root);
    		tp.addNode("节点3" , root);
    		System.out.println("添加子节点后的根节点：" + root);
    		System.out.println("此树的深度:" + tp.deep());
    		// 获取根节点的所有子节点
    		List<TreeChild.Node<String>> nodes = tp.children(root);
    		System.out.println("根节点的第一个子节点：" + nodes.get(0));
    		// 为根节点的第一个子节点新增一个子节点
    		tp.addNode("节点4" , nodes.get(0));
    		System.out.println("根节点的第一个子节点：" + nodes.get(0));
    		System.out.println("此树的深度:" + tp.deep());
    	}
    }

运行结果：  
            ![在这里插入图片描述][20190325152837475.png]

# 顺序存储二叉树 #

顺序存储二叉树是最简单实现的二叉树，思想是将树中不同的节点存入数组的固定的位置。比如，根节点永远使用数组的第一个元素来保存，第二层的第2个节点，永远使用数组的第3个元素来保存:第三层最右边的节点，永远使用数组的第7个元素来保存，一依此类推。但是还是要初始化顺序存储二叉树的数组大小，每次添加结点传入参数父节点的index，以及该结点是父节点的左结点还是右结点，决定了存储在Object\[2*index +1\]还是在Object\[2*index +2\]中。

public class ArrayBinTree<T>
    { 
    	// 使用数组来记录该树的所有节点
    	private Object[] datas;
    	private int DEFAULT_DEEP = 8;
    	// 保存该树的深度
    	private int deep;
    	private int arraySize;
    	// 以默认的深度来创建二叉树
    	public ArrayBinTree()
    	{ 
    		this.deep = DEFAULT_DEEP;
    		this.arraySize = (int)Math.pow(2 , deep) - 1;
    		datas = new Object[arraySize];
    	}
    	// 以指定深度来创建二叉树
    	public ArrayBinTree(int deep)
    	{ 
    		this.deep = deep;
    		this.arraySize = (int)Math.pow(2 , deep) - 1;
    		datas = new Object[arraySize];
    	}
    	// 以指定深度,指定根节点创建二叉树
    	public ArrayBinTree(int deep , T data)
    	{ 
    		this.deep = deep;
    		this.arraySize = (int)Math.pow(2 , deep) - 1;
    		datas = new Object[arraySize];
    		datas[0] = data;
    	}
    	/** * 为指定节点添加子节点。 * @param index 需要添加子节点的父节点的索引 * @param data 新子节点的数据 * @param left 是否为左节点 */
    	public void add(int index , T data , boolean left)
    	{ 
    		if (datas[index] == null)
    		{ 
    			throw new RuntimeException(index + "处节点为空，无法添加子节点");
    		}
    		if (2 * index + 1 >= arraySize)
    		{ 
    			throw new RuntimeException("树底层的数组已满，树越界异常");
    		}
    		// 添加左子节点
    		if (left)
    		{ 
    			datas[2 * index + 1] = data;
    		}
    		else
    		{ 
    			datas[2 * index + 2] = data;
    		}
    	}
    	// 判断二叉树是否为空。
    	public boolean empty()
    	{ 
    		// 根据根元素来判断二叉树是否为空
    		return datas[0] == null;
    	}
    	// 返回根节点。
    	@SuppressWarnings("unchecked")
    	public T root()
    	{ 
    		return (T)datas[0] ;
    	}
    	// 返回指定节点（非根节点）的父节点。
    	@SuppressWarnings("unchecked")
    	public T parent(int index)
    	{ 
    		return (T)datas[(index - 1) / 2] ;
    	}
    	// 返回指定节点（非叶子）的左子节点。
    	// 当左子节点不存在时返回null。
    	@SuppressWarnings("unchecked")
    	public T left(int index)
    	{ 
    		if (2 * index + 1 >= arraySize)
    		{ 
    			throw new RuntimeException("该节点为叶子节点，无子节点");
    		}
    		return (T)datas[index * 2 + 1] ;
    	}
    	// 返回指定节点（非叶子）的右子节点。
    	// 当右子节点不存在时返回null。
    	@SuppressWarnings("unchecked")
    	public T right(int index)
    	{ 
    		if (2 * index + 1 >= arraySize)
    		{ 
    			throw new RuntimeException("该节点为叶子节点，无子节点");
    		}
    		return (T)datas[index * 2 + 2] ;
    	}
    	// 返回该二叉树的深度。
    	public int deep(int index)
    	{ 
    		return deep;
    	}
    	// 返回指定节点的位置。
    	public int pos(T data)
    	{ 
    		// 该循环实际上就是按广度遍历来搜索每个节点
    		for (int i = 0 ; i < arraySize ; i++)
    		{ 
    			if (datas[i].equals(data))
    			{ 
    				return i;
    			}
    		}
    		return -1;
    	}
    	public String toString()
    	{ 
    		return java.util.Arrays.toString(datas);
    	}
    	public static void main(String[] args)
    	{ 
    		ArrayBinTree<String> binTree =
    			new ArrayBinTree<String>(4, "根");
    		binTree.add(0 , "第二层右子节点" , false);
    		binTree.add(2 , "第三层右子节点" , false);
    		binTree.add(6 , "第四层右子节点" , false);
    		System.out.println(binTree);
    	}
    }

运行结果：  
![在这里插入图片描述][20190325154423133.png]

# 链式存储二叉树 #

二叉树存储添加结点，除了指定结点的数据，还需要指定父节点，以及插入的该结点是否为左结点。二叉树链式存储有左右子节点，递归求树的深度会相对容易。

public class TwoLinkBinTree<E>
    { 
    	public static class TreeNode
    	{ 
    		Object data;
    		TreeNode left;
    		TreeNode right;
    		public TreeNode()
    		{ 
    		}
    		public TreeNode(Object data)
    		{ 
    			this.data = data;
    		}
    		public TreeNode(Object data , TreeNode left
    			, TreeNode right)
    		{ 
    			this.data = data;
    			this.left = left;
    			this.right = right;
    		}
    	}
    	private TreeNode root;
    	// 以默认的构造器来创建二叉树
    	public TwoLinkBinTree()
    	{ 
    		this.root = new TreeNode();
    	}
    	// 以指定根元素来创建二叉树
    	public TwoLinkBinTree(E data)
    	{ 
    		this.root = new TreeNode(data);
    	}
    	/** * 为指定节点添加子节点。 * @param index 需要添加子节点的父节点的索引 * @param data 新子节点的数据 * @param isLeft 是否为左节点 * @return 新增的节点 */
    	public TreeNode addNode(TreeNode parent , E data
    		, boolean isLeft)
    	{ 
    		if (parent == null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点为null，无法添加子节点");
    		}
    		if (isLeft && parent.left != null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点已有左子节点，无法添加左子节点");
    		}
    		if (!isLeft && parent.right != null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点已有右子节点，无法添加右子节点");
    		}
    		TreeNode newNode = new TreeNode(data);
    		if (isLeft)
    		{ 
    			// 让父节点的left引用指向新节点
    			parent.left = newNode;
    		}
    		else
    		{ 
    			// 让父节点的right引用指向新节点
    			parent.right = newNode;
    		}
    		return newNode;
    	}
    	// 判断二叉树是否为空。
    	public boolean empty()
    	{ 
    		// 根据根元素来判断二叉树是否为空
    		return root.data == null;
    	}
    	// 返回根节点。
    	public TreeNode root()
    	{ 
    		if (empty())
    		{ 
    			throw new RuntimeException("树为空，无法访问根节点");
    		}
    		return root;
    	}
    	// 返回指定节点（非根节点）的父节点。
    	public E parent(TreeNode node)
    	{ 
    		// 对于二叉链表存储法，如果要访问指定节点的父节点必须遍历二叉树
    		return null;
    	}
    	// 返回指定节点（非叶子）的左子节点。当左子节点不存在时返回null
    	@SuppressWarnings("unchecked")
    	public E leftChild(TreeNode parent)
    	{ 
    		if (parent == null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点为null，无法添加子节点");
    		}
    		return parent.left == null ? null : (E)parent.left.data;
    	}
    	// 返回指定节点（非叶子）的右子节点。当右子节点不存在时返回null
    	@SuppressWarnings("unchecked")
    	public E rightChild(TreeNode parent)
    	{ 
    		if (parent == null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点为null，无法添加子节点");
    		}
    		return parent.right == null ? null : (E)parent.right.data;
    	}
    	// 返回该二叉树的深度。
    	public int deep()
    	{ 
    		// 获取该树的深度
    		return deep(root);
    	}
    	// 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1
    	private int deep(TreeNode node)
    	{ 
    		if (node == null)
    		{ 
    			return 0;
    		}
    		// 没有子树
    		if (node.left == null
    			&& node.right == null)
    		{ 
    			return 1;
    		}
    		else
    		{ 
    			int leftDeep = deep(node.left);
    			int rightDeep = deep(node.right);
    			// 记录其所有左、右子树中较大的深度
    			int max = leftDeep > rightDeep ?
    				leftDeep : rightDeep;
    			// 返回其左右子树中较大的深度 + 1
    			return max + 1;
    		}
    	}
    	public static void main(String[] args)
    	{ 
    		TwoLinkBinTree<String> binTree = new TwoLinkBinTree<>("根节点");
    		// 依次添加节点
    		TwoLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root()
    			,  "第二层左节点" , true);
    		TwoLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root()
    			, "第二层右节点" ,false );
    		TwoLinkBinTree.TreeNode tn3 = binTree.addNode(tn2
    			, "第三层左节点" , true);
    		TwoLinkBinTree.TreeNode tn4 = binTree.addNode(tn2
    			, "第三层右节点" , false);
    		TwoLinkBinTree.TreeNode tn5 = binTree.addNode(tn3
    			, "第四层左节点" , true);
    		System.out.println("tn2的左子节点：" + binTree.leftChild(tn2));
    		System.out.println("tn2的右子节点：" + binTree.rightChild(tn2));
    		System.out.println(binTree.deep());
    	}
    }

运行结果：  
                ![在这里插入图片描述][20190325161712173.png]

# 三叉链表存储的二叉树 #

三叉链表存储相对于二叉链存储多了指向父节点的指针，只是在增加删除时需要多维护一下parent。

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Queue;
    public class ThreeLinkBinTree<E>
    { 
    	public static class TreeNode
    	{ 
    		Object data;
    		TreeNode left;
    		TreeNode right;
    		TreeNode parent;
    		public TreeNode()
    		{ 
    		}
    		public TreeNode(Object data)
    		{ 
    			this.data = data;
    		}
    		public TreeNode(Object data , TreeNode left
    			, TreeNode right , TreeNode parent)
    		{ 
    			this.data = data;
    			this.left = left;
    			this.right = right;
    			this.parent = parent;
    		}
    		public String toString()
    		{ 
    			return "TreeNode[data=" + data + "]";
    		}
    	}
    	private TreeNode root;
    	// 以默认的构造器来创建二叉树
    	public ThreeLinkBinTree()
    	{ 
    		this.root = new TreeNode();
    	}
    	// 以指定根元素来创建二叉树
    	public ThreeLinkBinTree(E data)
    	{ 
    		this.root = new TreeNode(data);
    	}
    	/** * 为指定节点添加子节点。 * @param index 需要添加子节点的父节点的索引 * @param data 新子节点的数据 * @param isLeft 是否为左节点 * @return 新增的节点 */
    	public TreeNode addNode(TreeNode parent , E data
    		, boolean isLeft)
    	{ 
    		if (parent == null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点为null，无法添加子节点");
    		}
    		if (isLeft && parent.left != null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点已有左子节点，无法添加左子节点");
    		}
    		if (!isLeft && parent.right != null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点已有右子节点，无法添加右子节点");
    		}
    		TreeNode newNode = new TreeNode(data);
    		if (isLeft)
    		{ 
    			// 让父节点的left引用指向新节点
    			parent.left = newNode;
    		}
    		else
    		{ 
    			// 让父节点的right引用指向新节点
    			parent.right = newNode;
    		}
    		// 让新节点的parent引用到parent节点
    		newNode.parent = parent;
    		return newNode;
    	}
    	// 判断二叉树是否为空。
    	public boolean empty()
    	{ 
    		// 根据根元素来判断二叉树是否为空
    		return root.data == null;
    	}
    	// 返回根节点。
    	public TreeNode root()
    	{ 
    		if (empty())
    		{ 
    			throw new RuntimeException("树为空，无法访问根节点");
    		}
    		return root;
    	}
    	// 返回指定节点（非根节点）的父节点。
    	@SuppressWarnings("unchecked")
    	public E parent(TreeNode node)
    	{ 
    		if (node == null)
    		{ 
    			throw new RuntimeException(node +
    				"节点为null，无法访问其父节点");
    		}
    		return (E)node.parent.data;
    	}
    	// 返回指定节点（非叶子）的左子节点，当左子节点不存在时返回null
    	@SuppressWarnings("unchecked")
    	public E leftChild(TreeNode parent)
    	{ 
    		if (parent == null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点为null，无法添加子节点");
    		}
    		return parent.left == null ? null : (E)parent.left.data;
    	}
    	// 返回指定节点（非叶子）的右子节点，当右子节点不存在时返回null
    	@SuppressWarnings("unchecked")
    	public E rightChild(TreeNode parent)
    	{ 
    		if (parent == null)
    		{ 
    			throw new RuntimeException(parent +
    				"节点为null，无法添加子节点");
    		}
    		return parent.right == null ? null : (E)parent.right.data;
    	}
    	// 返回该二叉树的深度。
    	public int deep()
    	{ 
    		// 获取该树的深度
    		return deep(root);
    	}
    	// 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1
    	private int deep(TreeNode node)
    	{ 
    		if (node == null)
    		{ 
    			return 0;
    		}
    		// 没有子树
    		if (node.left == null
    			&& node.right == null)
    		{ 
    			return 1;
    		}
    		else
    		{ 
    			int leftDeep = deep(node.left);
    			int rightDeep = deep(node.right);
    			// 记录其所有左、右子树中较大的深度
    			int max = leftDeep > rightDeep ?
    				leftDeep : rightDeep;
    			// 返回其左右子树中较大的深度 + 1
    			return max + 1;
    		}
    	}
    	// 实现先序遍历
    	public List<TreeNode> preIterator()
    	{ 
    		return preIterator(root);
    	}
    	private List<TreeNode> preIterator(TreeNode node)
    	{ 
    		List<TreeNode> list = new ArrayList<TreeNode>();
    		// 处理根节点
    		list.add(node);
    		// 递归处理左子树
    		if (node.left != null)
    		{ 
    			list.addAll(preIterator(node.left));
    		}
    		// 递归处理右子树
    		if (node.right != null)
    		{ 
    			list.addAll(preIterator(node.right));
    		}
    		return list;
    	}
    	// 实现中序遍历
    	public List<TreeNode> inIterator()
    	{ 
    		return inIterator(root);
    	}
    	private List<TreeNode> inIterator(TreeNode node)
    	{ 
    		List<TreeNode> list = new ArrayList<TreeNode>();
    		// 递归处理左子树
    		if (node.left != null)
    		{ 
    			list.addAll(inIterator(node.left));
    		}
    		// 处理根节点
    		list.add(node);
    		// 递归处理右子树
    		if (node.right != null)
    		{ 
    			list.addAll(inIterator(node.right));
    		}
    		return list;
    	}
    	public List<TreeNode> postIterator()
    	{ 
    		return postIterator(root);
    	}
    	// 实现后序遍历
    	private List<TreeNode> postIterator(TreeNode node)
    	{ 
    		List<TreeNode> list = new ArrayList<TreeNode>();
    		// 递归处理左子树
    		if (node.left != null)
    		{ 
    			list.addAll(postIterator(node.left));
    		}
    		// 递归处理右子树
    		if (node.right != null)
    		{ 
    			list.addAll(postIterator(node.right));
    		}
    		// 处理根节点
    		list.add(node);
    		return list;
    	}
    	// 广度优先遍历
    	public List<TreeNode> breadthFirst()
    	{ 
    		Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
    		List<TreeNode> list = new ArrayList<TreeNode>();
    		if( root != null)
    		{ 
    			// 将根元素加入“队列”
    			queue.offer(root);
    		}
    		while(!queue.isEmpty())
    		{ 
    			// 将该队列的“头部”的元素添加到List中
    			list.add(queue.peek());
    			// 将该队列的“头部”的元素移出队列
    			TreeNode p = queue.poll();
    			// 如果左子节点不为null，将它加入“队列”
    			if(p.left != null)
    			{ 
    				queue.offer(p.left);
    			}
    			// 如果右子节点不为null，将它加入“队列”
    			if(p.right != null)
    			{ 
    				queue.offer(p.right);
    			}
    		}
    		return list;
    	}
    	public static void main(String[] args)
    	{ 
    		ThreeLinkBinTree<String> binTree = new ThreeLinkBinTree<>("根节点");
    		// 依次添加节点
    		ThreeLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root()
    			,  "二左" , true);
    		ThreeLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root()
    			, "二右" ,false );
    		ThreeLinkBinTree.TreeNode tn3 = binTree.addNode(tn1
    			, "三左" , true);
    		ThreeLinkBinTree.TreeNode tn4 = binTree.addNode(tn1
    			, "三右" , false);
    		ThreeLinkBinTree.TreeNode tn5 = binTree.addNode(tn3
    			, "四右" , false);
    		ThreeLinkBinTree.TreeNode tn6 = binTree.addNode(tn4
    			, "四右左" , true);
    		ThreeLinkBinTree.TreeNode tn7 = binTree.addNode(tn4
    			, "四右右" , false);
    		ThreeLinkBinTree.TreeNode tn8 = binTree.addNode(tn5
    			, "五左" , true);
    		ThreeLinkBinTree.TreeNode tn9 = binTree.addNode(tn5
    			, "五右" , false);
    		System.out.println(binTree.preIterator());
    		System.out.println(binTree.inIterator());
    		System.out.println(binTree.postIterator());
    		System.out.println(binTree.breadthFirst());
    
    	}
    }

运行结果：  
![在这里插入图片描述][20190325162800445.png]

# 哈夫曼树(带权路径最短的树) 未掌握 #

节点的带权路径长度:从该节点到根节点之间的路径长度与节点的权的乘积。图11.16表示节点到根结点的路径长度，图11.17树的带权路径长度。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]  
对于哈夫曼树，有一个很重要的定理：对于具有n个叶子节点的哈夫曼树.一共需要2*n-1个节点。因为对于二叉树来说，有三种类型节点，即度数为2的节点、度数为1的节点和度数为0的叶子节点，而哈夫曼树的非叶子节点都是由两个节点合并产生的，所以不会出现度数为1的节点。而生成的非叶子节点的个数为叶子节点个数一1，因此n个叶子节点的哈夫曼树，一共需要2*n一l个节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]  
例如下图：先找出最小两个结点即2、4，然后作为一颗二叉树，然后将两者和加入到原来的数组中，而除掉2、4结点，此时数组中有7、6、5，在选出数组最小的两个值作为二叉树左右结点，即5和、6，然后5+6 = 11，再次重复，最后得到的根结点权重18。创建哈夫曼树需要事先创建结点数组，结点Node用二叉链链式存储结构。  
难点：每次需要对节点数组进行排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 2]

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Queue;
    
    public class HuffmanTree
    { 
    	public static class Node<E>
    	{ 
    		E data;
    		double weight;
    		Node<E> leftChild;
    		Node<E> rightChild;
    		public Node(E data , double weight)
    		{ 
    			this.data = data;
    			this.weight = weight;
    		}
    		public String toString()
    		{ 
    			return "Node[data=" + data
    				+ ", weight=" + weight + "]";
    		}
    	}
    	public static void main(String[] args)
    	{ 
    		List<Node<String>> nodes = new ArrayList<>();
    		nodes.add(new Node<String>("A" , 40.0));
    		nodes.add(new Node<String>("B" , 7.0));
    		nodes.add(new Node<String>("C" , 10.0));
    		nodes.add(new Node<String>("D" , 30.0));
    		nodes.add(new Node<String>("E" , 12.0));
    		nodes.add(new Node<String>("F" , 2.0));
    		Node<String> root = HuffmanTree.createTree(nodes);
    		System.out.println(breadthFirst(root));
    	}
    	/** * 构造哈夫曼树 * @param nodes 节点集合 * @return 构造出来的哈夫曼树的根节点 */
    	private static <E> Node<E> createTree(List<Node<E>> nodes)
    	{ 
    		// 只要nodes数组中还有2个以上的节点
    		while (nodes.size() > 1)
    		{ 
    			quickSort(nodes);
    			// 获取权值最小的两个节点
    			Node<E> left = nodes.get(nodes.size() - 1);
    			Node<E> right = nodes.get(nodes.size() - 2);
    			// 生成新节点，新节点的权值为两个子节点的权值之和
    			Node<E> parent = new Node<>(null , left.weight + right.weight);
    			// 让新节点作为权值最小的两个节点的父节点
    			parent.leftChild = left;
    			parent.rightChild = right;
    			// 删除权值最小的两个节点
    			nodes.remove(nodes.size() - 1);
    			nodes.remove(nodes.size() - 1);
    			// 将新生成的父节点添加到集合中
    			nodes.add(parent);
    		}
    		// 返回nodes集合中唯一的节点，也就是根节点
    		return nodes.get(0);
    	}
    	// 将指定数组的i和j索引处的元素交换
    	private static <E> void swap(List<Node<E>> nodes, int i, int j)
    	{ 
    		Node<E> tmp;
    		tmp = nodes.get(i);
    		nodes.set(i , nodes.get(j));
    		nodes.set(j , tmp);
    	}
    	// 实现快速排序算法，用于对节点进行排序
    	private static <E> void subSort(List<Node<E>> nodes
    		, int start , int end)
    	{ 
    		// 需要排序
    		if (start < end)
    		{ 
    			// 以第一个元素作为分界值
    			Node base = nodes.get(start);
    			// i从左边搜索，搜索大于分界值的元素的索引
    			int i = start;
    			// j从右边开始搜索，搜索小于分界值的元素的索引
    			int j = end + 1;
    			while(true)
    			{ 
    				// 找到大于分界值的元素的索引，或i已经到了end处
    				while(i < end && nodes.get(++i).weight >= base.weight);
    				// 找到小于分界值的元素的索引，或j已经到了start处
    				while(j > start && nodes.get(--j).weight <= base.weight);
    				if (i < j)
    				{ 
    					swap(nodes , i , j);
    				}
    				else
    				{ 
    					break;
    				}
    			}
    			swap(nodes , start , j);
    			// 递归左子序列
    			subSort(nodes , start , j - 1);
    			// 递归右边子序列
    			subSort(nodes , j + 1, end);
    		}
    	}
    	public static <E> void quickSort(List<Node<E>> nodes)
    	{ 
    		subSort(nodes , 0 , nodes.size() - 1);
    	}
    	// 广度优先遍历
    	public static List<Node> breadthFirst(Node root)
    	{ 
    		Queue<Node> queue = new ArrayDeque<Node>();
    		List<Node> list = new ArrayList<Node>();
    		if( root != null)
    		{ 
    			// 将根元素入“队列”
    			queue.offer(root);
    		}
    		while(!queue.isEmpty())
    		{ 
    			// 将该队列的“队尾”的元素添加到List中
    			list.add(queue.peek());
    			Node p = queue.poll();
    			// 如果左子节点不为null，将它加入“队列”
    			if(p.leftChild != null)
    			{ 
    				queue.offer(p.leftChild);
    			}
    			// 如果右子节点不为null，将它加入“队列”
    			if(p.rightChild != null)
    			{ 
    				queue.offer(p.rightChild);
    			}
    		}
    		return list;
    	}
    }

运行结果：  
![在这里插入图片描述][20190325180136783.png]

# 排序二叉树(未掌握 重点) #

对于排序二叉树，若按中序遍历就可以得到由小到大的有序序列。

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Queue;
    
    public class SortedBinTree<T extends Comparable>
    { 
    	static class Node
    	{ 
    		Object data;
    		Node parent;
    		Node left;
    		Node right;
    		public Node(Object data , Node parent
    			, Node left , Node right)
    		{ 
    			this.data = data;
    			this.parent = parent;
    			this.left = left;
    			this.right = right;
    		}
    		public String toString()
    		{ 
    			return "[data=" + data + "]";
    		}
    		public boolean equals(Object obj)
    		{ 
    			if (this == obj)
    			{ 
    				return true;
    			}
    			if (obj.getClass() == Node.class)
    			{ 
    				Node target = (Node)obj;
    				return data.equals(target.data)
    					&& left == target.left
    					&& right == target.right
    					&& parent == target.parent;
    			}
    			return false;
    		}
    	}
    	private Node root;
    	// 两个构造器用于创建排序二叉树
    	public SortedBinTree()
    	{ 
    		root = null;
    	}
    	public SortedBinTree(T o)
    	{ 
    		root = new Node(o , null , null , null);
    	}
    	// 添加节点
    	@SuppressWarnings("unchecked")
    	public void add(T ele)
    	{ 
    		// 如果根节点为null
    		if (root == null)
    		{ 
    			root = new Node(ele , null , null , null);
    		}
    		else
    		{ 
    			Node current = root;
    			Node parent = null;
    			int cmp = 0;
    			// 搜索合适的叶子节点，以该叶子节点为父节点添加新节点
    			do
    			{ 
    				parent = current;
    				cmp = ele.compareTo(current.data);
    				// 如果新节点的值大于当前节点的值
    				if (cmp > 0)
    				{ 
    					// 以右子节点作为当前节点
    					current = current.right;
    				}
    				// 如果新节点的值小于当前节点的值
    				else
    				{ 
    					// 以左子节点作为当前节点
    					current = current.left;
    				}
    			}
    			while (current != null);
    			// 创建新节点
    			Node newNode = new Node(ele , parent , null , null);
    			// 如果新节点的值大于父节点的值
    			if (cmp > 0)
    			{ 
    				// 新节点作为父节点的右子节点
    				parent.right = newNode;
    			}
    			// 如果新节点的值小于父节点的值
    			else
    			{ 
    				// 新节点作为父节点的左子节点
    				parent.left = newNode;
    			}
    		}
    	}
    	// 删除节点
    	public void remove(T ele)
    	{ 
    		// 获取要删除的节点
    		Node target = getNode(ele);
    		// 如果要删除的节点为null，直接返回
    		if (target == null)
    		{ 
    			return;
    		}
    		// 如果要删除的节点的左、右子树为空
    		if (target.left == null
    			&& target.right == null)
    		{ 
    			// 如果要删除节点是根节点
    			if (target == root)
    			{ 
    				root = null;
    			}
    			else
    			{ 
    				// 要删除节点是父节点的左子节点
    				if (target == target.parent.left)
    				{ 
    					// 将target的父节点的left设为null
    					target.parent.left = null;
    				}
    				// 要删除节点是父节点的左子节点
    				else
    				{ 
    					// 将target的父节点的right设为null
    					target.parent.right = null;
    				}
    				target.parent = null;
    			}
    		}
    		// 如果要删除的节点只有右子树
    		else if (target.left == null
    			&& target.right != null)
    		{ 
    			// 如果要删除节点是根节点
    			if (target == root)
    			{ 
    				root = target.right;
    			}
    			else
    			{ 
    				// 如果要删除节点是父节点的左子节点
    				if (target == target.parent.left)
    				{ 
    					// 让target的父节点的left指向target的右子树
    					target.parent.left = target.right;
    				}
    				// 如果要删除节点是父节点的右子节点
    				else
    				{ 
    					// 让target的父节点的right指向target的右子树
    					target.parent.right = target.right;
    				}
    				//让target的右子树的parent指向target的parent
    				target.right.parent = target.parent;
    			}
    		}
    		// 如果要删除的节点只有左子树
    		else if(target.left != null
    			&& target.right == null)
    		{ 
    			// 被删除节点是根节点
    			if (target == root)
    			{ 
    				root = target.left;
    			}
    			else
    			{ 
    				// 被删除节点是父节点的左子节点
    				if (target == target.parent.left)
    				{ 
    					// 让target的父节点的left指向target的左子树
    					target.parent.left = target.left;
    				}
    				else
    				{ 
    					// 让target的父节点的right指向target的左子树
    					target.parent.right = target.left;
    				}
    				// 让target的左子树的parent指向target的parent
    				target.left.parent = target.parent;
    			}
    		}
    		// 如果要删除节点既有左子树，又有右子树
    		else
    		{ 
    			// leftMaxNode用于保存target节点的左子树中值最大的节点
    			Node leftMaxNode = target.left;
    			// 搜索target节点的左子树中值最大的节点
    			while (leftMaxNode.right != null)
    			{ 
    				leftMaxNode = leftMaxNode.right;
    			}
    			// 从原来的子树中删除leftMaxNode节点
    			leftMaxNode.parent.right = null;
    			// 让leftMaxNode的parent指向target的parent
    			leftMaxNode.parent = target.parent;
    			// 要删除节点是父节点的左子节点
    			if (target == target.parent.left)
    			{ 
    				// 让target的父节点的left指向leftMaxNode
    				target.parent.left = leftMaxNode;
    			}
    			// 要删除节点是父节点的右子节点
    			else
    			{ 
    				// 让target的父节点的right指向leftMaxNode
    				target.parent.right = leftMaxNode;
    			}
    			leftMaxNode.left = target.left;
    			leftMaxNode.right = target.right;
    			target.parent = target.left = target.right = null;
    		}
    	}
    	// 根据给定的值搜索节点
    	@SuppressWarnings("unchecked")
    	public Node getNode(T ele)
    	{ 
    		//从根节点开始搜索
    		Node p = root;
    		while (p != null)
    		{ 
    			int cmp = ele.compareTo(p.data);
    			// 如果搜索的值小于当前p节点的值
    			if (cmp < 0)
    			{ 
    				// 向左子树搜索
    				p = p.left;
    			}
    			// 如果搜索的值大于当前p节点的值
    			else if (cmp > 0)
    			{ 
    				// 向右子树搜索
    				p = p.right;
    			}
    			else
    			{ 
    				return p;
    			}
    		}
    		return null;
    	}
    	// 广度优先遍历
    	public List<Node> breadthFirst()
    	{ 
    		Queue<Node> queue = new ArrayDeque<Node>();
    		List<Node> list = new ArrayList<Node>();
    		if( root != null)
    		{ 
    			// 将根元素加入“队列”
    			queue.offer(root);
    		}
    		while(!queue.isEmpty())
    		{ 
    			// 将该队列的“队尾”的元素添加到List中
    			list.add(queue.peek());
    			Node p = queue.poll();
    			// 如果左子节点不为null，将它加入“队列”
    			if(p.left != null)
    			{ 
    				queue.offer(p.left);
    			}
    			// 如果右子节点不为null，将它加入“队列”
    			if(p.right != null)
    			{ 
    				queue.offer(p.right);
    			}
    		}
    		return list;
    	}
    	public static void main(String[] args)
    	{ 
    		SortedBinTree<Integer> tree
    			= new SortedBinTree<Integer>();
    		// 添加节点
    		tree.add(5);
    		tree.add(20);
    		tree.add(10);
    		tree.add(3);
    		tree.add(8);
    		tree.add(15);
    		tree.add(30);
    		System.out.println(tree.breadthFirst());
    		// 删除节点
    		tree.remove(20);
    		System.out.println(tree.breadthFirst());
    	}
    }

运行结果：  
        ![在这里插入图片描述][20190325182324751.png]

# 红黑树(未掌握) #

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Queue;
    
    public class RedBlackTree<T extends Comparable>
    { 
    	// 定义红黑树的颜色
    	private static final boolean RED   = false;
    	private static final boolean BLACK = true;
    	static class Node
    	{ 
    		Object data;
    		Node parent;
    		Node left;
    		Node right;
    		// 节点的默认颜色是黑色
    		boolean color = BLACK;
    		public Node(Object data , Node parent
    			, Node left , Node right)
    		{ 
    			this.data = data;
    			this.parent = parent;
    			this.left = left;
    			this.right = right;
    		}
    		public String toString()
    		{ 
    			return "[data=" + data
    				+ ", color=" + color + "]";
    		}
    		public boolean equals(Object obj)
    		{ 
    			if (this == obj)
    			{ 
    				return true;
    			}
    			if (obj.getClass() == Node.class)
    			{ 
    				Node target = (Node)obj;
    				return data.equals(target.data)
    					&& color == target.color
    					&& left == target.left
    					&& right == target.right
    					&& parent == target.parent;
    			}
    			return false;
    		}
    	}
    	private Node root;
    	// 两个构造器用于创建排序二叉树
    	public RedBlackTree()
    	{ 
    		root = null;
    	}
    	public RedBlackTree(T o)
    	{ 
    		root = new Node(o , null , null , null);
    	}
    	// 添加节点
    	public void add(T ele)
    	{ 
    		// 如果根节点为null
    		if (root == null)
    		{ 
    			root = new Node(ele , null , null , null);
    		}
    		else
    		{ 
    			Node current = root;
    			Node parent = null;
    			int cmp = 0;
    			// 搜索合适的叶子节点，以该叶子节点为父节点添加新节点
    			do
    			{ 
    				parent = current;
    				cmp = ele.compareTo(current.data);
    				// 如果新节点的值大于当前节点的值
    				if (cmp > 0)
    				{ 
    					// 以右子节点作为当前节点
    					current = current.right;
    				}
    				// 如果新节点的值小于当前节点的值
    				else
    				{ 
    					// 以左子节点作为当前节点
    					current = current.left;
    				}
    			}
    			while (current != null);
    			// 创建新节点
    			Node newNode = new Node(ele , parent , null , null);
    			// 如果新节点的值大于父节点的值
    			if (cmp > 0)
    			{ 
    				// 新节点作为父节点的右子节点
    				parent.right = newNode;
    			}
    			// 如果新节点的值小于父节点的值
    			else
    			{ 
    				//新节点作为父节点的左子节点
    				parent.left = newNode;
    			}
    			// 维护红黑树
    			fixAfterInsertion(newNode);
    		}
    	}
    	// 删除节点
    	public void remove(T ele)
    	{ 
    		// 获取要删除的节点
    		Node target = getNode(ele);
    		// 如果要删除节点的左子树、右子树都不为空
    		if (target.left != null && target.right != null)
    		{ 
    			// 找到target节点中序遍历的前一个节点
    			// s用于保存target节点的左子树中值最大的节点
    			Node s = target.left;
    			// 搜索target节点的左子树中值最大的节点
    			while (s.right != null)
    			{ 
    				s = s.right;
    			}
    			// 用s节点来代替p节点
    			target.data = s.data;
    			target = s;
    		}
    		// 开始修复它的替换节点，如果该替换节点不为null
    		Node replacement = (target.left != null ?
    			target.left : target.right);
    		if (replacement != null)
    		{ 
    			// 让replacement的parent指向target的parent
    			replacement.parent = target.parent;
    			// 如果target的parent为null，表明target本身是根节点
    			if (target.parent == null)
    			{ 
    				root = replacement;
    			}
    			// 如果target是其父节点的左子节点
    			else if (target == target.parent.left)
    			{ 
    				// 让target的父节点left指向replacement
    				target.parent.left  = replacement;
    			}
    			// 如果target是其父节点的右子节点
    			else
    			{ 
    				// 让target的父节点right指向replacement
    				target.parent.right = replacement;
    			}
    			// 彻底删除target节点
    			target.left = target.right = target.parent = null;
    
    			// 修复红黑树
    			if (target.color == BLACK)
    			{ 
    				fixAfterDeletion(replacement);
    			}
    		}
    		// target本身是根节点
    		else if (target.parent == null)
    		{ 
    			root = null;
    		}
    		else
    		{ 
    			// target没有子节点，把它当成虚的替换节点。
    			// 修复红黑树
    			if (target.color == BLACK)
    			{ 
    				fixAfterDeletion(target);
    			}
    			if (target.parent != null)
    			{ 
    				// 如果target是其父节点的左子节点
    				if (target == target.parent.left)
    				{ 
    					// 将target的父节点left设为null
    					target.parent.left = null;
    				}
    				// 如果target是其父节点的右子节点
    				else if (target == target.parent.right)
    				{ 
    					// 将target的父节点right设为null
    					target.parent.right = null;
    				}
    				// 将target的parent设置null
    				target.parent = null;
    			}
    		}
    	}
    	// 根据给定的值搜索节点
    	public Node getNode(T ele)
    	{ 
    		// 从根节点开始搜索
    		Node p = root;
    		while (p != null)
    		{ 
    			int cmp = ele.compareTo(p.data);
    			// 如果搜索的值小于当前p节点的值
    			if (cmp < 0)
    			{ 
    				// 向左子树搜索
    				p = p.left;
    			}
    			// 如果搜索的值大于当前p节点的值
    			else if (cmp > 0)
    			{ 
    				// 向右子树搜索
    				p = p.right;
    			}
    			else
    			{ 
    				return p;
    			}
    		}
    		return null;
    	}
    	// 广度优先遍历
    	public List<Node> breadthFirst()
    	{ 
    		Queue<Node> queue = new ArrayDeque<Node>();
    		List<Node> list = new ArrayList<Node>();
    		if( root != null)
    		{ 
    			// 将根元素入“队列”
    			queue.offer(root);
    		}
    		while(!queue.isEmpty())
    		{ 
    			// 将该队列的“队尾”的元素添加到List中
    			list.add(queue.peek());
    			Node p = queue.poll();
    			// 如果左子节点不为null，将它入“队列”
    			if(p.left != null)
    			{ 
    				queue.offer(p.left);
    			}
    			// 如果右子节点不为null，将它入“队列”
    			if(p.right != null)
    			{ 
    				queue.offer(p.right);
    			}
    		}
    		return list;
    	}
    	// 插入节点后修复红黑树
    	private void fixAfterInsertion(Node x)
    	{ 
    		x.color = RED;
    		// 直到x节点的父节点不是根，且x的父节点不是红色
    		while (x != null && x != root
    			&& x.parent.color == RED)
    		{ 
    			// 如果x的父节点是其父节点的左子节点
    			if (parentOf(x) == leftOf(parentOf(parentOf(x))))
    			{ 
    				// 获取x的父节点的兄弟节点
    				Node y = rightOf(parentOf(parentOf(x)));
    				// 如果x的父节点的兄弟节点是红色
    				if (colorOf(y) == RED)
    				{ 
    					// 将x的父节点设为黑色
    					setColor(parentOf(x), BLACK);
    					// 将x的父节点的兄弟节点设为黑色
    					setColor(y, BLACK);
    					// 将x的父节点的父节点设为红色
    					setColor(parentOf(parentOf(x)), RED);
    					x = parentOf(parentOf(x));
    				}
    				// 如果x的父节点的兄弟节点是黑色
    				else
    				{ 
    					// 如果x是其父节点的右子节点
    					if (x == rightOf(parentOf(x)))
    					{ 
    						// 将x的父节点设为x
    						x = parentOf(x);
    						rotateLeft(x);
    					}
    					// 把x的父节点设为黑色
    					setColor(parentOf(x), BLACK);
    					// 把x的父节点的父节点设为红色
    					setColor(parentOf(parentOf(x)), RED);
    					rotateRight(parentOf(parentOf(x)));
    				}
    			}
    			// 如果x的父节点是其父节点的右子节点
    			else
    			{ 
    				// 获取x的父节点的兄弟节点
    				Node y = leftOf(parentOf(parentOf(x)));
    				// 如果x的父节点的兄弟节点是红色
    				if (colorOf(y) == RED)
    				{ 
    					// 将x的父节点设为黑色。
    					setColor(parentOf(x), BLACK);
    					// 将x的父节点的兄弟节点设为黑色
    					setColor(y, BLACK);
    					// 将x的父节点的父节点设为红色
    					setColor(parentOf(parentOf(x)), RED);
    					// 将x设为x的父节点的节点
    					x = parentOf(parentOf(x));
    				}
    				// 如果x的父节点的兄弟节点是黑色
    				else
    				{ 
    					// 如果x是其父节点的左子节点
    					if (x == leftOf(parentOf(x)))
    					{ 
    						//将x的父节点设为x
    						x = parentOf(x);
    						rotateRight(x);
    					}
    					// 把x的父节点设为黑色
    					setColor(parentOf(x), BLACK);
    					// 把x的父节点的父节点设为红色
    					setColor(parentOf(parentOf(x)), RED);
    					rotateLeft(parentOf(parentOf(x)));
    				}
    			}
    		}
    		// 将根节点设为黑色
    		root.color = BLACK;
    	}
    	// 删除节点后修复红黑树
    	private void fixAfterDeletion(Node x)
    	{ 
    		// 直到x不是根节点，且x的颜色是黑色
    		while (x != root && colorOf(x) == BLACK)
    		{ 
    			// 如果x是其父节点的左子节点
    			if (x == leftOf(parentOf(x)))
    			{ 
    				// 获取x节点的兄弟节点
    				Node sib = rightOf(parentOf(x));
    				// 如果sib节点是红色
    				if (colorOf(sib) == RED)
    				{ 
    					// 将sib节点设为黑色
    					setColor(sib, BLACK);
    					// 将x的父节点设为红色
    					setColor(parentOf(x), RED);
    					rotateLeft(parentOf(x));
    					// 再次将sib设为x的父节点的右子节点
    					sib = rightOf(parentOf(x));
    				}
    				// 如果sib的两个子节点都是黑色
    				if (colorOf(leftOf(sib)) == BLACK
    					&& colorOf(rightOf(sib)) == BLACK)
    				{ 
    					// 将sib设为红色
    					setColor(sib, RED);
    					// 让x等于x的父节点
    					x = parentOf(x);
    				}
    				else
    				{ 
    					// 如果sib的只有右子节点是黑色
    					if (colorOf(rightOf(sib)) == BLACK)
    					{ 
    						// 将sib的左子节点也设为黑色
    						setColor(leftOf(sib), BLACK);
    						// 将sib设为红色
    						setColor(sib, RED);
    						rotateRight(sib);
    						sib = rightOf(parentOf(x));
    					}
    					// 设置sib的颜色与x的父节点的颜色相同
    					setColor(sib, colorOf(parentOf(x)));
    					// 将x的父节点设为黑色
    					setColor(parentOf(x), BLACK);
    					// 将sib的右子节点设为黑色
    					setColor(rightOf(sib), BLACK);
    					rotateLeft(parentOf(x));
    					x = root;
    				}
    			}
    			// 如果x是其父节点的右子节点
    			else
    			{ 
    				// 获取x节点的兄弟节点
    				Node sib = leftOf(parentOf(x));
    				// 如果sib的颜色是红色
    				if (colorOf(sib) == RED)
    				{ 
    					// 将sib的颜色设为黑色
    					setColor(sib, BLACK);
    					// 将sib的父节点设为红色
    					setColor(parentOf(x), RED);
    					rotateRight(parentOf(x));
    					sib = leftOf(parentOf(x));
    				}
    				// 如果sib的两个子节点都是黑色
    				if (colorOf(rightOf(sib)) == BLACK
    					&& colorOf(leftOf(sib)) == BLACK)
    				{ 
    					// 将sib设为红色
    					setColor(sib, RED);
    					//让x等于x的父节点
    					x = parentOf(x);
    				}
    				else
    				{ 
    					// 如果sib只有左子节点是黑色
    					if (colorOf(leftOf(sib)) == BLACK)
    					{ 
    						// 将sib的右子节点也设为黑色
    						setColor(rightOf(sib), BLACK);
    						// 将sib设为红色
    						setColor(sib, RED);
    						rotateLeft(sib);
    						sib = leftOf(parentOf(x));
    					}
    					// 将sib的颜色设为与x的父节点颜色相同
    					setColor(sib, colorOf(parentOf(x)));
    					// 将x的父节点设为黑色
    					setColor(parentOf(x), BLACK);
    					// 将sib的左子节点设为黑色
    					setColor(leftOf(sib), BLACK);
    					rotateRight(parentOf(x));
    					x = root;
    				}
    			}
    		}
    		setColor(x, BLACK);
    	}
    	// 获取指定节点的颜色
    	private boolean colorOf(Node p)
    	{ 
    		return (p == null ? BLACK : p.color);
    	}
    	// 获取指定节点的父节点
    	private Node parentOf(Node p)
    	{ 
    		return (p == null ? null: p.parent);
    	}
    	// 为指定节点设置颜色
    	private void setColor(Node p, boolean c)
    	{ 
    		if (p != null)
    		{ 
    			p.color = c;
    		}
    	}
    	// 获取指定节点的左子节点
    	private Node leftOf(Node p)
    	{ 
    		return (p == null) ? null: p.left;
    	}
    	// 获取指定节点的右子节点
    	private Node rightOf(Node p)
    	{ 
    		return (p == null) ? null: p.right;
    	}
    	/** * 执行如下转换 * p r * r p * q q */
    	private void rotateLeft(Node p)
    	{ 
    		if (p != null)
    		{ 
    			// 取得p的右子节点
    			Node r = p.right;
    			Node q = r.left;
    			// 将r的左子节点链到p的右节点链上
    			p.right = q;
    			// 让r的左子节点的parent指向p节点
    			if (q != null)
    			{ 
    				q.parent = p;
    			}
    			r.parent = p.parent;
    			// 如果p已经是根节点
    			if (p.parent == null)
    			{ 
    				root = r;
    			}
    			// 如果p是其父节点的左子节点
    			else if (p.parent.left == p)
    			{ 
    				// 将r设为p的父节点的左子节点
    				p.parent.left = r;
    			}
    			else
    			{ 
    				// 将r设为p的父节点的右子节点
    				p.parent.right = r;
    			}
    			r.left = p;
    			p.parent = r;
    		}
    	}
    	/** * 执行如下转换 * p l * l p * q q */
    	private void rotateRight(Node p)
    	{ 
    		if (p != null)
    		{ 
    			// 取得p的左子节点
    			Node l = p.left;
    			Node q = l.right;
    			// 将l的右子节点链到p的左节点链上
    			p.left = q;
    			// 让l的右子节点的parent指向p节点
    			if (q != null)
    			{ 
    				q.parent = p;
    			}
    			l.parent = p.parent;
    			// 如果p已经是根节点
    			if (p.parent == null)
    			{ 
    				root = l;
    			}
    			// 如果p是其父节点的右子节点
    			else if (p.parent.right == p)
    			{ 
    				// 将l设为p的父节点的右子节点
    				p.parent.right = l;
    			}
    			else
    			{ 
    				// 将l设为p的父节点的左子节点
    				p.parent.left = l;
    			}
    			l.right = p;
    			p.parent = l;
    		}
    	}
    	// 实现中序遍历
    	public List<Node> inIterator()
    	{ 
    		return inIterator(root);
    	}
    	private List<Node> inIterator(Node node)
    	{ 
    		List<Node> list = new ArrayList<Node>();
    		// 递归处理左子树
    		if (node.left != null)
    		{ 
    			list.addAll(inIterator(node.left));
    		}
    		// 处理根节点
    		list.add(node);
    		// 递归处理右子树
    		if (node.right != null)
    		{ 
    			list.addAll(inIterator(node.right));
    		}
    		return list;
    	}
    	public static void main(String[] args)
    	{ 
    		RedBlackTree<Integer> tree
    			= new RedBlackTree<Integer>();
    		//添加节点
    		tree.add(5);
    		tree.add(20);
    		tree.add(10);
    		tree.add(3);
    		tree.add(8);
    		tree.add(15);
    		tree.add(30);
    		System.out.println(tree.breadthFirst());
    		//删除节点
    		tree.remove(20);
    		System.out.println(tree.breadthFirst());
    // System.out.println(tree.inIterator());
    	}
    }

运行结果：  
![在这里插入图片描述][20190325182641608.png]

[20190324161854683.png]: /images/20220228/1d4f78636da54be79b392744553e86b9.png
[20190325152837475.png]: /images/20220228/51df6a850553466aa3857efa8bfc7430.png
[20190325154423133.png]: /images/20220228/3bd387287c06485f9ea9b54ebb9d2d7c.png
[20190325161712173.png]: /images/20220228/78a5a6fbd44847aba651077daf739463.png
[20190325162800445.png]: /images/20220228/ca30f825a60c44608e323a89a2dafdcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]: /images/20220228/f70bc76d56324c0ebe0e7008c570f86c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]: /images/20220228/d3d7dce92ff44b4aabf89c7a5c06169b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 2]: /images/20220228/c98584c11e674a1585f02a84a299dca2.png
[20190325180136783.png]: /images/20220228/489d1fb7f1f04f93bdffce870f8512fa.png
[20190325182324751.png]: /images/20220228/dc8fdfe40477465cbdd66f7c749571c8.png
[20190325182641608.png]: /images/20220228/e9042931e53748609e1ab00f418d3f7e.png