文档章节

数据结构与算法04 之二叉树

乐在克里特
 乐在克里特
发布于 2017/02/23 14:53
字数 2209
阅读 5
收藏 0
点赞 0
评论 0

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

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

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

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

         ·该节点是叶节点,没有子节点

         ·该节点有一个子节点

         ·该节点有两个子节点

         第一种最简单,第二种也还是比较简单的,第三种就相当复杂了。

下面分析这三种删除情况:

        1.要删除叶节点,只需要改变该节点的父节点对应子字段的值即可,由指向该节点改为null就可以了。垃圾回收器会自动回收叶节点,不需要自己手动删掉;

        2.当节点有一个子节点时,这个节点只有两个连接:连向父节点和连向它唯一的子节点。需要从这个序列中剪断这个节点,把它的子节点直接连到它的父节点上即可,这个过程要求改变父节点适当的引用(左子节点还是右子节点),指向要删除节点的子节点即可;

         3.第三种情况最复杂,如果要删除有两个子节点的节点,就不能只用它的一个子节点代替它,比如要删除节点25,如果用35取代它,那35的左子节点是15呢还是30?

   

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

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

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

         ·把后继父节点的leftChild字段置为后继的右子节点;

         ·把后继的rightChild字段置为要删除节点的右子节点;

         ·把待删除节点从它父节点的leftChild或rightChild字段删除,把这个字段置为后继;

         ·把待删除的左子节点移除,将后继的leftChild字段置为待删除节点的左子节点。

        如下图所示:

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

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

 

  1. public class BinaryTree {  
  2.     private BNode root; //根节点  
  3.       
  4.     public BinaryTree() {  
  5.         root = null;  
  6.     }  
  7.       
  8.     //二叉搜索树查找的时间复杂度为O(logN)  
  9.     public BNode find(int key) { //find node with given key  
  10.         BNode current = root;  
  11.         while(current.key != key) {  
  12.             if(key < current.key) {  
  13.                 current = current.leftChild;  
  14.             }  
  15.             else {  
  16.                 current = current.rightChild;  
  17.             }  
  18.             if(current == null) {  
  19.                 return null;  
  20.             }  
  21.         }  
  22.         return current;  
  23.     }  
  24.       
  25.     //插入节点  
  26.     public void insert(int key, double value) {  
  27.         BNode newNode = new BNode();  
  28.         newNode.key = key;  
  29.         newNode.data = value;  
  30.         if(root == null) { //if tree is null  
  31.             root = newNode;  
  32.         }  
  33.         else {  
  34.             BNode current = root;  
  35.             BNode parent;  
  36.             while(true) {  
  37.                 parent = current;  
  38.                 if(key < current.data) { //turn left   ?:应为current.key
  39.                     current = current.leftChild;  
  40.                     if(current == null) {  
  41.                         parent.leftChild = newNode;  
  42.                         newNode.parent = parent;  
  43.                         return;  
  44.                     }  
  45.                 }  
  46.                 else { //turn right  
  47.                     current = current.rightChild;  
  48.                     if(current == null) {  
  49.                         parent.rightChild = newNode;  
  50.                         newNode.parent = parent;  
  51.                         return;  
  52.                     }  
  53.                 }  
  54.             }  
  55.         }  
  56.     }  
  57.       
  58.     //遍历二叉树  
  59.     public void traverse(int traverseType) {  
  60.         switch(traverseType)  
  61.         {  
  62.         case 1: System.out.println("Preorder traversal:");  
  63.                 preOrder(root);//前向遍历  
  64.                 break;  
  65.         case 2: System.out.println("Inorder traversal:");  
  66.                 inOrder(root);//中向遍历  
  67.                 break;  
  68.         case 3: System.out.println("Postorder traversal:");  
  69.                 postOrder(root);//后向遍历  
  70.                 break;  
  71.         default: System.out.println("Inorder traversal:");  
  72.                 inOrder(root);  
  73.                 break;  
  74.         }  
  75.         System.out.println("");  
  76.     }  
  77.       
  78.     //前向遍历  :(右子树,左子树)
  79.     private void preOrder(BNode localRoot) {  
  80.         if(localRoot != null) {  
  81.             System.out.print(localRoot.data + " ");  
  82.             preOrder(localRoot.leftChild);  
  83.             preOrder(localRoot.rightChild);  
  84.         }  
  85.     }  
  86.       
  87.     //中向遍历  :(左,节点,右)
  88.     private void inOrder(BNode localRoot) {  
  89.         if(localRoot != null) {  
  90.             inOrder(localRoot.leftChild);  
  91.             System.out.print(localRoot.data + " ");  
  92.             inOrder(localRoot.rightChild);  
  93.         }  
  94.     }  
  95.       
  96.     //后向遍历  :(左子树,右子树)
  97.     private void postOrder(BNode localRoot) {  
  98.         if(localRoot != null) {  
  99.             postOrder(localRoot.leftChild);  
  100.             postOrder(localRoot.rightChild);  
  101.             System.out.print(localRoot.data + " ");  
  102.         }  
  103.     }  
  104.       
  105.     //查找最小值  
  106.     /*根据二叉搜索树的存储规则,最小值应该是左边那个没有子节点的那个节点*/  
  107.     public BNode minNumber() {  
  108.         BNode current = root;  
  109.         BNode parent = root;  
  110.         while(current != null) {  
  111.             parent = current;  
  112.             current = current.leftChild;  
  113.         }     
  114.         return parent;  
  115.     }  
  116.       
  117.     //查找最大值  
  118.     /*根据二叉搜索树的存储规则,最大值应该是右边那个没有子节点的那个节点*/  
  119.     public BNode maxNumber() {  
  120.         BNode current = root;  
  121.         BNode parent = root;  
  122.         while(current != null) {  
  123.             parent = current;  
  124.             current = current.rightChild;  
  125.         }     
  126.         return parent;  
  127.     }  
  128.       
  129.     //删除节点  
  130.     /* 
  131.      * 删除节点在二叉树中是最复杂的,主要有三种情况: 
  132.      * 1. 该节点没有子节点(简单) 
  133.      * 2. 该节点有一个子节点(还行) 
  134.      * 3. 该节点有两个子节点(复杂) 
  135.      * 删除节点的时间复杂度为O(logN) 
  136.      */  
  137.     public boolean delete(int key) {  
  138.         BNode current = root;  
  139. //      BNode parent = root;  
  140.         boolean isLeftChild = true;  
  141.           
  142.         if(current == null) {  
  143.             return false;  
  144.         }  
  145.         //寻找要删除的节点  
  146.         while(current.data != key) {  
  147. //          parent = current;  
  148.             if(key < current.key) {  
  149.                 isLeftChild = true;  
  150.                 current = current.leftChild;  
  151.             }  
  152.             else {  
  153.                 isLeftChild = false;  
  154.                 current = current.rightChild;  
  155.             }  
  156.             if(current == null) {  
  157.                 return false;  
  158.             }  
  159.         }  
  160.           
  161.         //找到了要删除的节点,下面开始删除  
  162.         //1. 要删除的节点没有子节点,直接将其父节点的左子节点或者右子节点赋为null即可  
  163.         if(current.leftChild == null && current.rightChild == null) {  
  164.             return deleteNoChild(current, isLeftChild);  
  165.         }  
  166.           
  167.         //3. 要删除的节点有两个子节点  
  168.         else if(current.leftChild != null && current.rightChild != null) {  
  169.             return deleteTwoChild(current, isLeftChild);  
  170.         }  
  171.           
  172.         //2. 要删除的节点有一个子节点,直接将其砍断,将其子节点与其父节点连起来即可,要考虑特殊情况就是删除根节点,因为根节点没有父节点  
  173.         else {  
  174.             return deleteOneChild(current, isLeftChild);  
  175.         }  
  176.           
  177.     }  
  178.       
  179.     public boolean deleteNoChild(BNode node, boolean isLeftChild) {  
  180.         if(node == root) {  
  181.             root = null;  
  182.             return true;  
  183.         }  
  184.         if(isLeftChild) {  
  185.             node.parent.leftChild = null;  
  186.         }  
  187.         else {  
  188.             node.parent.rightChild = null;  
  189.         }  
  190.         return true;  
  191.     }  
  192.       
  193.     public boolean deleteOneChild(BNode node, boolean isLeftChild) {  
  194.         if(node.leftChild == null) {  
  195.             if(node == root) {  
  196.                 root = node.rightChild;  
  197.                 node.parent = null;  
  198.                 return true;  
  199.             }  
  200.             if(isLeftChild) {  
  201.                 node.parent.leftChild  = node.rightChild;  
  202.             }  
  203.             else {  
  204.                 node.parent.rightChild = node.rightChild;  
  205.             }  
  206.             node.rightChild.parent = node.parent;  
  207.         }  
  208.         else {  
  209.             if(node == root) {  
  210.                 root = node.leftChild;  
  211.                 node.parent = null;  
  212.                 return true;  
  213.             }  
  214.             if(isLeftChild) {  
  215.                 node.parent.leftChild  = node.leftChild;  
  216.             }  
  217.             else {  
  218.                 node.parent.rightChild = node.leftChild;  
  219.             }  
  220.             node.leftChild.parent = node.parent;  
  221.         }  
  222.         return true;  
  223.     }  
  224.       
  225.     public boolean deleteTwoChild(BNode node, boolean isLeftChild) {  
  226.         BNode successor = getSuccessor(node);  
  227.         if(node == root) {  
  228.             successor.leftChild = root.leftChild;  
  229.             successor.rightChild = root.rightChild;  
  230.             successor.parent = null;  
  231.             root = successor;  
  232.         }  
  233.         else if(isLeftChild) {  
  234.             node.parent.leftChild = successor;  
  235.         }  
  236.         else {  
  237.             node.parent.rightChild = successor;  
  238.         }  
  239.         successor.leftChild = node.leftChild;//connect successor to node's left child  
  240.         return true;  //不需要加successor.rightChild = node.rightChild;是因为下面获取后继时处理过了
  241.     }  
  242.       
  243.     //获得要删除节点的后继节点(中序遍历的下一个节点)  
  244.     public BNode getSuccessor(BNode delNode) {  
  245.         BNode successor = delNode;  
  246.         BNode current = delNode.rightChild;  
  247.         while(current != null) {  
  248.             successor = current;  
  249.             current = current.leftChild;  
  250.         }  
  251.         if(successor != delNode.rightChild) {  
  252.             successor.parent.leftChild = successor.rightChild;  
  253.             if(successor.rightChild != null) {        
  254.                 successor.rightChild.parent = successor.parent;//删除后续节点在原来的位置  
  255.             }  
  256.             successor.rightChild = delNode.rightChild;//将后续节点放到正确位置,与右边连上  
  257.         }  
  258.         return successor;  
  259.     }  
  260. }  
  261.   
  262. class BNode {  
  263.     public int key;  
  264.     public double data;  
  265.     public BNode parent;  
  266.     public BNode leftChild;  
  267.     public BNode rightChild;  
  268.       
  269.     public void displayNode() {  
  270.         System.out.println("{" + key + ":" + data + "}");  
  271.     }  
  272. }  

   

 

