二叉排序树的实现与基本操作

二叉排序树又称二叉查找树。它或者是一颗空树,或者是具有以下性质的二叉树:

①如果左子树不空,那么左子树上所有结点的值均小于它的根结点的值;

②如果右子树不空,那么右子树上所有结点的值均大于它的根结点的值;

③左右子树也分别为二叉排序树。

以下代码实现了:

  • 二叉树的构建
  • 二叉树的中、前、后、层序遍历
  • 二叉树中结点的最大距离
import java.util.LinkedList;
import java.util.Queue;
class Node{
 public int data;
 public Node left;
 public Node right;
 public int leftMaxDistance;
 public int rightMaxDistance;
 public Node(int data){
 this.data=data;
 this.left=null;
 this.right=null;
 }
}
/**
 * @author TY
 * 实现二叉排序树,包括插入、中序遍历、先序遍历、后序遍历、计算所有节点的最大距离的功能
 */
public class BinaryTree {
 private Node root;
 public BinaryTree(){
 root=null;
 }
 public void insert(int data){
 Node newNode=new Node(data);
 if(root==null)
 root=newNode;
 else{
 Node current=root;
 Node parent;
 while (true) {//寻找插入位置
 parent=current;
 if(data<current.data){
 current=current.left;
 if(current==null){
 parent.left=newNode;
 return;
 }
 }else{
 current=current.right;
 if (current==null) {
 parent.right=newNode;
 return;
 }
 }
 }
 }
 }
 //将数值输入构建二叉树
 public void buildTree(int[] data){
 for (int i = 0; i < data.length; i++) {
 insert(data[i]);
 }
 }
 //中序遍历方法递归实现
 public void inOrder(Node localRoot){
 if(localRoot!=null){
 inOrder(localRoot.left);
 System.out.print(localRoot.data+" ");
 inOrder(localRoot.right);
 }
 }
 public void inOrder(){
 this.inOrder(this.root);
 }
 //先序遍历方法递归实现
 public void preOrder(Node localRoot){
 if(localRoot!=null){
 System.out.print(localRoot.data+" ");
 preOrder(localRoot.left);
 preOrder(localRoot.right);
 }
 }
 public void preOrder(){
 this.preOrder(this.root);
 }
 //后序遍历方法递归实现
 public void postOrder(Node localRoot){
 if(localRoot!=null){
 postOrder(localRoot.left);
 postOrder(localRoot.right);
 System.out.print(localRoot.data+" ");
 }
 }
 public void postOrder(){
 this.postOrder(this.root);
 }
 /**
 * 层序遍历二叉树:现将根结点放入队列中,然后每次都从队列中取一个结点打印该结点的值,
 * 若这个结点有子结点,则将它的子结点放入队列尾,直到队列为空
 */
 public void layerTranverse(){
 if(this.root==null)
 return;
 Queue<Node> q=new LinkedList<Node>();
 q.add(this.root);
 while(!q.isEmpty()){
 Node n=q.poll();
 System.out.print(n.data+" ");
 if(n.left!=null)
 q.add(n.left);
 if(n.right!=null)
 q.add(n.right);
 }
 }
 private int maxLen=0;
 private int max(int a,int b){
 return a>b?a:b;
 }
 public void findMaxDistance(Node root){
 if(root==null)
 return;
 if(root.left==null)
 root.leftMaxDistance=0;
 if(root.right==null)
 root.rightMaxDistance=0;
 if(root.left!=null)
 findMaxDistance(root.left);
 if(root.right!=null)
 findMaxDistance(root.right);
 //计算左字树中距离根结点的最大距离
 if(root.left!=null)
 root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+1;
 //计算右字树中距离根结点的最大距离
 if(root.right!=null)
 root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+1;
 //获取二叉树所有结点的最大距离
 if(root.leftMaxDistance+root.rightMaxDistance>maxLen){
maxLen=root.leftMaxDistance+root.rightMaxDistance;
 }
 }
 public static void main(String[] args) {
 BinaryTree biTree=new BinaryTree();
 int[] data={2,8,7,4,9,3,1,6,7,5};
 biTree.buildTree(data);
 System.out.print("二叉树的中序遍历:");
 biTree.inOrder();
 System.out.println();
 System.out.print("二叉树的先序遍历:");
 biTree.preOrder();
 System.out.println();
 System.out.print("二叉树的后序遍历:");
 biTree.postOrder();
 System.out.println();
 System.out.print("二叉树的层序遍历:");
 biTree.layerTranverse();
 System.out.println();
 biTree.findMaxDistance(biTree.root);
 System.out.println("二叉树中结点的最大距离:"+biTree.maxLen);
 }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持我们!

(0)

相关推荐

