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

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

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

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

 

四、关于查找的说明

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