二叉排序树

欢迎查看我的其他文章

二叉树基本概念

二叉树：是n(n>=0)个结点的有限集。该集合或为空或由一个根节点和两个互不相交的的节点

满二叉树：在一棵二叉树中，果所有分支结点都存在左子树和右子树

完全二叉树：n个结点的二叉树按层次序编号，编号为i（1<=i<=n）的结点与同样深度的满二叉树编号为i的结点在二叉树中的位置完全相同

完全二叉树官方定义：二叉树的深度为h,那么除了h层以外，其他的层的节结点数都达到最大值，并h层的所有结点都连续集中在最左边

二叉排序树的基本概念和生成

二叉排序树：一棵空树或者具有如下性质的二叉树，又称二叉查找树、二叉搜索树

1.若左子树不为空，那么左子树上面的所有结点的关键字都比根结点的关键字小

2.若右子树不为空，那么右子树上面的所有结点的关键字都比根结点的关键字大

1.左右子树都为二叉树

image

我们现在按照二叉排序树的规则，生成一个二叉排序树来存储一组数据
1.首先判断有无根结点，没有就创建根结点
2.往下遍历，小的放左边，大的放右边。
下面开始手撕代码

1.创建二叉树树结点! 结点结构图

static class TreeNode{
        TreeNode parent; //父结点
        TreeNode leftChild; // 左子结点
        TreeNode rightChild; //右子结点
        int data;//存储数据
        public TreeNode(int data){
            this.data=data;
        }
    }

相信这里应该很好理解，对于一个节点来说，他需要存储本身的数据外，还要存储父结点、左子树和右子树的地址。
2.添加数据
这边既然生成二叉树，肯定事将一组数据一个一个插入，依次生成一个一个结点来储存

  // 循环添加
        for (int i : datas) {
            put(i);
        }
 /**
   * 添加一个数据
   * */
    public static TreeNode put(int data) {
        // 如果根结点为空
        if (root == null) {
            TreeNode node = new TreeNode(data);
            root = node;
            return node;
        }
        TreeNode parent = null;
        TreeNode node = root;
        // 从根结点开始往下遍历 ，比当前结点小 查找左边  ，比当前结点大 查找右边  ，直到找出的空结点
        for(; node != null;) {
            parent = node;
            if (data < node.data) {
                node = node.leftChild;
            } else if(data > node.data) {
                node = node.rightChild;
            } else {
                return node;
            }
        }
        //创建存储当前数据的结点
        TreeNode newNode = new TreeNode(data);
        // 判断是加载左边还是右边
        if (data < parent.data) {
            parent.leftChild = newNode;
        } else {
            parent.rightChild = newNode;
        }
        // 赋值新结点的父结点
        newNode.parent = parent;
        return newNode;
    }

我们来分析一下上面的流程
1.这个树是否是空的 是 创建结点存储数据 返回结点
2.根据上述生成规则轮询结点直到null，此时得到了父结点
3.再判断添加左右子树
上面就是一个结点的添加过程。
至此 我们就能对一组数据生成一个二叉排序树。

下面我们接着说一下对二叉排序树的遍历吧。现在我们有个二叉排序树，我们改怎么样遍历出所有的节点数据呢？

我们对一段数据进行测试
private static int[] datas ={10,2,6,15,23,5,9,11}; //待存储的数据

image.png 1.先序遍历 ---- 根结点 > 左子树 > 右子树 image.png

 /**
     * 前序遍历
     * */
    public void preOrderTraverse(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println("前序:" + root.data); 
        preOrderTraverse(root.leftChild);  
        preOrderTraverse(root.rightChild); 
    }
结果-->
前序:10
前序:2
前序:6
前序:5
前序:9
前序:15
前序:11
前序:23

2.中序遍历 ： 左子树 > 根结点 > 右子树 image.png

  /**
    * 中序
    * */
    public static void midOrderTraverse(TreeNode root){
        if(root==null){
            return;
        }
        midOrderTraverse(root.leftChild);
        System.out.println("中序" + root.data);
        midOrderTraverse(root.rightChild);
    }
结果-->
中序2
中序5
中序6
中序9
中序10
中序11
中序15
中序23

3.后序遍历 ： 左子树 > 右子树 > 根结点 image.png

  /**
     * 后序
     * */
    public static void postOrderTraverse(TreeNode root){
        if(root==null){
            return;
        }
        postOrderTraverse(root.leftChild);
        postOrderTraverse(root.rightChild);
        System.out.println("post :" + root.data);
    }
结果-->
post:5
post:9
post:6
post:2
post:11
post:23
post:15
post:10

在此运用了递归算法实现了下二叉排序树的三种遍历
在理解遍历的时候 ，我们可以根据图来理解，下面画一下具体理解步骤

举例 后序遍历 image.png