  • java使用归并删除法删除二叉树中节点的方法

    本文实例讲述了java使用归并删除法删除二叉树中节点的方法.分享给大家供大家参考.具体分析如下: 实现的思想很简单: first:找到要删除的节点 second:如果删除的节点没有右子树那么左子树链到父节点 third:如果删除的节点没有左子树那么右子树链到父节点 forth:如果删除的节点又左右孩子,那么可以归并删除节点后的子树:方法有两种一种是用删除节点的左子树的最右节点,指向删除节点的右子树,另一种是用删除节点的用字数的最左节点指向删除节点的左子树. Java 实现如下: public v

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

  • Java实现求二叉树的深度和宽度

    这个是常见的对二叉树的操作.总结一下: 设节点的数据结构,如下: 复制代码 代码如下: class TreeNode {     char val;     TreeNode left = null;     TreeNode right = null; TreeNode(char _val) {         this.val = _val;     } } 1.二叉树深度 这个可以使用递归,分别求出左子树的深度.右子树的深度,两个深度的较大值+1即可. 复制代码 代码如下: // 获取最大

  • JAVA 实现二叉树(链式存储结构)

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • Java实现表达式二叉树

    什么是二叉树,这里不再介绍,可以自行百度:二叉树.在这里利用java实现"表达式二叉树". 表达式二叉树的定义  第一步先要搞懂表达式二叉树是个什么东东?举个栗子,表达式:(a+b×(c-d))-e/f.将数字放在叶子节点,将操作符放在分支节点,就构成了一个二叉树,由于存储的是一个表达式,称之为"表达式二叉树". 童靴们可能好奇这个到底是怎么构建的?就拿45+23*56/2-5来说吧.首先取出第一个数字45放在叶子节点,遇到"+"后将其放到分支节

  • Java的二叉树排序以及遍历文件展示文本格式的文件树

    Java二叉树排序算法 排序二叉树的描述也是一个递归的描述, 所以排序二叉树的构造自然也用递归的: 排序二叉树的3个特征: 1:当前node的所有左孩子的值都小于当前node的值: 2:当前node的所有右孩子的值都大于当前node的值: 3:孩子节点也满足以上两点 package test.sort; public class BinaryNode { private int value;//current value private BinaryNode lChild;//left chil

  • 详解Java二叉排序树

    一.二叉排序树定义 1.二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree).其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ①若它的左子树非空,则左子树上所有结点的值均小于根结点的值: ②若它的右子树非空,则右子树上所有结点的值均大于根结点的值: ③左.右子树本身又各是一棵二叉排序树. 上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足BST性质的二叉树. 2.二叉排序树的性质 按中序遍历二

  • 二叉排序树的实现与基本操作