http://blog.csdn.net/eson_15/article/details/51138663#java

© 著作权归作者所有

共有 人打赏支持
乐在克里特
粉丝 15
博文 265
码字总数 394729
作品 0
杭州
程序员
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian ⋅ 2017/08/30 ⋅ 0

排序算法之冒泡排序

关于数据结构和算法,有人可能回觉得很难,还有人觉得工作中用不到.其实简单的数据结构和算法不难,对于一个有基本CS素养的工程师,简单的算法是应该能够徒手写出来的.所以我准备总结一下简单的数...

Lubby ⋅ 2015/05/14 ⋅ 0

Java学习资料-Java常用算法-二叉树算法

二叉树算法的数据结构: 二叉树结点Node实现与c中的区别是,c中采用的是结构体,而java中是用类来实现,而在c++的教材中,类是一种自定义数据结构。 二叉树的leftchild和rightchild在c中是利...

晓阳 ⋅ 2015/01/28 ⋅ 0

二叉树,排序二叉树

说到二叉树,这可是数据结构里面的非常重要的一种数据结构,二叉树是树的一种,本身具有递归性质,所以基于二叉树的一些算法很容易用递归算法去实现。作为一种非线性结构,比起线性结构还是相...

长平狐 ⋅ 2013/12/25 ⋅ 0

