笔记5- 二叉排序树简介。 树和二叉树和森林之间的转换

二叉排序树(查找树，搜索树)

二叉排序树属于二叉树的一种：
当一个二叉树或者是一颗空树，或者是一颗具有如下性质的树：
1）若左子树不为空，那么左子树上面的所有节点的关键字值都比根节点的关键字值小
2）若右子树不为空，那么右子树上面的所有节点的关键字值都比根节点的关键字值大
3）左右子树都为二叉树
4）没有重复值（这一点在实际中可以忽略）
这棵二叉树可以称为二叉排序树，用二叉排序树可以很快的用来查询和搜索。


image.png

下面简单的介绍一个二叉排序树的增删改查方法：
1.生成一个空树：

public class SearchBinaryTree {
    
    //根节点
    public TreeNode rootNode;
    
    public class TreeNode{
        int data;
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode parent;
        
        public TreeNode(int data){
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
            this.parent = null;
        }
    }
}
image.png

2.添加一个节点：

    // 添加一个节点
    public TreeNode put(int data){
        if(rootNode==null){
            TreeNode node=new TreeNode(data);
            rootNode=node;
            return node;
        }
        TreeNode parent=null;
        TreeNode node=rootNode;
        //找到要放入的位置
        while(node!=null){
            parent=node;
            if(data<node.data){
                node=node.leftChild;
            }else if(data>node.data){
                node=node.rightChild;
            }else{//是重复值 就不理会了
                return node;
            }
        }
        //生成一个节点放入
        TreeNode newNode=new TreeNode(data);
        if(data<parent.data) {
            parent.leftChild = newNode;
        }else{
            parent.rightChild=newNode;
        }
        newNode.parent=parent;

        return newNode;
    }

3.查找一个节点：

    /**
     * 查找一个节点
     */
    public TreeNode searchNode(int data){
        if(rootNode==null){
            return null;
        }
        TreeNode node=rootNode;
        while(node!=null){
            if(node.data==data){
                return node;
            }else if(data>node.data){
                node=node.rightChild;
            }else if(data<node.data){
                node=node.leftChild;
            }
        }
        return null;
    }

4.删除一个节点：

1.节点是叶子
image.png

2.只有左孩子
image.png

3.只有右孩子
image.png

4.左右孩子都有
image.png
    /**
     * 删除节点
     * 要删除的节点在树上是一定存在的才删除
     * 
     * TODO 把一些引用置空
     * 此处删除方法只是为了说清思路，还会有更优化的删除方法，大家可以参考Java中的 TreeMap类
     */
    public void delNode(TreeNode node){
        if(node==null){
            throw new NoSuchElementException();
        }else{
            //先得到父亲，方便后面的操作
            TreeNode parent=node.parent;
            //1.叶子
            if(node.leftChild==null && node.rightChild==null){
                //特别的情况:1.树上只有一个节点或是空树
                if(parent==null){
                    rootNode=null;
                }else if(parent.rightChild==node){
                    parent.rightChild=null;
                }else if(parent.leftChild==node){
                    parent.leftChild=null;
                }
                node.parent=null;
            }else if(node.leftChild!=null && node.rightChild==null){
                //2.只有左孩子
                if(parent==null){//如果要删除的是根
                    node.parent=null;
                    node.leftChild.parent=null;
                    rootNode=node.leftChild;
                }else{
                    if(parent.leftChild==node){//要删除的节点是父亲的左边
                        node.leftChild.parent=parent;
                        parent.leftChild=node.leftChild;

                    }else{//要删除的节点是父亲的右边
                        node.leftChild.parent=parent;
                        parent.rightChild=node.leftChild;
                    }
                    node.parent=null;
                }

            }else if(node.leftChild==null && node.rightChild!=null){
                //3.只有右孩子
                if(parent==null){//如果要删除的是根
                    node.parent=null;
                    node.rightChild.parent=null;
                    rootNode=node.rightChild;
                }else{
                    if(parent.leftChild==node){//要删除的节点是父亲的左边
                        node.rightChild.parent=parent;
                        parent.leftChild=node.rightChild;
                    }else{//要删除的节点是父亲的右边
                        node.rightChild.parent=parent;
                        parent.rightChild=node.rightChild;
                    }
                    node.parent=null;
                }
            }else{//4。有左右两个孩子
                if(node.rightChild.leftChild==null){//1.如果被删除节点的右子树的左子树为空，就直接补上右子树
                    node.rightChild.leftChild=node.leftChild;
                    if(parent==null){
                        rootNode=node.rightChild;
                    }else{
                        if(parent.leftChild==node){
                            parent.leftChild=node.rightChild;
                            //
                        }else{
                            parent.rightChild=node.rightChild;
                            //
                        }
                    }
                    node.parent=null;
                }else{//2.否则就要补上右子树的左子树上最小的一个
                    TreeNode leftNode=getMinLeftTreeNode(node.rightChild);
                    //1
                    leftNode.leftChild=node.leftChild;
                    //2
                    TreeNode leftNodeP=leftNode.parent;
                    leftNodeP.leftChild=leftNode.rightChild;
                    //3
                    leftNode.rightChild=node.rightChild;
                    //4
                    if(parent==null){
                        rootNode=leftNode;
                    }else{
                        if(parent.leftChild==node){
                            parent.leftChild=leftNode;
                            //
                        }else{
                            parent.rightChild=leftNode;
                            //
                        }
                    }
                }
            }
        }
    }

