当前位置:   article > 正文

数据结构(四)——二叉搜索树和平衡二叉树_什么是二叉搜索树和二叉平衡树

什么是二叉搜索树和二叉平衡树

1. 二叉排序树(BST)

1.1 二叉排序树的定义

  • 左子树上所有节点的值小于根节点的值。
  • 右子树上所有节点的值大于根节点的值。
  • 对二叉排序树进行中序遍历,可以获得递增的有序序列。

1.2 查找

(1)思想
二叉排序树的查找是从根节点开始,自顶向下比较的过程。

  • 若相等,则查找成功。
  • 当根节点非空时,若小于根节点的值,则在左子树上查找。如大于根节点的值,则在右子树上查找。
  • 函数返回正确节点或NULL值。
/*二叉搜索树的查找(非递归版本)*/
BSTNode* BST_Search(BSTNode* T, int key)
{
   
	while(T != NULL && T->val != key){
   
		if(T->val >key)	T = T->rchild;
		else T = T->lchild;
	}
	return T;		// NULL 或 查找到的节点
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

(2)查找效率分析

  • 最好情况下:即AVL树,n个节点的二叉树最小高度为 [ log ⁡ 2 n ] + 1 [\log_2n]+1 [log<
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/914524
推荐阅读
相关标签
  

闽ICP备14008679号