二叉查找树(C)

背景概述

在近期的学习计划中，我将着手研究二叉平衡树的相关内容。然而，在深入掌握这一数据结构之前，必须先理解二叉搜索树的基本原理，因为二叉平衡树正是在二叉搜索树的基础上，通过优化其特性而发展而来的。

二叉查找树基本概念

二叉查找树具体指什么？（又称为二叉搜索树）其名称本身即表达了含义，首先它是一种二叉树结构：即一种树形数据结构，每个节点最多只能拥有两个子节点。

1.1 满二叉树

上图展示的是一棵典型的二叉树结构，同时它也符合满二叉树的定义：树中所有节点均拥有两个子节点，分别位于左侧与右侧。

此外，还存在一种称为完全二叉树的结构：对于一棵深度为k且包含n个节点的 二叉树 ，若按照从上至下、从左到右的顺序对节点进行编号，当编号为i（1≤i≤n）的节点在该树中的位置与满二叉树中对应编号i的节点位置一致时，则这棵树被定义为 完全二叉树 。

1.2 完全二叉树