这样就基本完成了一个可以增删查的二叉树：

import java.util.NoSuchElementException;

/**
 * 二叉排序树
 * @author LiXin
 *
 */
public class SearchBinaryTree {
    
    //根节点
    public TreeNode rootNode;
    
    // 添加一个节点
    public TreeNode put(int data){
        if(rootNode==null){
            TreeNode node=new TreeNode(data);
            rootNode=node;
            return node;
        }
        TreeNode parent=null;
        TreeNode node=rootNode;
        //找到要放入的位置
        while(node!=null){
            parent=node;
            if(data<node.data){
                node=node.leftChild;
            }else if(data>node.data){
                node=node.rightChild;
            }else{//是重复值 就不理会了
                return node;
            }
        }
        //生成一个节点放入
        TreeNode newNode=new TreeNode(data);
        if(data<parent.data) {
            parent.leftChild = newNode;
        }else{
            parent.rightChild=newNode;
        }
        newNode.parent=parent;

        return newNode;
    }
    
    /**
     * 中序遍历
     * @param rootNode
     */
    public void midOrderTraverse(TreeNode rootNode){
        if(rootNode == null){
            return;
        }
        midOrderTraverse(rootNode.leftChild);
        System.out.print(rootNode.data);
        midOrderTraverse(rootNode.rightChild);
    }
    
    /**
     * 查找一个节点
     */
    public TreeNode searchNode(int data){
        if(rootNode==null){
            return null;
        }
        TreeNode node=rootNode;
        while(node!=null){
            if(node.data==data){
                return node;
            }else if(data>node.data){
                node=node.rightChild;
            }else if(data<node.data){
                node=node.leftChild;
            }
        }
        return null;
    }


