使用二叉排序树查找效率也非常高,当然有更稳定的二叉平衡树,但是实现起来比较困难,所以这里只实现了二叉排序树;二叉排序树的特点如下:
- 左子树中的所有节点值都小于父节点值
- 右子树中的所有节点值都大于父节点值
- 所有节点不允许出现重复,否则会破坏二叉排序树的数据结构
- 二叉排序树的中序遍历的结果就是所有元素的排序结果
- 二叉排序树是二叉树
所以,使用二叉排序树不仅仅能够实现快速查找,而且也能够实现排序。
一、使用二叉排序树实现排序(非递归建树)
package com.kdyzm.bitsorttree; import java.util.Scanner; class Node { int data; Node lchild = null; Node rchild = null; } public class BinarySortTree { public static void main(String args[]) { Scanner scanner = new Scanner(System.in); int total = scanner.nextInt(); Node root = createBinarySortTree(scanner, total); midOrderTraverse(root); } private static void midOrderTraverse(Node root) { if (root != null) { midOrderTraverse(root.lchild); System.out.print(root.data + " "); midOrderTraverse(root.rchild); } } public static Node createBinarySortTree(Scanner scanner, int total) { Node root = null; for (int i = 0; i < total; i++) { if (root == null) { int data = scanner.nextInt(); root = new Node(); root.data = data; } else { int data = scanner.nextInt(); Node node = root; while (node != null) { if (data == node.data) { //查找成功 return null; } else if (data < node.data) { if (node.lchild == null) { node.lchild = new Node(); node.lchild.data = data; break; } else { node = node.lchild; } } else { if (node.rchild == null) { node.rchild = new Node(); node.rchild.data = data; break; } else { node = node.rchild; } } } } } return root; } }
二、测试用例
使用之前的MyRandom类产生的1024个数字进行测试:
import java.util.Random; public class MyRandom { public static void main(String args[]){ int[] array=new int[1024]; for(int i=0;i<1024;i++){ array[i]=i; } for(int i=0;i<=1023;i++){ int m=new Random().nextInt(1024); int n=new Random().nextInt(1024); int temp=array[m]; array[m]=array[n]; array[n]=temp; } System.out.println("1024"); for(int i=0;i<1024;i++){ System.out.print(array[i]+" "); } System.out.println(); } }
三、测试结果
测试方法:
java MyRandom | java BinarySortTree
这个结果实际上是对二叉排序树中序遍历的结果:
四、关于查找的说明
查找的原理和过程在以上的代码中已经有了充分的体现,不赘述。
相关推荐
二叉排序树的实现 二叉排序补充概念(也可以参考书上第九章第二节) 左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的数据小于右边. ...课程设计数据结构二叉排序树
该程序演示二叉排序树的生成。 包括: 初始化二叉树 查找指定值 插入函数 打印二叉树 注:本程序为本人课堂实验程序,请勿到处转载!仅限学习交流使用!
这是数据结构实验中的二叉排序树,能够进行动态查找,将数据插入到二叉排序树中,或者从二叉排序树中删除某个元素。主要是查找功能!
一、实验目的 (1)理解动态查找表的动态生成过程; (2)任意给出一组数(不...(1)定义二叉排序树的数据结构; (2)实现二叉排序树的插入算法与查找算法,并建立二叉排序树; (3)进行数据查找和建树过程的比较。
采用C++语言编写的程序,二叉排序树的查找方法简单。
用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
一、问题描述 根据给定的关键字序列,实现二叉排序树的基本操作。 输入格式:8, 10, 5, 6, 3, 13 二、实验目的 ...1、构造二叉排序树的存储结构。 2、实现创建、查找、插入、删除、平均查找长度等操作。
从键盘读入一组数据,建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。 【基本要求】 建立二叉排序树并对其进行查找,包括成功和不成功两种情况,并给出查找长度 【选作内容】 实现二叉排序树的插入、...
老师给的资源,对于数据结构入门的学生很有帮助的。
1,动态创建二叉排序树 2,输出二叉排序树 3.判断是否为二叉排序树 4.输出查找某元素的路径 5.删除特定关键字结点
二叉排序树的查找插入删除打印演示,可多个同时查找插入删除,树的横向打印有图片,输入以0结束
最近在研究数据结构这本书,自己动手实现的一个二叉查找排序树的类BinSortTree,实现数据的插入,查找,删除,层序遍历,中序遍历等操作,熟悉数据结构的朋友都知道,根据二叉排序树的定义,中序遍历后得到的序列...
数据结构,二叉排序树的C++源代码。可以实现插入,删除,查找功能。
实验内容:建立有n个元素的二叉排序树,并在其上进行查找。 实验说明:(1)建立n个元素的二叉树,以链式结构存储,数据元素为整型。(2)在该二叉树上查找某数据,若查找成功则输出成功信息,若查找失败,则插入该数据...
/*用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
查找二叉排序树的双亲节点,并输出路径project
数据结构课程设计报告 本人做的 可以套用下哦 呵呵
运行环境:Dev-c++ 使用范围:大学c语言数据结构课程设计 功能: 【基本要求】 1.用二叉链表作存储... (4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”;
用函数实现如下二叉排序树算法:(1) 插入新结点(2) 前序、中序、后序遍历二叉树(3) 中序遍历的非递归算法(4) 层次遍历二叉树(5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input 第一行:准备...
从键盘读入一组数据,建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作 。 1.1.2数据结构课程设计基本要求。 建立二叉排序树并对其进行查找,包括成功和不成功两种情况,并给出查找长度。 1.2.1数据结构...