数据结构与算法—二叉排序树详解 _二叉排序树

前言

前面介绍学习的大多是线性表相关的内容，把指针搞懂后其实也没有什么难度。规则相对是简单的。

再数据结构中树、图才是数据结构标志性产物，(线性表大多都现成api可以使用),因为树的难度相比线性表大一些并且树的拓展性很强，你所知道的树、二叉树、二叉排序树，AVL树，线索二叉树、红黑树、B数、线段树等等高级数据结构。然而二叉排序树是所有的基础，所以彻底搞懂二叉排序树也是非常重要的。
树

文章插图

参考王道数据结构

二叉树也是树的一种，而二叉排序树又是二叉树的一种。

树是递归的，将树的任何一个节点以及节点下的节点都能组合成一个新的树。并且很多操作基于递归完成。
根节点：最上面的那个节点(root)，根节点没有前驱节点，只有子节点（0个或多个都可以）
层数：一般认为根节点是第1层(有的也说第0层) 。而树的高度就是层数最高(上图层数开始为1)节点的层数
节点关系: 父节点：就是链接该节点的上一层节点,孩子节点:和父节点对应，上下关系。而祖先节点是父节点的父节点(或者祖先）节点。兄弟节点：拥有同一个父节点的节点们！
度：节点的度就是节点拥有孩子节点的个数(是孩子不是子孙).而树的度(最大)节点的度。同时，如果度大于0就成为分支节点,度等于0就成为叶子节点（没有子孙）。

相关性质：

树的节点数=所有节点度数+1.
度为m的树第i层最多有mi-1个节点。(i>=1)
高度而h的m叉树最多（mh-1）/(m-1)个节点(等比数列求和)
n个节点的m叉树最小高度[logm(n(m-1)+1)]

二叉树二叉树是一树的一种，但应用比较多，所以需要深入学习。二叉树的每个节点最多只有两个节点。
二叉树与度为2的树的区别：

一：度为2的的树必须有三个节点以上，二叉树可以为空。
二：二叉树的度不一定为2：比如说斜树。
三：二叉树有左右节点区分，而度为2的树没有左右节点的区分。

几种特殊二叉树：

满二叉树。高度为n的满二叉树有2n-1个节点

文章插图

完全二叉树：上面一层全部满，最下一层从左到右顺序排列

文章插图

二叉排序树：树按照一定规则插入排序(本文详解) 。
平衡二叉树：树上任意节点左子树和右子树深度差距不超过1.

二叉树性质：
相比树，二叉树的性质就是树的性质更加具体化。

非空二叉树叶子节点数=度为2的节点树+1.本来一个节点如果度为1.那么一直延续就一个叶子，但如果出现一个度为2除了延续原来的一个节点，会多出一个节点需要维系。所以到最后会多出一个叶子。
非空第i层最多有2i-1个节点。
高为h的树最多有2h-1个节点(等比求和) 。
完全二叉树若从左往右，从上到下编号如图：

文章插图

二叉排序(搜索)树概念
前面铺垫那么多，咱们言归正传，详细实现一个二叉排序树。首先要了解二叉排序树的规则：

从任意节点开始，节点左侧节点值总比节点右侧值要小。
例如。一个二叉排序树依次插入15，6，23，7，4，71，5，50会形成下图顺序

文章插图

构造
首先二叉排序树是由若干节点构成。

对于node需要这些属性：left，right，和value 。其中left和right是左右指针，而value是储存的数据，这里用int 类型。

node类构造为：
class node {//结点 public int value; public node left; public node right; public node() { } public node(int value) {this.value=https://www.isolves.com/it/rj/czxt/linux/2019-08-19/value;this.left=null;this.right=null; } public node(int value,node l,node r) {this.value=value;this.left=l;this.right=r; }}既然节点构造好了，那么就需要节点等其他信息构造成树。有了链表构造经验，很容易得知一棵树最主要的还是root根节点。
所以树的构造为：
public class BinarySortTree { node root;//根 public BinarySortTree() {root=null;} public void makeEmpty()//变空 {root=null;} public boolean isEmpty()//查看是否为空 {return root==null;} //各种方法}