13714245368

网站建设 APP开发 小程序

新闻

二叉搜索树(BinarySearchTree,简写BST),又称为二叉排序树或二叉查找树。其定义为:对于树中的每个节点,其左子树的所有节点值都小于该节点的值,其右子树的所有节点值都大于该节点

您当前位置>主页 > 新闻 > 新闻中心 >

二叉搜索树的构建

发表时间:2020-03-23 13:37

文章来源:佚名

浏览次数:

二叉搜索树(Binary Search Tree,简写BST),又称为二叉排序树或二叉查找树。其定义为:对于树中的每个节点,其左子树的所有节点值都小于该节点的值,其右子树的所有节点值都大于该节点的值。二叉搜索树的任意一个子树也是二叉搜索树。

二叉树通过某种方式遍历后会得到一个序列结果,而某个节点的前驱节点就是遍历序列中该节点的前一个节点,后继节点就是遍历序列中该节点的后一个节点。例如中序前驱节点就是中序遍历二叉树后该节点的前一个节点。

由于中序遍历得到的序列是按从小到大排列的,中序前驱节点就是小于该节点的所有节点中最大的那个节点,中序后继节点就是大于该节点的所有节点中最小的节点。

动态创建二叉树就是将数组变成一个二叉树,往往动态创建二叉树都是创建二叉搜索树。创建二叉搜索树的过程就是不断的向二叉树中插入节点的过程。在插入节点过程中保证二叉搜索树的特性:任意一节点的左子树的所有节点都小于该节点,并且其右子树的所有节点都大于该节点。例如用数组[10, 6, 8, 15, 13, 17, 11, 14]来创建二叉搜索树。

3 处理元素8,与根节点比较:810,向左子树移动后比较:86,将8作为6的右子节点插入。如下图:

5 处理元素13,与根节点比较:1310,向右子树移动后比较:1315,将13作为15的左子节点插入。如下图所示:

6 处理元素17,与根节点比较:1710,向右子树移动后比较:1715,将17作为13的右子节点插入。如下图所示:

7 处理元素11,与根节点比较:1110,向右子树移动后比较:1115,向左子树移动后比较:1113,将11作为13的左子节点插入。如下图所示:

8 处理元素14,与根节点比较:1410,向右子树移动后比较:1415,向左子树移动后比较:1413,将14作为13的右子节点插入。如下图所示,就创建了一棵二叉搜索树:

1 由上述过程可以总结到,每个节点插入的过程中都会保证二叉树为二叉搜索树,二叉每一个节点都是作为二叉树的叶子节点插入的。

2 形成的二叉搜索树中序遍历顺序为:6,8,10,11,13,14,15,17,一个从小到的的有序序列。

2 如果i小于root位置的元素r且root没有左子节点,那么直接将其作为root的左子节点插入;

3如果i小于root位置的元素r且root有左子节点,将root换为root的左子节点从步骤2开始处理;

4如果i大于root位置的元素r且root没有右子节点,那么直接将其作为root的右子节点插入;

5如果i大于root位置的元素r且root有右子节点,那么将root换位root的右子节点从步骤2开始处理;

可见这套规则应用了一个递归思想去处理插入问题,递归界限是带插入节点总以叶节点的身份插入到已有的二叉搜索树中。程序实例如下:

相关案例查看更多