二叉树分类树

如何显示二叉排序树？

如何显示二叉排序树？

在计算机科学中，二叉树是一种树形结构，每个节点最多有两种结构。子树通常被称为左子树和右子树。二叉树常用于实现二叉查找树和二进制堆。二叉排序树也叫二叉查找树，也叫二叉查找树。二叉排序树或空树，或具有以下性质的二叉树:(充要条件)(1)如果左子树不是空，则左子树中所有节点的值小于其根节点的值；(2)如果右子树不是空，则右子树中所有节点的值都大于或等于其根节点的值；(3)左右树也是二叉排序树；(4)没有相等节点的键值。C(i)每个节点的层数。最坏的情况下，当插入的关键字按顺序排列时，二叉排序树就会变成一棵树，树的深度就是它的平均搜索长度(n ^ 1)/2(和顺序搜索一样)。在最好的情况下，二叉排序树与半搜索的判断树具有相同的形状，其平均搜索长度与log 2 (n)成正比。

二叉排序树的定义？

二叉排序树也是二叉树。所谓二叉树，就是任何一个节点最多只允许有两个子节点。

存储结构一般采用二叉排序树。中间遍历二叉排序树可以得到根据关键字排序的序列。通过构造二叉排序树，可以将一个无序序列转变为有序序列。建树的过程就是对无序序列进行排序的过程。每次插入一个新节点，它都是二叉排序树上的一个新叶节点。插入时不需要移动其他节点，只需要将节点的指针由空改为non 空。搜索、插入、删除的时间复杂度等于树的高度，期望值O(logn)，最差O(n)(序列是有序的，树退化成线性表，比如直角树)。

二叉排序树的属性:

1.如果左子树不是空，那么左子树中所有节点的值都小于其根节点的值；

2.如果其右子树不是空，则右子树中所有节点的值都大于其根节点的值。

3.换句话说，任何节点的键值都必须大于左子树中每个节点的键值，小于右子树中每个节点的键值。