`
狂盗一枝梅
  • 浏览: 17702 次
  • 性别: Icon_minigender_1
  • 来自: 青岛
社区版块
存档分类
最新评论

【数据结构】【查找】二叉排序树

阅读更多

       使用二叉排序树查找效率也非常高,当然有更稳定的二叉平衡树,但是实现起来比较困难,所以这里只实现了二叉排序树;二叉排序树的特点如下:

  1. 左子树中的所有节点值都小于父节点值
  2. 右子树中的所有节点值都大于父节点值
  3. 所有节点不允许出现重复,否则会破坏二叉排序树的数据结构
  4. 二叉排序树的中序遍历的结果就是所有元素的排序结果
  5. 二叉排序树是二叉树

所以,使用二叉排序树不仅仅能够实现快速查找,而且也能够实现排序。

一、使用二叉排序树实现排序(非递归建树)

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

 这个结果实际上是对二叉排序树中序遍历的结果:

 

四、关于查找的说明

查找的原理和过程在以上的代码中已经有了充分的体现,不赘述。

 

  • 大小: 119.7 KB
分享到:
评论

相关推荐

    数据结构之二叉排序树的生成

    二叉排序树,又称二叉查找树或二叉搜索树,是一种特殊的数据结构,它具有以下特性:对于树中的任意节点,其左子树中的所有节点的值都小于该节点的值,而右子树中所有节点的值都大于该节点的值。这种特性使得在二叉...

    数据结构二叉排序树的源代码

    二叉排序树(Binary Search Tree, BST),又称为二叉查找树或有序二叉树,是一种特殊的二叉树数据结构。它具有以下性质: 1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 2. 若任意节点...

    数据结构之二叉排序树

    4. **查找操作**:查找二叉排序树中的特定值非常高效。从根节点开始,如果目标值小于当前节点,就移动到左子树;如果目标值大于当前节点,就移动到右子树。重复这个过程,直到找到目标值或者到达空节点。 5. **平衡...

    数据结构课程设计 二叉排序树与平衡二叉排序树

    在数据结构的学习中,二叉排序树(Binary Search Tree,BST)是一种常见的树形数据结构,它具有查找、插入和删除等操作的高效性。在这个课程设计中,我们将重点探讨如何利用二叉链表作为存储结构来实现二叉排序树,...

    数据结构实验之二叉排序树

    总结来说,"数据结构实验之二叉排序树"是一个实践性的学习项目,旨在通过动手实现二叉排序树的查找、插入和删除操作,来巩固和加深对数据结构理论知识的理解。在这个过程中,学生将学习到如何使用MFC来构建交互式...

    采用二叉链式结构做存储结构的二叉排序树建立和查找算法

    ### 查找二叉排序树 在二叉排序树中查找特定元素的算法相当简单: 1. 从根节点开始。 2. 如果根节点的值等于目标值,返回找到的节点。 3. 如果目标值小于根节点的值,递归地在左子树中查找。 4. 如果目标值大于根...

    数据结构课程设计二叉排序树的实现

    ### 数据结构课程设计二叉排序树的实现 #### 一、二叉排序树的基本概念 二叉排序树(Binary Search Tree, BST),又称二叉查找树或有序二叉树,是一种特殊的二叉树,其特点在于对于任意节点而言,其左子树中的所有...

    数据结构二叉排序树及其操作实验报告

    数据结构是计算机科学中的核心课程,它探讨了如何有效地存储和检索数据,以优化...这个实验报告提供了一个实用的框架,可以帮助其他学生理解和实现二叉排序树的各种操作,进一步巩固他们在数据结构课程中的学习成果。

    二叉排序树插入

    二叉排序树插入算法 二叉排序树插入是指在二叉排序树中插入新的数据元素的过程。...二叉排序树插入算法是二叉排序树操作的基础,它能够确保树的结构满足二叉排序树的性质,并且能够快速地查找和插入新的数据元素。

    数据结构课设—二叉排序树的判别

    《数据结构》课程设计说明书——二叉排序树的判别 1. 问题描述与分析 二叉排序树(Binary Sort Tree,BST)是一种特殊的二叉树,其中每个节点的值都大于其左子树中的任何节点的值,且小于其右子树中的任何节点的值...

    数据结构___二叉排序树

    一、实验目的 (1)理解动态查找表的动态生成过程; (2)任意给出一组数(不...(1)定义二叉排序树的数据结构; (2)实现二叉排序树的插入算法与查找算法,并建立二叉排序树; (3)进行数据查找和建树过程的比较。

    数据结构 二叉排序树 java图形界面实现

    总的来说,`BiSortTreeGui.java`文件通过Java Swing库实现了二叉排序树的数据结构,并结合GUI,使得用户可以直观地进行数据的插入、查找和删除操作,这在教学或实践数据结构时非常有帮助。这个项目展示了如何将抽象...

    《数据结构课程设计》二叉排序树基本操作实验程序

    在IT领域,数据结构是计算机科学的基础,而二叉排序树(Binary Sort Tree,BST)作为其中的一种重要数据结构,有着广泛的应用。本实验程序旨在深入理解和掌握二叉排序树的基本操作,包括动态创建、输出、判断、查找...

    数据结构课程设计二叉排序树

    二叉排序树(Binary Sort Tree,BST),也称为二叉搜索树,是一种特殊的二叉树数据结构,它的每个节点都包含一个键、一个关联值、一个指向左子节点的引用和一个指向右子节点的引用。在二叉排序树中,对于任何节点,...

    Java实现二叉排序树

    总之,二叉排序树是计算机科学中一种重要的数据结构,适用于需要高效查找、插入和删除操作的场景。在Java中实现二叉排序树时,我们需要考虑其基本操作的逻辑,并注意处理好边界条件和异常情况,以确保代码的正确性和...

    二叉排序树和折半查找

    二叉排序树(Binary Sort Tree,BST)是一种特殊的二叉树数据结构,它具有以下特性:每个节点的左子树只包含比当前节点小的元素,而右子树则只包含比当前节点大的元素。这种结构使得二叉排序树在插入、删除和查找...

    二叉排序树_17281183_刘梦婷_leavingtbk_二叉排序树_

    二叉排序树,又称二叉查找树或二叉搜索树,是一种特殊的二叉树数据结构,它具有以下特性:对于树中的每个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。这种性质使得...

    数据结构 二叉排序树的查找

    采用C++语言编写的程序,二叉排序树的查找方法简单。

    数据结构综合课设二叉排序树.docx

    总结,二叉排序树是一种重要的数据结构,适用于需要快速查找、插入和删除操作的场景。在实际应用中,保持树的平衡至关重要,以确保高效的性能。在编程实现时,需注意节点的插入、删除以及平衡调整策略。

Global site tag (gtag.js) - Google Analytics