狮子的魂/celib

celib是使用ANSI C开发的一个扩展类库(c extend library),包含了一些常用的数据结构和算法的封装,可以用于应用或者学习。 目前已经包含的封装如下: (01). 动态数组。 (02). bitmap。 (03)...

狮子的魂 ⋅ 2014/09/13 ⋅ 0

C 扩展类库--celib

celib 是使用ANSI C开发的一个扩展类库(c extend library),包含了一些常用的数据结构和算法的封装,可以应用到项目或者用于学习。 目前已经包含的封装如下: (01). 动态数组。 (02). bitmap...

狮子的魂 ⋅ 2014/01/03 ⋅ 0

OJ 有序树转二叉树

Time Limit: 1 Sec Memory Limit: 4 MB Description 计算输入有序树的深度和有序树转化为二叉树之后树的深度。 Input 输入包含多组数据。每组数据第一行为一个整数n(2<=n<=30000)代表节点的...

流氓兔来啦 ⋅ 2016/11/07 ⋅ 0

二叉搜索树的简明实现(ES5 & ES6)

二叉树 & 二叉搜索树 二叉树(Binary Tree)是 n(n >= 0)个节点的有限集合,集合为空集时,叫作空二叉树;不为空时,由根节点及左子树、右子树组成,左子树、右子树也都是二叉树。 从这个描...

