Java二叉树查询原理深入分析讲解

　　二叉查询树
　　概述
　　二叉树（Binarytree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分
　　特点
　　树同时具有数组查询的效率、链表增删、改的性能
　　右子树的结点比左子树的节点大
　　查找法
　　搜索的数字如果比节点大则往右搜索，搜索的数字如果比节点小则往左搜索结点实现原理
　　插入实现原理
　　int〔〕arrs｛5，2，1，4，3，9，7，6，8｝；如果树是空树，插入节点就直接放入到根结点如果树不是空树，则插入的数字于根结点的数字进行比较如果插入的值小于于结点的数字，则往左子树插入如果左子结点没有元素就插入到左子结点中如果左子结点有元素，就可以设计一个引用（游标）指向左子节点，并且再次和待插入的执行左子结点进行比较，直到找到插入的位置如果插入的值大于结点的数字，则往右子树插入判断右子结点是否存在值，如果不存在则直接插入判断右子结点是否存在值，如果存在则通过一个引用指向右子结点继续和待插入的值进行比较，直到找到插入的位置
　　总结：
　　小往左，大往右
　　左子数永远小于右子树
　　遍历实现原理
　　中序遍历：左根右
　　通过中序遍历就可以将二叉树查找树的进行顺序输出
　　总结：
　　始终贯彻左根右的原则、由内层向外层拆分
　　int〔〕arrs｛1，2，3，4，5，6，7，8，9｝；删除实现原理
　　提供一个待删除的结点的值，根据值从二叉查找树找到需要删除的结点
　　找到待删除结点的父类结点，并且要根据待删除结点在父类结点的左右子树的位置，设置为null进行删除
　　需要考虑结点的三种情况
　　情况1：待删除的结点没有子结点
　　直接让父类结点的对应目标结点引用设置为null即可
　　情况2：待删除的结点有一个子节点
　　将待删除的父类结点对应子节点的引用指向待删除结点的子节点
　　情况3：待删除的结点有两个子节点从左子树中找到最大的结点进行删除，并且将最大的结点的值放入到待删除结点从右子树中找到最小的结点进行删除，并且将最小的结点的值放入（替换）到待删除结点
　　（上述两种删除方法：需要将待删除结点指向新创建（替换后的）的结点，并且将新的结点（替换后的）的左右结点指向待删除的左右子树的结点）
　　删除的结点是根节点的情况情况1：根节点没有子节点，直接将根结点指向null情况2：根结点有一个子节点，则根结点直接指向子节点情况3：根结点有两个子节点
　　可以从左子树中找到最大值删除结点，然后将最大值覆盖（替换）根节点
　　可以从右子树中找到最小值删除结点，然后将最小值覆盖（替换）根节点
　　结点插入与遍历案例BinarySearchTree类
　　packageAlgorithm；publicclassBinarySearchTree｛Noderoot；定义根节点结点插入方法publicvoidinsert（intvalue）｛if（rootnull）｛1。如果树是空树，插入节点就直接放入到根结点rootnewNode（value）；｝else｛如果树不是空树，则插入的数字于根结点的数字进行比较2。如果插入的值小于于结点的数字，则往左子树插入Nodenoderoot；声明一个游标结点，开始指向根节点while（true）｛并且再次和待插入的执行左子结点进行比较，直到找到插入的位置if（valuenode。value）｛如果插入的值小于于结点的数字，则往左子树插入2。1如果左子结点没有元素就插入到左子结点中if（node。leftnull）｛node。leftnewNode（value）；break；如果找到插入的位置，则跳出while循环｝else｛如果左子结点有元素，就可以设计一个引用（游标）指向左子节点，并且再次和待插入的执行左子结点进行比较，直到找到插入的位置游标指向左子节点nodenode。left；｝｝else｛如果插入的值大于结点的数字，则往右子树插入判断右子结点是否存在值，如果不存在则直接插入if（node。rightnull）｛node。rightnewNode（value）；break；｝else｛判断右子结点是否存在值，如果存在则通过一个引用指向右子结点继续和待插入的值进行比较，直到找到插入的位置游标指向右子节点nodenode。right；｝｝｝｝｝定义左右结点常量publicstaticfinalintLEFT0；左子节点publicstaticfinalintRIGHT1；右子节点结点查找方法publicvoiddeleteNode（intvalue）｛定义游标从根节点开始查询Nodenoderoot；定义目标结点Nodetargetnull；定义目标结点的父类结点Nodeparentnull；目标结点的类型为，左子节点或者右子节点intnodeType0；0代表左子节点1代表右子节点while（node！null）｛游标不为空，如果为空则没有子节点，无法删除if（node。valuevalue）｛如果目标结点的值和需要删除结点的值相同找到结点targetnode；break；｝elseif（valuenode。value）｛如果值不同，则判断目标结点值是否小于node结点保存父类结点parentnode；游标指向左子节点nodenode。left；nodeTypeLEFT；｝else｛如果值不同，且目标结点值大于node结点保存父类结点parentnode；游标指向右子节点nodenode。right；nodeTypeRIGHT；｝｝如果没找到需要删除的目标结点if（targetnull）｛System。out。println（没有找到要删除的结点）；return；｝删除结点的三种情况if（target。leftnulltarget。rightnull）｛情况1：待删除的结点没有子结点if（parentnull）｛删除的结点没有子结点将root设置为null即可rootnull；return；｝判断目标的结点是左子节点还是右子节点if（nodeTypeLEFT）｛将父类的左子节点设置为nullparent。leftnull；｝else｛将父类的右子节点设置为nullparent。rightnull；｝｝elseif（target。left！nulltarget。right！null）｛情况2：待删除的结点有2个子节点两个子节点，从target右子树查找最小的值Nodemintarget。right；遍历左子树while（min。left！null）｛minmin。left；｝将最小的结点进行删除deleteNode（min。value）；将待删除的结点替换成最小的结点的值target。valuemin。value；｝else｛情况3：待删除的结点有1个子节点删除结点是根节点if（parentnull）｛if（target。left！null）｛判断是左子节点还是右子节点有值roottarget。left；根节点目标左子结点｝else｛roottarget。right；根节点目标右子结点｝｝只有一个子节点if（nodeTypeLEFT）｛如果是左子节点if（target。left！null）｛将父类的左子节点，指向待删除结点的左子节点parent。lefttarget。left；｝else｛如果是右子节点将父类的左子节点，指向待删除结点的右子节点parent。lefttarget。right；｝｝else｛if（target。right！null）｛将父类的右子节点，指向待删除结点的左子节点parent。righttarget。left；｝else｛如果是右子节点将父类的右子节点，指向待删除结点的右子节点parent。righttarget。right；｝｝｝｝实现中序遍历publicvoidmidTraversal（Nodenode）｛if（nodenull）｛进行判断结点不能为空，如果为空则退出return；｝else｛如果结点不为null，则执行下列遍历语句首先，遍历左节点midTraversal（node。left）；打印根节点System。out。print（node。value，）；最后遍历右子结点midTraversal（node。right）；｝｝创建一个结点类publicstaticclassNode｛intvalue；存储值Nodeleft；左子树Noderight；右子树带参构造方法，传入value赋值publicNode（intvalue）｛this。valuevalue；｝｝｝TestBST测试类packageAlgorithm；publicclassTestBST｛publicstaticvoidmain（String〔〕args）｛int〔〕arrs｛5，2，1，4，3，9，7，6，8｝；创建二叉查询树BinarySearchTreetreenewBinarySearchTree（）；将数组中的元素构造成二叉查询树for（inti0；iarrs。length；i）｛tree。insert（arrs〔i〕）；｝删除结点tree。deleteNode（20）；中序遍历根结点tree。midTraversal（tree。root）；｝｝