• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

下次面试若再被问到二叉树,希望你能对答如流!

技术杂谈 勤劳的小蚂蚁 3个月前 (01-13) 77次浏览 已收录 0个评论 扫描二维码

曾经有个朋友问我:二叉树可以用来干啥况?
我回答他:可以搜索、可以排序呀?
可是,排序有快速排序,归并排序,查找有二分法,甚至直接遍历查找,我干啥要使用二叉树呢?
……
这位朋友说的是有道理的,二叉树确实在实际中用的比较少,因为有更高级的树,但是二叉树作为一种最基本最典型的排序树,是研究其他树的基础。除此之外,在面试数据结构的时候,二叉树原理被问到的概率是相当高的。这篇文章建议收藏。言归正传,我们来分析分析二叉树
我们知道,在有序数组中,可以快速找到特定的值,但是想在有序数组中插入一个新的数据项,就必须首先找出新数据项插入的位置,然后将比新数据项大的数据项向后移动一位,来给新的数据项腾出空间,删除同理,这样移动很费时。显而易见,如果要做很多的插入和删除操作和删除操作,就不该选用有序数组。
另一方面,链表中可以快速添加和删除某个数据项,但是在链表中查找数据项可不容易,必须从头开始访问链表的每一个数据项,直到找到该数据项为止,这个过程很慢。
树这种数据结构,既能像链表那样快速的插入和删除,又能想有序数组那样快速查找。这里主要实现一种特殊的树——二叉(搜索)树。二叉搜索树有如下特点:一个节点的左子节点的关键字值小于这个节点,右子节点的关键字值大于或等于这个节点。插入一个节点需要根据这个规则进行插入。
删除节点时二叉搜索树中最复杂的操作,但是删除节点在很多树的应用中又非常重要,所以详细研究并总结下特点。删除节点要从查找要删的节点开始入手,首先找到节点,这个要删除的节点可能有三种情况需要考虑。
  • 该节点是叶节点,没有子节点
  • 该节点有一个子节点
  • 该节点有两个子节点
第一种最简单,第二种也还是比较简单的,第三种就相当复杂了。下面分析这三种删除情况:
要删除叶节点,只需要改变该节点的父节点对应子字段的值即可,由指向该节点改为 null 就可以了。垃圾回收器会自动回收叶节点,不需要自己手动删掉;当节点有一个子节点时,这个节点只有两个连接:连向父节点和连向它唯一的子节点。需要从这个序列中剪断这个节点,把它的子节点直接连到它的父节点上即可,这个过程要求改变父节点适当的引用(左子节点还是右子节点),指向要删除节点的子节点即可;第三种情况最复杂,如果要删除有两个子节点的节点,就不能只用它的一个子节点代替它,比如要删除节点25,如果用35取代它,那35的左子节点是15呢还是30?
因此需要考虑另一种方法,寻找它的中序后继来代替该节点。下图显示的就是要删除节点用它的后继代替它的情况,删除后还是有序的。(这里还有更麻烦的情况,即它的后继自己也有右子节点,下面再讨论。)
那么如何找后继节点呢?首先得找到要删除的节点的右子节点,它的关键字值一定比待删除节点的大。然后转到待删除节点右子节点的左子节点那里(如果有的话),然后到这个左子节点的左子节点,以此类推,顺着左子节点的路径一直向下找,这个路径上的最后一个左子节点就是待删除节点的后继。如果待删除节点的右子节点没有左子节点,那么这个右子节点本身就是后继。寻找后继的示意图如下:
找到了后继节点,现在开始删除了,先看第一种情况,后继节点是delNode右子节点的做后代,这种情况要执行以下四个步骤:
  • 把后继父节点的leftChild字段置为后继的右子节点;
  • 把后继的rightChild字段置为要删除节点的右子节点;
  • 把待删除节点从它父节点的leftChild或rightChild字段删除,把这个字段置为后继;
  • 把待删除的左子节点移除,将后继的leftChild字段置为待删除节点的左子节点。
