数据结构四 二叉搜索树 平衡二叉树

文章结构概述

• 1. 二叉排序树（BST）
  • • 1.1 二叉排序树的概念界定
    • 1.2 检索操作
    • 1.3 数据添加
    • 1.4 结构生成
    • 1.5 元素移除

  • 2. 平衡二叉树（AVL）

  • • 2.1 平衡二叉树的定义说明
    • 2.2 数据插入过程

1. 二叉排序树（BST）

1.1 二叉排序树的定义

• 二叉树左侧分支中所有节点的数值均低于其父节点的数值。
  • 二叉树右侧分支中所有节点的数值均高于其父节点的数值。
  • 当对二叉排序树实施中序遍历操作时，可得到一个按照升序排列的序列。

1.信息检索机制设计

（1）思想
二叉排序树的查找过程始于根节点，通过逐层向下进行比较来实现。

• 一旦当前节点的值与目标相等，则完成查找。
• 若根节点不为空，且目标值小于当前节点的值，则继续在左子树中进行搜索；若目标值大于当前节点的值，则转向右子树进行查找。
• 最终函数将返回对应的节点指针或NULL。

    /*二叉搜索树的查找（非递归版本）*/
    BSTNode* BST_Search(BSTNode* T, int key)
    {
    	while(T != NULL && T->val != key)