package tree.binarytree; import java.util.Random; /** * Created by Lanxiaowei * Craated on 2016/12/12 17:14 * 判断给定的一个数字x是否在指定的一个无序的数字序列中存在 * 采用二叉排序树方式实现 */ public class TestBinarySortTree { public static void main(String[] args) { //测试100次 test(100); } /** * 测试方法 * @param times 测试的总次数 */ public static void test(int times) { if(times <= 0) { throw new IllegalArgumentException("The number [times] MUST be greater than zero."); } while(times-- > 0) { System.out.println("/**********************华丽的分割线 begin************************/"); int min = 1; int max = 100; //先随机生成一个随机数作为二叉树的父节点 int parentVal = random(min,max); //打印生成的parent节点数值 System.out.println("Parent:" + parentVal); //创建二叉树的父节点 BinarySortTreeNode parentNode = new BinarySortTreeNode(parentVal); //假设我们的无序数字序列的长度n=10,这里我们随机生成无序数字序列里的每个数字,然后插入二叉树结构中 int n = 10; //用于存储每个子节点的数值 int num = 0; //这里之所以是n - 2,是因为我们已经生成了父节点,剩下我们只需要生成n - 1个子节点, //而i是从零开始的,因此这里是n - 2 for(int i=0; i < n - 2; i++) { //随机生成每个子节点的数值 num = random(min,max); System.out.println("Child:" + num); //创建每个子节点 BinarySortTreeNode child = new BinarySortTreeNode(num); //往二叉排序树里插入子节点 parentNode.insert(parentNode,child); } //随机生成我们待查找的数字x int x = random(min,max); //查找数字x是否在二叉树中存在 boolean exists = parentNode.search(parentNode,x); System.out.println("Number x[" + x + "] exists in binary sorted tree?:" + exists); System.out.println("/**********************华丽的分割线 end**************************/\n"); } } /** * 二叉排序树的每个节点 */ public static class BinarySortTreeNode { //左子节点 private BinarySortTreeNode left; //右子节点 private BinarySortTreeNode right; /**节点上的值*/ private int val; public BinarySortTreeNode() {} public BinarySortTreeNode(int val) { this.val = val; } /** * 往指定的父节点上插入一个子节点 * @param parentNode 父节点 * @param newNode 待插入的节点 * @return */ public boolean insert(BinarySortTreeNode parentNode, BinarySortTreeNode newNode) { if(null == parentNode) { throw new IllegalArgumentException("Parent Node MUST be specified."); } //若待插入的节点数值大于等于父节点,则待插入的newNode此时应该在右边 if(parentNode.val <= newNode.val) { //如果父节点此刻的右树为空,那么就将待插入的newNode作为父节点右树的父节点 if(parentNode.right == null) { parentNode.right = newNode; return true; } else { //如果父节点的右树不为空,那么就插入到右树的父节点下 return insert(parentNode.right, newNode); } } //若待插入的节点数值大于等于父节点,则待插入的newNode此时应该在左边 if(parentNode.val > newNode.val) { //如果父节点此刻的左树为空,那么就将待插入的newNode作为父节点左树的父节点 if(parentNode.left == null) { parentNode.left = newNode; return true; } else { //如果父节点的左树不为空,那么就插入到左树的父节点下 return insert(parentNode.left, newNode); } } return false; } /** * 在指定的父节点为parentNode的二叉树下查找是否存在一个数字x * @param parentNode 二叉树的父节点 * @param x 待查找的数字x * @return */ public boolean search(BinarySortTreeNode parentNode, int x) { //如果二叉树为null,直接return false if(null == parentNode) { return false; } //此时说明找到数字x了,直接return true if(parentNode.val == x) { return true; } //此时应该在右子树中查找 if(parentNode.val < x) { return search(parentNode.right,x); } //此时应该在左子树中查找 if(parentNode.val > x) { return search(parentNode.left,x); } return false; } } /** * 生成[min,max)区间内的随机数 * @param min * @param max * @return */ public static int random(int min,int max) { Random random = new Random(); return random.nextInt(max)%(max - min + 1) + min; } }
相关推荐
判别给定二叉树是否为二叉排序树
用二叉链表作存储结构,编写程序实现二叉排序树上的基本操作:以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T......
用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
二叉排序树,其中有一个关键字,可以通过关键字的大小排序~~
根据给定的关键字序列,实现二叉排序树的基本操作。 输入格式:8, 10, 5, 6, 3, 13 二、实验目的 掌握二叉排序树的存储方法,实现二叉排序树的创建、查找、插入、删除、平均查找长度等基本操作。 三、实验内容及要求...
/*用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
用C语言写的一个二叉排序树,不过由于是课程设计上的完成的,所以,可能会有点凌乱。
根据给定的序列,建立一个二叉排序树,然后给定一个值,判断该值是否在这棵树中,若不在,请给出相关信息;若存在,请将与给定值相同的结点从该二叉排序树中删除。
一:需求分析 1. 基本要求 ... 在二叉排序树中插入一个新结点,中序遍历所建二叉排序树,将得到一个按关键字有序的元素序列 二叉排序树的查找,可多次查找,并输出查找的结果 4.最后对输出结构进行分析
用函数实现如下二叉排序树算法:(1) 插入新结点(2) 前序、中序、后序遍历二叉树(3) 中序遍历的非递归算法(4) 层次遍历二叉树(5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input 第一行:准备...
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各...
为了向二叉排序树中插入一个新元素,必须先检查这个元素在二叉排序树中是否已经存在。因此,在插入之前,首先在二叉排序树中检查待插入的数据元素,如果查找成功,说明树中已经存在这个数据元素,则不再插入:如果...
该课题是用来描述二叉排序树的,给定一列整型的数据(无序),按照二叉排序树的思想将该列数据排成一个有序的序列(通过中序遍历该二叉树可以得到一个非递减有序序列)。通过该二叉排序树可以快速的查找所需的数据...
1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性,以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理...1、以二叉链表作存储结构,试编写前序、中序、后序遍历二叉树的算法。
数据结构实验课,关于判断二叉树是不是二叉排序树》》》》》
1.学生基本数据的有序表输入 2.学生基本数据的有序表输出 3.学生基本数据的有序表的二分法查找 4.学生基本数据的有序二叉树建立 5.学生基本数据的有序二叉树前序遍历输出 6.学生基本数据的有序二叉树... 7....
二叉排序树查找算法,用c++编写,简单易通,查找效率高。
二叉排序树的判定,广义表表示法创建二叉树,C语言指针的相关应用。