天方夜 ⋅ 2017/11/24 ⋅ 0

数据结构与算法——搜索二叉树

基础的数据结构一般都会包含插入、删除、查找和修改等几个基本的操作。对于搜索二叉树而言,数据的插入和删除操作都是在叶子结点进行。搜索二叉树主要方便于数据的查找,其查找算法复杂度为O...

木兰宿莽 ⋅ 2016/11/05 ⋅ 0

C语言/C++编程新手入门基础知识整理学习

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 04/01 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CENTOS7防火墙命令记录

安装Firewall命令: yum install firewalld firewalld-config Firewall开启常见端口命令: firewall-cmd --zone=public --add-port=80/tcp --permanent firewall-cmd --zone=public --add-po......

cavion ⋅ 26分钟前 ⋅ 0

【C++】【STL】利用chromo来测量程序运行时间与日志时间打印精确到微秒

直接上代码吧,没啥好说的。头疼。 #include <iostream>#include <string>#include <ctime>#include <sstream>#include <iomanip>#include <thread>#include <chrono>using ......

muqiusangyang ⋅ 29分钟前 ⋅ 0

Mac环境下svn的使用

在Windows环境中,我们一般使用TortoiseSVN来搭建svn环境。在Mac环境下,由于Mac自带了svn的服务器端和客户端功能,所以我们可以在不装任何第三方软件的前提下使用svn功能,不过还需做一下简...

故久呵呵 ⋅ 39分钟前 ⋅ 0

破解公司回应苹果“USB限制模式”:已攻破

本周四,苹果发表声明称 iOS 中加入了一项名为“USB 限制模式”的功能,可以防止 iPhone 在连接其他设备的时候被破解,并且强调这一功能并不是针对 FBI 等执法部门,为的是保护用户数据安全。...

六库科技 ⋅ 40分钟前 ⋅ 0

MyBtais整合Spring Boot整合,TypeHandler对枚举类(enum)处理

概要 问题描述 我想用枚举类来表示用户当前状态,枚举类由 code 和 msg 组成,但我只想把 code 保存到数据库,查询处理,能知道用户当前状态,这应该怎么做呢?在 Spring 整合MyBatis 的时候...

Wenyi_Feng ⋅ 59分钟前 ⋅ 0

synchronized与Lock的区别

# <center>王梦龙的读书笔记第一篇</center> ## <center>-synchronized与Lock的区别</centre> ###一、从使用场景来说 + synchronized 是能够注释代码块、类、方法但是它的加锁是和解锁使用一......

我不想加班 ⋅ 今天 ⋅ 0

VConsole的使用

手机端控制台打印输出,方便bug的排查。 首先需要引入vconsole.min.js 文件,然后在文件中创造实例。就能直接使用了。 var vConsole = new VConsole(); vConsole的文件地址...

大美琴 ⋅ 今天 ⋅ 0

Java NIO之字符集

1 字符集和编解码的概念 首先,解释一下什么是字符集。顾名思义,就是字符的集合。它的初衷是把现实世界的符号映射为计算机可以理解的字节。比如我创造一个字符集,叫做sex字符集,就包含两个...

士别三日 ⋅ 今天 ⋅ 0

Spring Bean基础

1、Bean之间引用 <!--如果Bean配置在同一个XML文件中,使用local引用--><ref bean="someBean"/><!--如果Bean配置在不同的XML文件中,使用ref引用--><ref local="someBean"/> 其实两种......

霍淇滨 ⋅ 今天 ⋅ 0

05、基于Consul+Upsync+Nginx实现动态负载均衡

1、Consul环境搭建 下载consul_0.7.5_linux_amd64.zip到/usr/local/src目录 cd /usr/local/srcwget https://releases.hashicorp.com/consul/0.7.5/consul_0.7.5_linux_amd64.zip 解压consu......

北岩 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部