二叉排序树的建立 二叉排序树的作用是什么

一、二叉搜索树怎么构建

动态创建二叉树就是将数组变成一个二叉树，往往动态创建二叉树都是创建二叉搜索树。创建二叉搜索树的过程就是不断的向二叉树中插入节点的过程。在插入节点过程中保证二叉搜索树的特性：任意一节点的左子树的所有节点都小于该节点，并且其右子树的所有节点都大于该节点。

例如用数组[10,6,8,15,13,17,11,14]来创建二叉搜索树。

二、二叉排序树的定义

首先二叉排序树也是一棵二叉树，所谓二叉树，就是“任何节点最多只允许两个子节点”，这两个子节点称为左右子节点。

二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树可得到一个依据关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的时间复杂度等于树高，期望O(logn)，最坏O(n)（数列有序，树退化成线性表，如右斜树）。

二叉排序树性质：

1、就是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2、若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。

3、换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。

三、二叉排序树的asl公式

对于二叉排序树的ASL算法

二叉排序树的特点是左孩子小于根节点，右孩子大于根节点

之前寻找博客上计算ASL的算法时，看到用的是设置一个max值来判断是否换层，遍历二叉排序树，若是大于max则是属于同一层，赋值给max，直到找到小于max的节点就是下一层，但是对于如果一层中只有最后一个节点（即这一层最大的节点）有右孩子，max值就一直是增加的，则不会换层

解决方法

使用一个父节点数组和队列，有孩子节点则加入父节点队列，存储每一层的父节点数，一层结束后输出前面的父节点，只留下该层最后一父节点，则可以判断一层结束；

若节点队列为空且当前节点无孩子，则整个二叉排序树结束。