专栏首页Kevin-ZhangCG数据结构之二叉树解析

数据结构之二叉树解析

曾经有个朋友问我:二叉树可以用来干啥况?

我回答他:可以搜索、可以排序呀?

可是,排序有快速排序,归并排序,查找有二分法,甚至直接遍历查找,我干啥要使用二叉树呢?

……

  这位朋友说的是有道理的,二叉树确实在实际中用的比较少,因为有更高级的树,但是二叉树作为一种最基本最典型的排序树,是研究其他树的基础。除此之外,在面试数据结构的时候,二叉树原理被问到的概率是相当高的。言归正传,我们来分析分析二叉树。

  我们知道,在有序数组中,可以快速找到特定的值,但是想在有序数组中插入一个新的数据项,就必须首先找出新数据项插入的位置,然后将比新数据项大的数据项向后移动一位,来给新的数据项腾出空间,删除同理,这样移动很费时。显而易见,如果要做很多的插入和删除操作和删除操作,就不该选用有序数组

  另一方面,链表中可以快速添加和删除某个数据项但是在链表中查找数据项可不容易,必须从头开始访问链表的每一个数据项,直到找到该数据项为止,这个过程很慢。

  树这种数据结构,既能像链表那样快速的插入和删除,又能想有序数组那样快速查找。这里主要实现一种特殊的树——二叉(搜索)树。二叉搜索树有如下特点:一个节点的左子节点的关键字值小于这个节点,右子节点的关键字值大于或等于这个节点。插入一个节点需要根据这个规则进行插入。

  删除节点时二叉搜索树中最复杂的操作,但是删除节点在很多树的应用中又非常重要,所以详细研究并总结下特点。删除节点要从查找要删的节点开始入手,首先找到节点,这个要删除的节点可能有三种情况需要考虑。

  • 该节点是叶节点,没有子节点
  • 该节点有一个子节点
  • 该节点有两个子节点

  第一种最简单,第二种也还是比较简单的,第三种就相当复杂了。下面分析这三种删除情况:

  要删除叶节点,只需要改变该节点的父节点对应子字段的值即可,由指向该节点改为 null 就可以了。垃圾回收器会自动回收叶节点,不需要自己手动删掉;当节点有一个子节点时,这个节点只有两个连接:连向父节点和连向它唯一的子节点。需要从这个序列中剪断这个节点,把它的子节点直接连到它的父节点上即可,这个过程要求改变父节点适当的引用(左子节点还是右子节点),指向要删除节点的子节点即可;第三种情况最复杂,如果要删除有两个子节点的节点,就不能只用它的一个子节点代替它,比如要删除节点25,如果用35取代它,那35的左子节点是15呢还是30?

  因此需要考虑另一种方法,寻找它的中序后继来代替该节点。下图显示的就是要删除节点用它的后继代替它的情况,删除后还是有序的。(这里还有更麻烦的情况,即它的后继自己也有右子节点,下面再讨论。)

  那么如何找后继节点呢?首先得找到要删除的节点的右子节点,它的关键字值一定比待删除节点的大。然后转到待删除节点右子节点的左子节点那里(如果有的话),然后到这个左子节点的左子节点,以此类推,顺着左子节点的路径一直向下找,这个路径上的最后一个左子节点就是待删除节点的后继如果待删除节点的右子节点没有左子节点,那么这个右子节点本身就是后继。寻找后继的示意图如下:

  找到了后继节点,现在开始删除了,先看第一种情况,后继节点是delNode右子节点的做后代,这种情况要执行以下四个步骤:

  • 把后继父节点的leftChild字段置为后继的右子节点;
  • 把后继的rightChild字段置为要删除节点的右子节点;
  • 把待删除节点从它父节点的leftChild或rightChild字段删除,把这个字段置为后继;
  • 把待删除的左子节点移除,将后继的leftChild字段置为待删除节点的左子节点。

这下图所示:

  如果后继节点就是待删除节点的右子节点,这种情况就简单了,因为只需要把后继为跟的子树移到删除的节点的位置即可。如下图所示:

  看到这里,就会发现删除时相当棘手的操作。实际上,因为它非常复杂,一些程序员都尝试着躲开它,他们在Node类中加了一个Boolean字段来标识该节点是否已经被删除,在其他操作之前会先判断这个节点是不是已经删除了,这样删除节点不会改变树的结构。当然树中还保留着这种已经删除的节点,对存储造成浪费,但是如果没有那么多删除的话,这也不失为一个好方法。

  另外二叉树有三种遍历方式:前序中序后序。这个比较简单,直接看下代码即可。

