当前位置:首页 > 开发 > 编程语言 > 搜索 > 正文

二叉树:二叉搜索树

发表于: 2012-02-17   作者:dieslrae   来源:转载   浏览:
摘要:     所谓二叉树,就是一个节点最多只能有两个子节点,而二叉搜索树就是一个经典并简单的二叉树.规则是一个节点的左子节点一定比自己小,右子节点一定大于等于自己(当然也可以反过来).在树基本平衡的时候插入,搜索和删除速度都很快,时间复杂度为O(logN).但是,如果插入的是有序的数据,那效率就会变成O(N),在这个时候,树其实变成了一个链表. tree代码:
    所谓二叉树,就是一个节点最多只能有两个子节点,而二叉搜索树就是一个经典并简单的二叉树.规则是一个节点的左子节点一定比自己小,右子节点一定大于等于自己(当然也可以反过来).在树基本平衡的时候插入,搜索和删除速度都很快,时间复杂度为O(logN).但是,如果插入的是有序的数据,那效率就会变成O(N),在这个时候,树其实变成了一个链表.

tree代码:
public class Tree {
    private Node root;
    
    /**
     * 插入节点
     * @param data 
     */
    public void insert(int data){
        Node node = new Node(data);
        
        if(this.root == null){
            this.setRoot(node);
            return;
        }
        
        Node current = this.root;
        
        while(true){
            if(current.getData() > data){
                if(current.hasLeft()){
                    current = current.getLeft();
                }else{
                    current.setLeft(node);
                    return;
                }
            }else if(current.getData() < data){
                if(current.hasRight()){
                    current = current.getRight();
                }else{
                    current.setRight(node);
                    return;
                }
            }else{
                return;
            }
        }
    }
    
    /**
     * 删除节点
     * @param key 
     */
    public void remove(int key){
        Node node = this.findNode(key);
        
        if(node == null){
            return;
        }
        
        Node parent = node.getParent();
        
        //要删除的节点没有子节点
        if(!node.hasLeft() && !node.hasRight()){
            if(parent == null){
                this.setRoot(null);
            }else if(node.isLeft()){
                parent.setLeft(null);
            }else{
                parent.setRight(null);
            }
        //要删除的节点只有一个子节点
        }else if(!node.hasRight() || !node.hasLeft()){
            Node child = node.hasLeft() ? node.getLeft() : node.getRight();
            
            if(parent == null){
                this.setRoot(child);
            }else if(node.isLeft()){
                parent.setLeft(child);
            }else{
                parent.setRight(child);
            }
        //要删除的节点有两个子节点
        }else{
            Node successor = this.getSuccessor(node);
            
            if (parent == null) {
                this.setRoot(successor);
            } else if (node.isLeft()) {
                parent.setLeft(successor);
            } else {
                parent.setRight(successor);
            } 
        }
    }
    
    /**
     * 查找
     * @param key 
     */
    public void find(int key){
        Node node = this.findNode(key);
        
        if(node != null){
            System.out.println("node data is : " + node.getData());
        }
    }
    
    /**
     * 查找节点
     * @param key
     * @return 
     */
    private Node findNode(int key){
        Node current = this.root;
        
        while(current.getData() != key){
            if(current.getData() > key){
                if(current.hasLeft()){
                    current = current.getLeft();
                }else{
                    return null;
                }
            }else if(current.getData() < key){
                if(current.hasRight()){
                    current = current.getRight();
                }else{
                    return null;
                }
            }
        }
        
        return current;
    }
    
    /**
     * 找到继任节点,找出删除节点中右树最小的节点,如果删除节点的右节点
     * 没有子节点,则返回null
     * @param node
     * @return 
     */
    private Node getSuccessor(Node node){
        Node current = node.getRight();
        
        while(current.hasLeft()){
            current = current.getLeft();
        }
        
        if(node.getRight() != current){
            Node parent = current.getParent();
            
            if(current.hasRight()){
                parent.setLeft(current.getRight());
            }else{
                parent.setLeft(null);
            }
            
            current.setRight(node.getRight());
        }
        
        current.setLeft(node.getLeft());
        
        return current;
    }
    
    private void setRoot(Node node){
        this.root = node;
        
        if(node != null){
            node.setParent(null);
        }
    }
}


node代码:
public class Node {
    private int data;
    private Node left;
    private Node right;
    private Node parent;

    public Node(int data){
        this.data = data;
    }
    
    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
        
        if(this.left != null){
            this.left.parent = this;
        }
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
        
        if(this.right != null){
            this.right.parent = this;
        }
    }
    
    public boolean hasRight(){
        return this.right != null;
    }
    
    public boolean hasLeft(){
        return this.left != null;
    }
    
    public boolean isRoot(){
        return this.parent == null;
    }
    
    public boolean isRight(){
        return this.parent.right == this;
    }
    
    public boolean isLeft(){
        return this.parent.left == this;
    }
}

二叉树:二叉搜索树

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
第十章 二叉树 学习目的 学习广义树的定义,熟悉树的有关术语 理解树是一种非线性的数据结构 理解很
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 树的特征和
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 树的特征和
二叉搜索树的定义 和前面一篇讨论二叉树有一点不一样,二叉搜索树它本身是一种二叉树,但是它有一个
(一)从上往下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。【层次遍历】 从上到
在上一篇数据结构的博文《数据结构(三):非线性逻辑结构-二叉树》中已经对二叉树的概念、遍历等基
性质 二叉搜索树;对于树中的每一个节点 x,x 的左子树所有节点的 key 不大于 x.key;x 的右子树的 key
基本概念 二叉搜索树是以一棵二叉树来组织的。这样的一棵树可以使用一个链表数据结构来表示: 其中
二叉搜索树定义 二叉搜索树,又称为二叉排序树。Binary Search Tree,Binary Sort Tree,简写为BST
一、概述 二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构。中序
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号