二叉查找树的构造(数据结构二叉查找树的应用educode)

导语：二叉查找树，数据结构中的重要概念，以及各种遍历方式的学习

二叉树

首先，我们来了解一下什么是二叉树(Binary Tree)，在数据结构中，二叉树指的是每个节点最多有两个子树的树结构

图一

如图一所示，这个就是二叉树，A、B、C节点最多有两个子树

二叉查找树

二叉查找树(Binary Search Tree)，指的是一颗空树，或者具有一些性质的二叉树

1、若左子树不为空的话，左边子树的值都要小于根

2、若右子树不为空的话，右边子树的值都要大于根

3、左右子树肯定都要是二叉查找树

俗称左小右大

那么我们给出一道例题来看看

把数据序列{73,23,44,99,21,78}依次插入到二叉查找树中，

请画出最终的二叉查找树

注意，题目中说的是依次

所以应该以73作为节点

如图所示，这就是这个数据序列最终的二叉查找树，满足了左小右大的要求

图二

先序遍历、中序遍历、后序遍历

先序遍历，简便记法，根左右

得到的结果就是73，23，21，44，99，78

中序遍历，简便记法，左根右

得到的结果就是21，23，44，73，78，99

后序遍历，简便记法，左右根

得到的结果就是21，44，23，78，99，73

本文内容由小德整理编辑！