上一篇讲到了二叉树的构建以及遍历方式有广度遍历以深度遍历，深度遍历又包括先序遍历、中序遍历以及后序遍历…
?上一篇链接
这篇主要来介绍什么是二叉排序树，以及如何构建二叉排序树
定义
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
特点
这棵二叉树的特点是：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树 （4）不存在键值相等的节点 （5）中序遍历的结果就是按照从小到大的规则排序后的结果
实现思想
1、判断是否为空树
2、如果是空树，则根节点等于插入新节点
3、如果不是，则将根节点设置为父节点，拿着新节点和父节点比较
如果小于父节点数据，则判断父节点是否为叶子结点（叶子结点是没有孩子的节点，即没有左、右节点）
如果是叶子结点，则将该节点插入到父节点的左边
如果不是叶子结点，则更新父节点为原来父节点的左子节点，后重复步骤3
如果大于父节点数据，则判断父节点是否为叶子结点
如果是叶子结点，则将该节点插入到父节点的右边
如果不是叶子结点，则更新父节点为原来父节点的右结点，重复步骤3
实现细节
/**
* 添加节点
* */
public boolean add(Integer data) {
if (root == null) {
this.root = new TreeNode(data);
size++;
return true;
} else {
TreeNode current = root;
TreeNode finalNode;
while (current != null) {
finalNode = current;
if (data < current.getData()) {
if (current.getLeft() == null){
finalNode.setLeft(new TreeNode(data));
size++;
return true;
}else {
current = current.getLeft();
}
}else {
if (current.getRight() == null){
finalNode.setRight(new TreeNode(data));
size++;
return true;
}else {
current = current.getRight();
}
}
}
}
return false;
}
老样子，这里放了全部代码，便于大家测试
整体代码实现
public class BinarySortedTree {
private static int size;
private static class TreeNode {
Integer data;
TreeNode left;
TreeNode right;
public TreeNode(Integer data) {
this.data = data;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
private TreeNode root;
public static int getSize() {
return size;
}
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
/**
* 添加节点
* */
public boolean add(Integer data) {
if (root == null) {
this.root = new TreeNode(data);
size++;
return true;
} else {
TreeNode current = root;
TreeNode finalNode;
while (current != null) {
finalNode = current;
if (data < current.getData()) {
if (current.getLeft() == null){
finalNode.setLeft(new TreeNode(data));
size++;
return true;
}else {
current = current.getLeft();
}
}else {
if (current.getRight() == null){
finalNode.setRight(new TreeNode(data));
size++;
return true;
}else {
current = current.getRight();
}
}
}
}
return false;
}
/**
* 中序遍历
* */
public void mid_print(TreeNode root){
if (root != null) {
//左
if(root.getLeft() != null){
mid_print(root.getLeft());
}
//根
System.out.print(root.getData()+"\t");
//右
if(root.getRight() != null){
mid_print(root.getRight());
}
}else {
System.out.println("当前为空树！");
return;
}
}
}
测试
public class Test {
public static void main(String[] args) {
BinarySortedTree tree = new BinarySortedTree();
tree.add(14);
tree.add(25);
tree.add(31);
tree.add(146);
tree.add(1);
tree.add(46);
tree.mid_print(tree.getRoot());
}
}
可以看出，尽管添加数据的时候无序，但是按照中序遍历的结果是有序的
可以看出，尽管添加数据的时候无序，但是按照中序遍历的结果是有序的
以上均为本人个人观点，借此分享，希望能和大家一起进步。如有不慎之处，劳请各位批评指正！鄙人将不胜感激并在第一时间进行修改！
