当前位置：移动技术网 > IT编程>开发语言>Java > 详解Java二叉排序树

详解Java二叉排序树

2019年07月22日 | 移动技术网IT编程 | 我要评论

一、二叉排序树定义
1.二叉排序树的定义
　　二叉排序树(binary sort tree)又称二叉查找(搜索)树(binary search tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(bst性质)，故二叉排序树实际上是满足bst性质的二叉树。

2.二叉排序树的性质
按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。

3.二叉排序树的插入
在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。　　
插入过程：
若二叉排序树为空，则待插入结点*s作为根结点插入到空树中；　　
当非空时，将待插结点关键字s->key和树根关键字t->key进行比较，若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

4.二叉排序树的查找
假定二叉排序树的根结点指针为 root ，给定的关键字值为 k ，则查找算法可描述为：
　　① 置初值： q ＝ root ；
　　② 如果 k ＝ q －＞ key ，则查找成功，算法结束；
　　③ 否则，如果 k ＜ q －＞ key ，而且 q 的左子树非空，则将 q 的左子树根送 q ，转步骤②；否则，查找失败，结束算法；
　　④ 否则，如果 k ＞ q －＞ key ，而且 q 的右子树非空，则将 q 的右子树根送 q ，转步骤②；否则，查找失败，算法结束。

5.二叉排序树的删除
假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论：　　
⑴ 若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可。　　
⑵ 若结点*p只有左子树pl或者只有右子树pr，则只要使pl或pr 成为其双亲结点的左子树即可。　　
⑶ 若结点*p的左、右子树均非空，先找到*p的中序前趋(或后继)结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：① 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。② 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。
6、二叉树的遍历
二叉树的遍历有三种方式，如下：
（1）前序遍历（dlr），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
（2）中序遍历（ldr），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
（3）后序遍历（lrd），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

二、代码编写
1、树节点类的定义0

package com.lin; 
/** 
 * 功能概要： 

 */ 
public class treenode { 
   
  public integer data; 
   
  /*该节点的父节点*/ 
  public treenode parent; 
   
  /*该节点的左子节点*/ 
  public treenode left; 
   
  /*该节点的右子节点*/ 
  public treenode right; 
   
  public treenode(integer data) { 
    this.data = data; 
     
  } 
 
  @override 
  public string tostring() { 
    return "treenode [data=" + data + "]"; 
  } 
     
}

2、二叉排序树的定义

package com.lin; 
 
/** 
 * 功能概要：排序/平衡二叉树 

 */ 
public class searchtree { 
   
   public treenode root; 
    
   public long size; 
     
  /** 
   * 往树中加节点  
   * @param data 
   * @return boolean 插入成功返回true 
   */ 
  public boolean addtreenode(integer data) { 
 
    if (null == root) { 
      root = new treenode(data); 
      system.out.println("数据成功插入到平衡二叉树中"); 
      return true; 
    } 
 
    treenode treenode = new treenode(data);// 即将被插入的数据 
    treenode currentnode = root; 
    treenode parentnode; 
 
    while (true) { 
      parentnode = currentnode;// 保存父节点 
      // 插入的数据比父节点小 
      if (currentnode.data > data) { 
        currentnode = currentnode.left; 
        // 当前父节点的左子节点为空 
        if (null == currentnode) { 
          parentnode.left = treenode; 
          treenode.parent = parentnode; 
          system.out.println("数据成功插入到二叉查找树中"); 
          size++; 
          return true; 
        } 
        // 插入的数据比父节点大 
      } else if (currentnode.data < data) { 
        currentnode = currentnode.right; 
        // 当前父节点的右子节点为空 
        if (null == currentnode) { 
          parentnode.right = treenode; 
          treenode.parent = parentnode; 
          system.out.println("数据成功插入到二叉查找树中"); 
          size++; 
          return true; 
        } 
      } else { 
        system.out.println("输入数据与节点的数据相同"); 
        return false; 
      } 
    }     
  } 
   
  /** 
   * @param data 
   * @return treenode 
   */ 
  public treenode findtreenode(integer data){ 
    if(null == root){ 
      return null; 
    } 
    treenode current = root; 
    while(current != null){ 
      if(current.data > data){ 
        current = current.left; 
      }else if(current.data < data){ 
        current = current.right; 
      }else { 
        return current; 
      } 
       
    } 
    return null; 
  } 
   
}

这里暂时只放了一个增加和查找的方法
3、前、中、后遍历

package com.lin; 
 
import java.util.stack; 
 
/** 
 * 功能概要： 
 */ 
public class treeorder { 
   
  /** 
   * 递归实现前序遍历 
   * @author linbingwen 
   * @since 2015年8月29日 
   * @param treenode 
   */ 
  public static void preordermethodone(treenode treenode) { 
    if (null != treenode) { 
      system.out.print(treenode.data + " "); 
      if (null != treenode.left) { 
        preordermethodone(treenode.left); 
      } 
      if (null != treenode.right) { 
        preordermethodone(treenode.right); 
 
      } 
    } 
  } 
 
  /** 
   * 循环实现前序遍历 
   * @param treenode 
   */ 
  public static void preordermethodtwo(treenode treenode) { 
    if (null != treenode) { 
      stack<treenode> stack = new stack<treenode>(); 
      stack.push(treenode); 
      while (!stack.isempty()) { 
        treenode tempnode = stack.pop(); 
        system.out.print(tempnode.data + " "); 
        // 右子节点不为null,先把右子节点放进去 
        if (null != tempnode.right) { 
          stack.push(tempnode.right); 
        } 
        // 放完右子节点放左子节点，下次先取 
        if (null != tempnode.left) { 
          stack.push(tempnode.left); 
        } 
      } 
    } 
  } 
   
  /** 
   * 递归实现中序遍历 
   * @param treenode 
   */ 
  public static void medordermethodone(treenode treenode){ 
    if (null != treenode) {      
      if (null != treenode.left) { 
        medordermethodone(treenode.left); 
      } 
      system.out.print(treenode.data + " "); 
      if (null != treenode.right) { 
        medordermethodone(treenode.right); 
      } 
    } 
     
  } 
   
  /** 
   * 循环实现中序遍历 
   * @param treenode 
   */ 
  public static void medordermethodtwo(treenode treenode){   
    stack<treenode> stack = new stack<treenode>();  
    treenode current = treenode;  
    while (current != null || !stack.isempty()) {  
      while(current != null) {  
        stack.push(current);  
        current = current.left;  
      }  
      if (!stack.isempty()) {  
        current = stack.pop();  
        system.out.print(current.data+" ");  
        current = current.right;  
      }  
    }     
  } 
   
  /** 
   * 递归实现后序遍历 
   * @param treenode 
   */ 
  public static void postordermethodone(treenode treenode){     
    if (null != treenode) {    
      if (null != treenode.left) { 
        postordermethodone(treenode.left); 
      } 
      if (null != treenode.right) { 
        postordermethodone(treenode.right); 
      } 
      system.out.print(treenode.data + " "); 
    } 
     
  } 
   
  /** 
   * 循环实现后序遍历 
   * @param treenode 
   */ 
  public static void postordermethodtwo(treenode treenode){ 
    if (null != treenode) { 
      stack<treenode> stack = new stack<treenode>(); 
      treenode current = treenode; 
      treenode rightnode = null; 
      while(current != null || !stack.isempty()) {  
        while(current != null) {  
          stack.push(current);  
          current = current.left;  
        }  
        current = stack.pop();  
        while (current != null && (current.right == null ||current.right == rightnode)) {  
          system.out.print(current.data + " ");  
          rightnode = current;  
          if (stack.isempty()){  
            system.out.println();  
            return;  
          }  
          current = stack.pop();  
        }  
        stack.push(current);  
        current = current.right;  
      }  
       
       
       
    } 
  } 
   
}

4、使用方法

package com.lin;  
/** 
 * 功能概要： 
*/ 
public class searchtreetest { 
 
  /** 
   * @param args   
   */ 
  public static void main(string[] args) { 
    searchtree tree = new searchtree(); 
    tree.addtreenode(50); 
    tree.addtreenode(80); 
    tree.addtreenode(20); 
    tree.addtreenode(60);   
    tree.addtreenode(10); 
    tree.addtreenode(30); 
    tree.addtreenode(70); 
    tree.addtreenode(90);   
    tree.addtreenode(100); 
    tree.addtreenode(40); 
    system.out.println("=============================="+"采用递归的前序遍历开始"+"=============================="); 
    treeorder.preordermethodone(tree.root); 
    system.out.println(); 
    system.out.println("=============================="+"采用循环的前序遍历开始"+"=============================="); 
    treeorder.preordermethodtwo(tree.root); 
    system.out.println(); 
    system.out.println("=============================="+"采用递归的后序遍历开始"+"=============================="); 
    treeorder.postordermethodone(tree.root); 
    system.out.println(); 
    system.out.println("=============================="+"采用循环的后序遍历开始"+"=============================="); 
    treeorder.postordermethodtwo(tree.root); 
    system.out.println(); 
    system.out.println("=============================="+"采用递归的中序遍历开始"+"=============================="); 
    treeorder.medordermethodone(tree.root); 
    system.out.println(); 
    system.out.println("=============================="+"采用循环的中序遍历开始"+"=============================="); 
    treeorder.medordermethodtwo(tree.root); 
 
  } 
 
}

输出结果：

同样，进行查找过程如下：

treenode node = tree.findtreenode(100); 
system.out.println(node);

结果是正确的

以上就是关于java二叉排序树的详细介绍，希望对大家的学习java程序设计有所帮助。

您可能感兴趣的文章:

如对本文有疑问，点击进行留言回复！！

springcloud中feign调用处理mybatis-plus Ipage反序列化问题。

通过feign接口返回的分页列表IPage，出现报错，具体报错内容如下：feign.codec.DecodeEx... [阅读全文]
大数据云计算——Azkaban组件

什么是 AzkabanAzkaban 是由 Linkedin 公司推出的一个批量工作流任务调度器，主要用于在一个... [阅读全文]
荐聊聊数据库表结构设计心得

本文讨论是一般表的设计，有一定的普遍性和通用性，当然对于特殊性的考量则不在本文讨论之列。自增 idJava 层的... [阅读全文]
SpringCloud各个组件最强总结

一、概念1.1 什么是Spring Cloud？Spring Cloud就是微服务系统架构的一站式解决方案，在平... [阅读全文]
微服务之SpringCloud

# 微服务介绍将一个原本独立的系统拆分成多个小型服务，这些小型服务都在各自独立的进程中运行，并使用轻量级机制通信... [阅读全文]
劝退记：如你如我，平庸且不甘 | 年中总结

关于我前端劝退师，最近也叫前端失业师。没能力没学历没背景，三无前端。工作第四年，想和优秀的一批人竞争，永远和自己... [阅读全文]
Flume 史上最全面的大数据学习第十篇（一）别再说不知道flume是什么了

昨天没有增加小粉丝，我反思了一下自己，是不是我写的东西太过枯燥了呀！挺难受的！算了还是不说了，每天都是美好的一天... [阅读全文]
一直想学习Java网络编程，却不知道怎么入门？

其实，我刚学习Netty的时候，也是很迷茫的，直到有一天，一个同事收到了阿里的offer，他要去阿里做中台了，临... [阅读全文]
SpringCloud相关笔记一系统架构的演变(一)

SpringCloudSpringBoot 四种属性注入小结1.@Autowired注入2.构造方法注入3.@B... [阅读全文]
面试官：说说Kafka控制器事件处理全流程

前言大家好，我是 yes。这是Kafka源码分析第四篇文章，今天来说说 Kafka控制器，即 Kafka Con... [阅读全文]

网友评论


验证码：

详解Java二叉排序树

2019年07月22日 | 移动技术网IT编程 | 我要评论

您可能感兴趣的文章:

相关文章:

网友评论