二叉树的基本实现
二叉树节点
//二叉树节点
private static class TreeNode{
int value;
TreeNode leftChild;
TreeNode rightChild;
public TreeNode(int value){
this.value=value;
leftChild = null;
rightChild = null;
}
public void display(){
System.out.print(value+" ");
}
@Override
public String toString() {
return "TreeNode-value is "+value;
}
public boolean isHasLeftChild(TreeNode root){
if(root.leftChild!=null)
return true;
else{
return false;
}
}
public boolean isHasRightChild(TreeNode root){
if(root.rightChild!=null)
return true;
else{
return false;
}
}
}
二叉树节点的增加
/**
* 增加二叉树节点
* @param root
* @param value
* @return
*/
public TreeNode insertNode(TreeNode root,int value){
TreeNode current = new TreeNode(value);
if(root == null){
root = current;
return root;
}
if(root.value < value){
if(root.rightChild == null){
root.rightChild = current;
}else{
insertNode(root.rightChild,value);
}
}else{
if(root.leftChild == null){
root.leftChild = current;
}else{
insertNode(root.leftChild,value);
}
}
return root;
}
二叉树的构造
public TreeNode createBinaryTree(int[] data){
TreeNode root = null;
if(data == null) {
return root;
}
BinaryTree tree = new BinaryTree();
for(int i=0;i<data.length;i++){
root = tree.insertNode(root,data[i]);
}
return root;
}
二叉树的遍历
/**
* 先序遍历
* @param root
*/
public static void preOrderTravle(TreeNode root){
if(root == null){
return;
}
root.display();
preOrderTravle(root.leftChild);
preOrderTravle(root.rightChild);
}
/**
* 后序遍历
*/
public static void afterOrderTravle(TreeNode root){
if(root == null){
return;
}
afterOrderTravle(root.leftChild);
afterOrderTravle(root.rightChild);
root.display();
}
/**
* 中序遍历
*/
public static void inOrderTravle(TreeNode root){
if(root == null){
return;
}
inOrderTravle(root.leftChild);
root.display();
inOrderTravle(root.rightChild);
}
二分查找
/**
* 二分查找
* @param root
* @param value
* @return
*/
public static TreeNode findKey(TreeNode root,int value){
TreeNode current = root;
for(;;){
if(current == null){
return current;
}
if(current.value == value){
return current;
}else if(current.value < value){
current = current.rightChild;
}else {
current = current.leftChild;
}
}
}
查找树中最小值/最大值
/**
* 查找树中最小值
* @param root
* @return
*/
public static int getMinValue(TreeNode root){
TreeNode current = root;
while(current.leftChild != null){
current = current.leftChild;
}
return current.value;
}
/**
* 查找树中最大值
* @param root
* @return
*/
public static int getMaxValue(TreeNode root){
TreeNode current = root;
while(current.rightChild != null){
current = current.rightChild;
}
return current.value;
}
删除节点
对于二叉搜索树的删除操作，主要是要理解其中的几种情况，写起来还是比较简单的。
当然一开始还是需要判断要删除的节点是否存在于我们的树中，如果要删除的元素都不在树中，就直接返回false；否则，再分为以下四种情况来进行分析：
- 要删除的节点无左右孩子
- 要删除的节点只有左孩子
- 要删除的节点只有右孩子
- 要删除的节点有左、右孩子
删除方法解释
对于第一种情况，我们完全可以把它归为第二或者第三种情况，就不用再单独写一部分代码进行处理；
如果要删除的节点只有左孩子，那么就让该节点的父亲结点指向该节点的左孩子，然后删除该节点，返回true；
如果要删除的节点只有右孩子，那么就让该节点的父亲结点指向该节点的右孩子，然后删除该节点，返回true；
对于上面这两种情况我们还应该在之前进行一个判断，就是判断这个节点是否是根节点，如果是根节点的话，就直接让根节点指向这个节点的左孩子或右孩子，然后删除这个节点。
最后一种也是最麻烦的一种就是要删除的节点的左右孩子都存在。此时我们的删除方法如下：
- 找到该节点的右子树中的最左孩子（也就是右子树中序遍历的第一个节点）
- 把它的值和要删除的节点的值进行交换
- 然后删除这个节点即相当于把我们想删除的节点删除了，返回true；
/**
* 删除节点
* @param root
* @param value
* @return
*/
public static boolean deleteTreeNode(TreeNode root , int value){
if(root == null){
return false;
}
TreeNode parent = null;
TreeNode current = root;
//要删除的节点
TreeNode del = null;
//查找节点
while(current != null && current.value != value){
if(current.value > value){
parent = current;
current = current.leftChild;
}else{
parent = current;
current = current.rightChild;
}
}
//节点若不存在，直接返回false
if(current == null){
return false;
}
//只有右孩子，则进一步判断该节点是否为根节点
//若为根节点则直接将根节点设置为将被删除节点的右孩子
//若不是根节点,则将被删除节点的父节点指向被删除节点的右孩子
if(current.leftChild == null ){
//如果current就是根节点,则将当前跟节点的右孩子设置为新的根节点
if(current == root){
root = current.rightChild;
}
else if(current == parent.leftChild){
parent.leftChild = current.rightChild;
}
else{
parent.rightChild = current.rightChild;
}
//只有左孩子，则进一步判断该节点是否为根节点
//若为根节点则直接将根节点设置为将被删除节点的左孩子
//若不是根节点,则将被删除节点的父节点指向被删除节点的左孩子
}else if(current.rightChild == null){
if(current == root){
root = current.leftChild;
}
else if(current == parent.leftChild){
parent.leftChild = current.leftChild;
}else{
parent.rightChild = current.leftChild;
}
}//左右孩子都不为空
else if(current.leftChild != null && current.rightChild != null){
//找到节点右子树的最左节点
TreeNode left = current.rightChild;
parent = current;
for(;left.leftChild != null;left = left.leftChild){
parent = left;
}
del = left;
//交换节点的值，把left的值作为current的值
current.value = left.value;
//将被删除节点的孩子连接到被删除节点的父节点
if(parent.leftChild == left){
parent.leftChild = left.rightChild;
}else{
parent.rightChild = left.rightChild;
}
}
return true;
}