二叉查找树是指在链表的基础上往数组中追加元素时,考虑到数据的大小关系,将其分成左右两个方向的表现形式。例如,假设我们事先把50这个值保存到了数组中。那么,如果接下来的值比先前保存的数值大的话,就要将其放到右边,反之如果小的话就放在左边。但实际的内存并不会分成两个方向,这是在程序逻辑上实现的(图4-15)。
树(tree)构造指的是数据像树一样分叉连接的方式。二叉查找树也是树构造的一种。
为了实现二叉查找树,怎么处理比较好呢?其实数组的每个元素中只要有数据的值和两个索引信息就可以了。图4-16向我们展示了如何用数组来实现图4-14中的二叉查找树。二叉查找树是由链表构造发展而来的表现形式,因此在追加或删除元素方面也同样是有效的。
使用二叉查找树的便利之处在于可以使数据的搜索等更有效率。在使用一般的数组时,必须从数组的开头按照索引顺序来查找目标数据。而使用二叉查找树时,当目标数据比现在读出来的数据小时就可以转到左侧,反之目标数据较大时即可转到链表的右侧,这样就加快了找到目标数据的速度。
标签:树使,二叉,链表,查找,数组,数据,树是 From: https://www.cnblogs.com/2674308160-lucky/p/17052369.html