    二叉排序树又称二叉查找树.它或者是一颗空树,或者是具有以下性质的二叉树: ①如果左子树不空,那么左子树上所有结点的值均小于它的根结点的值: ②如果右子树不空,那么右子树上所有结点的值均大于它的根结点的值: ③左右子树也分别为二叉排序树. 以下代码实现了: 二叉树的构建 二叉树的中.前.后.层序遍历 二叉树中结点的最大距离 import java.util.LinkedList; import java.util.Queue; class Node{ public int data; public

  • C语言实现BST二叉排序树的基本操作

    本文实例为大家分享了C语言实现BST二叉排序树的基本操作代码,供大家参考,具体内容如下 BST-二叉排序树的几个基本操作. 头文件声明与函数定义 #include <stdio.h> #include <stdlib.h> typedef int ElemType; /** * 定义节点 */ typedef struct BSTNode{ ElemType data;//数据域 struct BSTNode *lchild,//左孩子 *rchild;//右孩子 }BSTNode

  • AngularJS中table表格基本操作示例

    本文实例讲述了AngularJS表格基本操作.分享给大家供大家参考,具体如下: css内容: table, td { border: 1px solid grey; border-collapse: collapse; padding: 5px; } HTML正文: <body ng-app=""> <div ng-init="persons=[{'name':'zhangsan','age':'20'}, {'name':'lisi','age':'19'

  • C++ 中Vector常用基本操作

    标准库vector类型是C++中使用较多的一种类模板,vector类型相当于一种动态的容器,在vector中主要有一些基本的操作,下面通过本文给大家介绍,具体内容如下所示: (1)头文件#include<vector>. (2)创建vector对象,vector<int> vec; (3)尾部插入数字:vec.push_back(a); (4)使用下标访问元素,cout<<vec[0]<<endl;记住下标是从0开始的. (5)使用迭代器访问元素. vect

  • Git 的基本操作、开发流程、实用技巧总结(陈彦贝)

    Git 是什么? Git 是一个分布式的代码管理容器,本地和远端都保有一份相同的代码. Git 仓库主要是由是三部分组成:本地代码,缓存区,提交历史,这几乎是所有操作的本质,但是为了文章更加简单易懂,就不围绕这块展开了,有兴趣的可以去了解下. 开门见山,我们直接来说说 Git 有哪些常见的操作. Git 有哪些常规操作? 我们简单说说Git有哪些常规操作,能够让我们应付简单的开发需求. 克隆代码 ✦ 克隆远端代码 git clone http://git.code.oa.com/QCFE/sql

  • GIt的基本操作详解

    目录 基本操作 安装与配置 init add与commit clone vim status diff rm(删除文件) 恢复文件 MV(重命名) Git分支操作 查看历史记录 添加标签 清屏 基本操作 安装与配置 $ git config --global user.name "runoob" $ git config --global user.email test@runoob.com $ git config --global core.editor Vim//指定文本编辑器

  • 浅谈Oracle 11g 发行版2 新安装后关于登录的一些基本操作

    Oracle 11g是在推出的最新数据库软件,Oracle 11g有400多项功能,经过了1500万个小时的测试,开发工作量达到了3.6万人/月,相当于1000名员工连续研发3年.Oracle 11g提供了高性能.伸展性.可用性和安全性,并能更方便地在低成本服务器和存储设备组成的网格上运行 ,相对过往版本而言,Oracle 11g具有了与众不同的特性 首先要注意,安装时候可以选择桌面类或者服务器类.桌面类就比较简单,不用什么配置,在安装时候提示你输入的密码,是SYS用户的密码:而服务器类,可以配

  • Vista使用教程之基本操作技巧图解教程第1/7页

    桌面与外观 相信在初接触Windows Vista时,大部分用户首先感受到的是强烈的视觉刺激--尽管从技术角度看,Windows Vista在安全性以及功能方面所做的改进更为重要--焕然一新的用户接口, Aero Glass固然美轮美奂,即便最精减的Windows Vista Basic主题同样令人惊艳.客观地说,Windows Vista在很多方面已经接近对曾经是"酷"的代表引领时尚的Apple Mac OS X形成了真正的威胁. 而在操作方面,Windows Vista则秉持了微软

  • C#针对xml基本操作及保存配置文件应用实例

    本文实例讲述了C#针对xml的基本操作及保存配置文件应用,分享给大家供大家参考.具体方法如下: 引言:这里首先介绍了xml的基本操作,后面写了一个经常用到的xml保存配置文件的实例. xml常用方法: 定义xml文档:XmlDocument xmlDoc = new XmlDocument(); 初始化xml文档:xmlDoc.Load("D:\\book.xml");//找到xml文件 创建根元素:XmlElement xmlElement = xmlDoc.CreateElemen

  • C语言对栈的实现基本操作

    c语言中栈是一种数据结构,后进先出,即最后进入栈的数据最先弹出.c语言中没有栈这种数据类型,需要自己编程构建.下面我们就一起来了解一下c语言中栈的基本操作. C语言对栈的实现基本操作,操作如下: #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <stdbool.h> typedef struct Node { int data; struct Node * pNext;

随机推荐