    /**
     * 删除节点
     * 要删除的节点在树上是一定存在的才删除
     * 
     * TODO 把一些应用置空
     */
    public void delNode(TreeNode node){
        if(node==null){
            throw new NoSuchElementException();
        }else{
            //先得到父亲，方便后面的操作
            TreeNode parent=node.parent;
            //1.叶子
            if(node.leftChild==null && node.rightChild==null){
                //特别的情况:1.树上只有一个节点或是空树
                if(parent==null){
                    rootNode=null;
                }else if(parent.rightChild==node){
                    parent.rightChild=null;
                }else if(parent.leftChild==node){
                    parent.leftChild=null;
                }
                node.parent=null;
            }else if(node.leftChild!=null && node.rightChild==null){
                //2.只有左孩子
                if(parent==null){//如果要删除的是根
                    node.parent=null;
                    node.leftChild.parent=null;
                    rootNode=node.leftChild;
                }else{
                    if(parent.leftChild==node){//要删除的节点是父亲的左边
                        node.leftChild.parent=parent;
                        parent.leftChild=node.leftChild;

                    }else{//要删除的节点是父亲的右边
                        node.leftChild.parent=parent;
                        parent.rightChild=node.leftChild;
                    }
                    node.parent=null;
                }

            }else if(node.leftChild==null && node.rightChild!=null){
                //3.只有右孩子
                if(parent==null){//如果要删除的是根
                    node.parent=null;
                    node.rightChild.parent=null;
                    rootNode=node.rightChild;
                }else{
                    if(parent.leftChild==node){//要删除的节点是父亲的左边
                        node.rightChild.parent=parent;
                        parent.leftChild=node.rightChild;
                    }else{//要删除的节点是父亲的右边
                        node.rightChild.parent=parent;
                        parent.rightChild=node.rightChild;
                    }
                    node.parent=null;
                }
            }else{//4。有左右两个孩子
                if(node.rightChild.leftChild==null){//1.如果被删除节点的右子树的左子树为空，就直接补上右子树
                    node.rightChild.leftChild=node.leftChild;
                    if(parent==null){
                        rootNode=node.rightChild;
                    }else{
                        if(parent.leftChild==node){
                            parent.leftChild=node.rightChild;
                            //此处要删除引用...
                        }else{
                            parent.rightChild=node.rightChild;
                            //此处要删除引用...
                        }
                    }
                    node.parent=null;
                }else{//2.否则就要补上右子树的左子树上最小的一个
                    TreeNode leftNode=getMinLeftTreeNode(node.rightChild);
                    //1
                    leftNode.leftChild=node.leftChild;
                    //2
                    TreeNode leftNodeP=leftNode.parent;
                    leftNodeP.leftChild=leftNode.rightChild;
                    //3
                    leftNode.rightChild=node.rightChild;
                    //4
                    if(parent==null){
                        rootNode=leftNode;
                    }else{
                        if(parent.leftChild==node){
                            parent.leftChild=leftNode;
                            //此处要删除引用...
                        }else{
                            parent.rightChild=leftNode;
                           //此处要删除引用...
                        }
                    }
                }
            }
        }
    }
    /**
     * 获取左子树上最小的一个
     * @param node
     * @return
     */
    private TreeNode getMinLeftTreeNode(TreeNode node) {
        TreeNode currootNode=null;
        if(node==null){
            return null;
        }else{
            currootNode=node;
            while(currootNode.leftChild!=null){
                currootNode=currootNode.leftChild;
            }
        }
        return currootNode;
    }
    
    
    public class TreeNode{
        int data;
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode parent;
        
        public TreeNode(int data){
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
            this.parent = null;
        }
    }
}

树 森林 二叉树的转化

1.树转化成二叉树：


image.png
image.png

2.森林转化成二叉树：

image.png

image.png

3.二叉树转成树：


image.png
image.png

4.二叉树转化成森林：

image.png
image.png
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 疯狂java笔记之树和二叉树
    树的概述 树是一种非常常用的数据结构，树与前面介绍的线性表，栈，队列等线性结构不同，树是一种非线性结构 1.树的定...
    Jack921阅读 4,716评论 1赞 31
  • 数据结构基础概念篇
    一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这...
    Winterfell_Z阅读 6,524评论 0赞 13
  • 树和二叉树
    什么是树？ 树状图是一种数据结构，它是由(n>=1）个有限节点组成一个具有层次关系的集合，把它叫做"树"把它们叫做...
    _Caesar阅读 595评论 0赞 3
  • 如果你是干净的
    才关掉电话那头的叨叨絮语 又听到你微信的声音核磁共振 还是清晨的阳光如此这般窗明 几净如此这般柔和 温馨 才...
    江城妖怪阅读 353评论 0赞 1
  • 声声慢似我
    寻寻觅觅 寻不见你的身影 冷冷清清 梧桐兼细雨无人问处境 乍暧还寒时候 最难将息的心 三杯两盏淡酒 怎敌他晚来的情...
    我的那只羊阅读 341评论 4赞 0

友情链接更多精彩内容