利用二叉排序树进行排序

• • •  1、二叉排序树简要概述
    •  2、二叉排序树图示
    •  3、二叉排序树进行排序基本思路
    •  4、java代码实现

 1、二叉排序树简要概述

  二叉排序树：BST:(BinarySort(Search)Tree),对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
注意：如果有相同的值，可以将该节点放在左子节点或右子节点。

 2、二叉排序树图示

对于数据(7,3,10,12,5,1,9)，对应的二叉排序树为：

 3、二叉排序树进行排序基本思路

（1）先将要排序的数构建成一个二叉排序树。
（2）对该二叉排序树进行中序遍历即可得到按升序排列的数。

 4、java代码实现

public class test { 
    public static void main(String[] args) { 
        int arr[] = new int[]{ 7, 3, 10, 12, 5, 1, 9};
        BinarySortTree tree = new BinarySortTree();
        //循环的添加结点到二叉排序树
        for (int i = 0; i < arr.length; i++) { 
            tree.add(new Node(arr[i]));
        }
        //中序遍历二叉排序树
        System.out.println("中序遍历二叉排序树:");
        tree.infixOrder();
    }
}

//结点
class Node { 
    int value;
    Node left;
    Node right;

    public Node(int value) { 
        this.value = value;
    }

    public void add(Node node) { 
        if (node == null) { 
            return;
        }
        if (node.value < this.value) { 
            if (this.left == null) { 
                this.left = node;
            } else { 
                this.left.add(node);
            }
        } else { 
            if (this.right == null) { 
                this.right = node;
            } else { 
                this.right.add(node);
            }
        }
    }

    public void infixOrder() { 
        if (this.left != null) { 
            this.left.infixOrder();
        }
        System.out.print(this.toString());
        if (this.right != null) { 
            this.right.infixOrder();
        }
    }

    public String toString() { 
        return value + " ";
    }
}

//二叉排序树
class BinarySortTree { 
    private Node root;

    public void add(Node node) { 
        if (root == null) { 
            root = node;
        } else { 
            root.add(node);
        }
    }

    public void infixOrder() { 
        if (root != null) { 
            root.infixOrder();
        } else { 
            System.out.println("二叉排序树为空！");
        }
    }
}

结果如下：

楠哥——-一心想为IT行业添砖加瓦，却总是面向cv编程的程序员。

  谢谢阅读，无误点赞，有误还望评论区指正。