这下图所示:
如果后继节点就是待删除节点的右子节点,这种情况就简单了,因为只需要把后继为跟的子树移到删除的节点的位置即可。如下图所示:
看到这里,就会发现删除时相当棘手的操作。实际上,因为它非常复杂,一些程序员都尝试着躲开它,他们在Node类中加了一个Boolean字段来标识该节点是否已经被删除,在其他操作之前会先判断这个节点是不是已经删除了,这样删除节点不会改变树的结构。当然树中还保留着这种已经删除的节点,对存储造成浪费,但是如果没有那么多删除的话,这也不失为一个好方法。
另外二叉树有三种遍历方式:前序、中序和后序。这个比较简单,直接看下代码即可。
下面手写个二叉搜索树的代码:
  1. publicclassBinaryTree{
  2.    privateBNode root;//根节点
  3.    publicBinaryTree(){
  4.        root =null;
  5.    }
  6.    //二叉搜索树查找的时间复杂度为O(logN)
  7.    publicBNode find(int key){//find node with given key
  8.        BNode current = root;
  9.        while(current.key != key){
  10.            if(key < current.key){
  11.                current = current.leftChild;
  12.            }
  13.            else{
  14.                current = current.rightChild;
  15.            }
  16.            if(current ==null){
  17.                returnnull;
  18.            }
  19.        }
  20.        return current;
  21.    }
  22.    //插入节点
  23.    publicvoid insert(int key,double value){
  24.        BNode newNode =newBNode();
  25.        newNode.key = key;
  26.        newNode.data = value;
  27.        if(root ==null){//if tree is null
  28.            root = newNode;
  29.        }
  30.        else{
  31.            BNode current = root;
  32.            BNode parent;
  33.            while(true){
  34.                parent = current;
  35.                if(key < current.data){//turn left
  36.                    current = current.leftChild;
  37.                    if(current ==null){
  38.                        parent.leftChild = newNode;
  39.                        newNode.parent = parent;
  40.                        return;
  41.                    }
  42.                }
  43.                else{//turn right
  44.                    current = current.rightChild;
  45.                    if(current ==null){
  46.                        parent.rightChild = newNode;
  47.                        newNode.parent = parent;
  48.                        return;
  49.                    }
  50.                }
  51.            }
  52.        }
  53.    }
  54.    //遍历二叉树
  55.    publicvoid traverse(int traverseType){
  56.        switch(traverseType)
  57.        {
  58.        case1:System.out.println("Preorder traversal:");
  59.                preOrder(root);//前向遍历
  60.                break;
  61.        case2:System.out.println("Inorder traversal:");
  62.                inOrder(root);//中向遍历
  63.                break;
  64.        case3:System.out.println("Postorder traversal:");
  65.                postOrder(root);//后向遍历
  66.                break;
  67.        default:System.out.println("Inorder traversal:");
  68.                inOrder(root);
  69.                break;
  70.        }
  71.        System.out.println("");
  72.    }
  73.    //前向遍历
  74.    privatevoid preOrder(BNode localRoot){
  75.        if(localRoot !=null){
  76.            System.out.print(localRoot.data +" ");
  77.            preOrder(localRoot.leftChild);
  78.            preOrder(localRoot.rightChild);
  79.        }
  80.    }
  81.    //中向遍历
  82.    privatevoid inOrder(BNode localRoot){
  83.        if(localRoot !=null){
  84.            inOrder(localRoot.leftChild);
  85.            System.out.print(localRoot.data +" ");
  86.            inOrder(localRoot.rightChild);
  87.        }
  88.    }
  89.    //后向遍历
  90.    privatevoid postOrder(BNode localRoot){
  91.        if(localRoot !=null){
  92.            postOrder(localRoot.leftChild);
  93.            postOrder(localRoot.rightChild);
  94.            System.out.print(localRoot.data +" ");
  95.        }
  96.    }
  97.    //查找最小值
  98.    /*根据二叉搜索树的存储规则,最小值应该是左边那个没有子节点的那个节点*/
  99.    publicBNode minNumber(){
  100.        BNode current = root;
  101.        BNode parent = root;
  102.        while(current !=null){
  103.            parent = current;
  104.            current = current.leftChild;
  105.        }  
  106.        return parent;
  107.    }
  108.    //查找最大值
  109.    /*根据二叉搜索树的存储规则,最大值应该是右边那个没有子节点的那个节点*/
  110.    publicBNode maxNumber(){
  111.        BNode current = root;
  112.        BNode parent = root;
  113.        while(current !=null){
  114.            parent = current;
  115.            current = current.rightChild;
  116.        }  
  117.        return parent;
  118.    }
  119.    //删除节点
  120.    /*
  121.     * 删除节点在二叉树中是最复杂的,主要有三种情况:
  122.     * 1. 该节点没有子节点(简单)
  123.     * 2. 该节点有一个子节点(还行)
  124.     * 3. 该节点有两个子节点(复杂)
  125.     * 删除节点的时间复杂度为O(logN)
  126.     */
  127.    publicbooleandelete(int key){
  128.        BNode current = root;
  129. //        BNode parent = root;
  130.        boolean isLeftChild =true;
  131.        if(current ==null){
  132.            returnfalse;
  133.        }
  134.        //寻找要删除的节点
  135.        while(current.data != key){
  136. //            parent = current;
  137.            if(key < current.key){
  138.                isLeftChild =true;
  139.                current = current.leftChild;
  140.            }
  141.            else{
  142.                isLeftChild =false;
  143.                current = current.rightChild;
  144.            }
  145.            if(current ==null){
  146.                returnfalse;
  147.            }
  148.        }
  149.        //找到了要删除的节点,下面开始删除
  150.        //1. 要删除的节点没有子节点,直接将其父节点的左子节点或者右子节点赋为null即可
  151.        if(current.leftChild ==null&& current.rightChild ==null){
  152.            return deleteNoChild(current, isLeftChild);
  153.        }
  154.        //3. 要删除的节点有两个子节点
  155.        elseif(current.leftChild !=null&& current.rightChild !=null){
  156.            return deleteTwoChild(current, isLeftChild);
  157.        }
  158.        //2. 要删除的节点有一个子节点,直接将其砍断,将其子节点与其父节点连起来即可,要考虑特殊情况就是删除根节点,因为根节点没有父节点
  159.        else{
  160.            return deleteOneChild(current, isLeftChild);
  161.        }
  162.    }
  163.    publicboolean deleteNoChild(BNode node,boolean isLeftChild){
  164.        if(node == root){
  165.            root =null;
  166.            returntrue;
  167.        }
  168.        if(isLeftChild){
  169.            node.parent.leftChild =null;
  170.        }
  171.        else{
  172.            node.parent.rightChild =null;
  173.        }
  174.        returntrue;
  175.    }
  176.    publicboolean deleteOneChild(BNode node,boolean isLeftChild){
  177.        if(node.leftChild ==null){
  178.            if(node == root){
  179.                root = node.rightChild;
  180.                node.parent =null;
  181.                returntrue;
  182.            }
  183.            if(isLeftChild){
  184.                node.parent.leftChild  = node.rightChild;
  185.            }
  186.            else{
  187.                node.parent.rightChild = node.rightChild;
  188.            }
  189.            node.rightChild.parent = node.parent;
  190.        }
  191.        else{
  192.            if(node == root){
  193.                root = node.leftChild;
  194.                node.parent =null;
  195.                returntrue;
  196.            }
  197.            if(isLeftChild){
  198.                node.parent.leftChild  = node.leftChild;
  199.            }
  200.            else{
  201.                node.parent.rightChild = node.leftChild;
  202.            }
  203.            node.leftChild.parent = node.parent;
  204.        }
  205.        returntrue;
  206.    }
  207.    publicboolean deleteTwoChild(BNode node,boolean isLeftChild){
  208.        BNode successor = getSuccessor(node);
  209.        if(node == root){
  210.            successor.leftChild = root.leftChild;
  211.            successor.rightChild = root.rightChild;
  212.            successor.parent =null;
  213.            root = successor;
  214.        }
  215.        elseif(isLeftChild){
  216.            node.parent.leftChild = successor;
  217.        }
  218.        else{
  219.            node.parent.rightChild = successor;
  220.        }
  221.        successor.leftChild = node.leftChild;//connect successor to node's left child
  222.        returntrue;
  223.    }
  224.    //获得要删除节点的后继节点(中序遍历的下一个节点)
  225.    publicBNode getSuccessor(BNode delNode){
  226.        BNode successor = delNode;
  227.        BNode current = delNode.rightChild;
  228.        while(current !=null){
  229.            successor = current;
  230.            current = current.leftChild;
  231.        }
  232.        if(successor != delNode.rightChild){
  233.            successor.parent.leftChild = successor.rightChild;
  234.            if(successor.rightChild !=null){      
  235.                successor.rightChild.parent = successor.parent;//删除后续节点在原来的位置
  236.            }
  237.            successor.rightChild = delNode.rightChild;//将后续节点放到正确位置,与右边连上
  238.        }
  239.        return successor;
  240.    }
  241. }
  242. classBNode{
  243.    publicint key;
  244.    publicdouble data;
  245.    publicBNode parent;
  246.    publicBNode leftChild;
  247.    publicBNode rightChild;
  248.    publicvoid displayNode(){
  249.        System.out.println("{"+ key +":"+ data +"}");
  250.    }
  251. }
(敲黑板)如果你还是应届生,那更要好好掌握二叉树的原理咯,面试出现的概率很大~ 本文建议收藏,在上班等车的时候、吃饭排队的时候可以拿出来看看。

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:下次面试若再被问到二叉树,希望你能对答如流!
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00