Java Tree

二叉搜索树

Posted by Elijah's Blog on Monday, March 20, 2017

在学习数据结构中最常见的，最多考到的就是树，而树中最多使用到的就是二叉树，我们将学习如何对一棵二叉树进行增删改查，其中二叉树用二叉搜索树举例

首先，我们应该定义一个二叉树的节点信息

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode rigth;
    TreeNode(int x){
        val = x;
    }

    @Override
    public String toString() {
        return String.valueOf(val);
    }
}

对于树节点node的所有子节点进行遍历，查找x值是否存在，如果大于当前值则寻找node的右节点，如果小于则查找左节点，否则意味着node.val==x则返回node节点

 public TreeNode Find(int x, TreeNode node) {
        if (node == null) {
            return null;
        } else if (x > node.val) {
            return Find(x, node.rigth);
        } else if (x < node.val) {
            return Find(x, node.left);
        } else {
            return node;
        }
    }

寻找最小值就是不断地寻找最左子节点

    public TreeNode FindMin(TreeNode node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        } else {
            return FindMin(node.left);
        }
    }

与寻找最小值相似，寻找最大值的过程就是不断寻找最右子节点

    public TreeNode FindMax(TreeNode node) {
        if (node == null) {
            return null;
        } else if (node.rigth == null) {
            return node;
        } else {
            return FindMax(node.rigth);
        }
    }

插入节点就是判断val值对于当前node.val是应该在左边还是在右边，如果当前节点为空，则新建一个值为val的新节点

  public TreeNode Insert(int val, TreeNode node) {
        if (node == null) {
            node = new TreeNode(val);
        } else if (val < node.val) {
            node.left = Insert(val, node.left);
        } else if (val > node.val) {
            node.rigth = Insert(val, node.rigth);
        }
        return node;
    }

删除节点就是判断val值对于当前node.val是应该在左边还是在右边，如果等于当前节点，则判断是否只有一个节点，如果是则将它的下一个节点指向下一个节点的下一个节点，如果有两个节点，则将该值变为右子树中的最小值，并删除右子树的最小值

    public TreeNode Delete(int val, TreeNode node) {
        if (node == null) {
            return null;
        } else if (val < node.val) {
            node.left = Delete(val, node.left);
        } else if (val > node.val) {
            node.rigth = Delete(val, node.rigth);
        } else if (node.left != null && node.rigth != null) {
            TreeNode tmp = FindMin(node.rigth);
            node.val = tmp.val;
            node.rigth = Delete(tmp.val, node.rigth);
        } else {
            if (node.left == null) {
                node = node.rigth;
            } else if (node.rigth == null) {
                node = node.left;
            }
        }
        return node;
    }

这样我们就完成了二叉搜索树的增加删除查询，修改就是在查询到结果之后进行对node.val值的修改操作，在这里就不再赘述

FEATURED TAGS
java tree