下面手写个二叉搜索树的代码:

public class BNode {
    public int key;
    public double data;
    public BNode parent;
    public BNode leftChild;
    public BNode rightChild;

    public void displayNode() {
        System.out.println("{" + key + ":" + data + "}");
    }
}
public class BinaryTree {
    private BNode root;  // 根节点

    public BinaryTree(BNode root) {
        root = null;
    }

    //二搜索树查找的时间复杂度为O(logN)
    //find node with given key
    public BNode find(int key) {
        BNode current = root;
        while (current.key != key) {
            if (key < current.key) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    //插入节点
    public void inset(int key, int value) {
        BNode newNode = new BNode();
        newNode.key = key;
        newNode.data = value;
        if (root == null) {
            root = newNode;
        } else {
            BNode current = root;
            BNode parent;
            while (true) {
                parent = current;
                if (key < current.key) {
                    //turn left
                    current = current.leftChild;
                    if (current == null) {
                        parent.leftChild = newNode;
                        newNode.parent = parent;
                        return;
                    }
                } else {
                    //trun right
                    current = current.rightChild;
                    if (current == null) {
                        parent.rightChild = newNode;
                        newNode.parent = parent;
                        return;
                    }
                }
            }
        }
    }

    //遍历二叉树
    public void traverse(int traverseType) {
        switch (traverseType) {
            case 1:
                System.out.println("PreOrder Traversal!");
                preOrder(root);
                break;
            case 2:
                System.out.println("InOrder Traversal!");
                inOrder(root);
                break;
            case 3:
                System.out.println("PostOrder Traversal");
                postOrder(root);
            default:
                System.out.println("PreOrder Traversal!");
                preOrder(root);
                break;

        }
        System.out.println("");
    }

    //前序遍历
    public void preOrder(BNode localRoot) {
        if (localRoot != null) {
            System.out.println(localRoot.data + " ");
            preOrder(localRoot.leftChild);
            preOrder(localRoot.rightChild);
        }
    }

    //中序遍历
    public void inOrder(BNode localRoot) {
        if (localRoot != null) {
            inOrder(localRoot.leftChild);
            System.out.println(localRoot.data + " ");
            inOrder(localRoot.rightChild);
        }
    }

    //后序遍历
    public void postOrder(BNode localRoot) {
        if (localRoot != null) {
            postOrder(localRoot.leftChild);
            postOrder(localRoot.rightChild);
            System.out.println(localRoot.data + " ");
        }
    }

    //查找最小值
    /*根据二叉搜索树存储规则:最小值应该是左边那个没有子节点的那个节点*/
    public BNode minNumber() {
        BNode current = root;
        BNode parent = root;
        while (current != null) {
            parent = current;
            current = current.leftChild;
        }
        return parent;
    }

    //查找最大值
    /*根据二叉搜索树的存储规则:最大值应该是右边那个没有子节点的那个节点*/
    public BNode maxNumber() {
        BNode current = root;
        BNode parent = root;
        while (current != null) {
            parent = current;
            current = current.rightChild;
        }
        return parent;
    }

    //删除节点
    /*
    删除节点在二叉树中是最复杂的,主要有三种情况:
    1、该节点没有子节点(简单)
    2、该节点有一个子节点(还行)
    3、该节点有两个子节点(复杂)
    删除节点的时间复杂度为O(logN)
    */
    public boolean delete(int key) {
        BNode current = root;
        boolean isLeftChild = true;
        if (current == null) {
            return false;
        }
        //寻找要删除的节点
        while (current.data != key) {
            if (key < current.data) {
                isLeftChild = true;
                current = current.leftChild;
            } else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null) {
                return false;
            }
        }
        //找到了要删除的节点,下面开始删除
        //1、要删除的节点没有子节点,直接将其父节点的左子节点或者右子节点赋为null即可
        if (current.leftChild == null && current.rightChild == null) {
            return false;
        }
        //3、要删除的节点有两个子节点
        else if (current.leftChild != null && current.rightChild != null) {
            return false;
        }
        //2、要删除的节点有一个子节点,直接将其砍断,将其子节点与其父节点连接起来即可,要考虑特殊情况就是删除根节点,因为根节点没有父节点
        else {
            return false;
        }
    }

    public boolean deleteNoChild(BNode node, boolean isLeftChild) {
        if (node == root) {
            root = null;
            return true;
        }
        if (isLeftChild) {
            node.parent.leftChild = null;
        } else {
            node.parent.rightChild = null;
        }
        return true;
    }

    public boolean deleteOneChild(BNode node, boolean isLeftChild) {
        if (node.leftChild == null) {
            if (node == root) {
                root = node.rightChild;
                node.parent = null;
                return true;
            }
            if (isLeftChild) {
                node.parent.leftChild = node.rightChild;
            } else {
                node.parent.rightChild = node.rightChild;
            }
        } else {
            if (node == root) {
                root = node.leftChild;
                node.parent = null;
                return true;
            }
            if (isLeftChild) {
                node.parent.leftChild = node.leftChild;
            } else {
                node.parent.rightChild = node.rightChild;
            }
        }
        return true;
    }

    public boolean deleteTwoChild(BNode node, boolean isLeftChild) {
        BNode successor = getSuccessor(node);
        if (node == root) {
            successor.leftChild = root.leftChild;
            successor.rightChild = root.rightChild;
            successor.parent = null;
            root = successor;
        } else if (isLeftChild) {
            node.parent.leftChild = successor;
        } else {
            node.parent.rightChild = successor;
        }
        //connect successor to node's left child
        successor.leftChild = node.leftChild;
        return true;
    }

    //获得要删除节点的后继节点(中序遍历的下一个节点)
    public BNode getSuccessor(BNode delNode) {
        BNode successor = delNode;
        BNode current = delNode.rightChild;
        while (current != null) {
            successor = current;
            current = current.leftChild;
        }
        if (successor != delNode.rightChild) {
            (successor).leftChild = successor.rightChild;
            if (successor.rightChild != null) {
                //删除后续节点在原来的位置
                successor.rightChild.parent = successor.parent;
            }
            //将后续节点放到正确的位置,与右边连上
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • TreeSet集合解析

     TreeSet是实现Set接口的实现类。所以它存储的值是唯一的,同时也可以对存储的值进行排序,排序用的是二叉树原理。所以要理解这个类,必须先简单理解一下什么...

    Kevin_Zhang
  • [ Java学习基础 ] Java构造函数

    Kevin_Zhang
  • J2EE规范总结

    Kevin_Zhang
  • GR运维手册 - 第一册 苦海岸边,GR的基础知识

    作者简介: ? 刘伟 云和恩墨开源解决方案事业部首席架构师 多年一线互联网企业DBA经历,对MySQL、NoSQL,PostgreSQL等各类开源数据库均有涉猎...

    数据和云
  • Rafy 领域实体框架 - 树型实体功能(自关联表)

    在 Rafy 领域实体框架中,对自关联的实体结构做了特殊的处理,下面对这一功能进行讲解。 场景 在开发数据库应用程序时,往往会遇到自关联表的场景。例如,分类信息...

    用户1172223
  • 一文搞定 Redis 复制(全会的举个手看看)

    Step 2:从节点只是保存了 slaveof 命令中主节点的信息,并没有立即发起复制。

    良月柒
  • 红黑树(二):删除操作

    构造上,节点会有三种可能:其一是删除节点的孩子都为Nil,其二是删除节点的一个孩子节点为Nil,其三是删除节点的两个孩子节点都不为Nil。而如果两个节点都不为N...

    每天学Java
  • 重温数据结构:理解 B 树、B+ 树特点及使用场景

    B 树就是常说的“B 减树(B- 树)”,又名平衡多路(即不止两个子树)查找树,它和平衡二叉树的不同有这么几点:

    张拭心 shixinzhang
  • python学习之selenium的xpath轴的用法,附案例

    在 XPath 中,有七种类型的节点:元素、属性、文本、命名空间、处理指令、注释以及文档节点(或称为根节点)。

    吾爱乐享
  • 使用虚拟节点改进的一致性哈希算法

    1 作者:@lionets 分析缺点 连接:http://my.oschina.net/lionets/blog/288066 2 作者:@糖拌咸鱼 ...

    程序员小王

扫码关注云+社区

领取腾讯云代金券