《数据结构》第五章-树与二叉树思维导图的视觉表现

这份课件深入浅出地讲解了二叉树的核心概念，涵盖了二叉树的定义、类型、性质以及常见的遍历方法。通过丰富的示例和图解，您将轻松理解二叉树的构建、操作和应用。

二叉树的前序、中序和后序遍历方法是数据结构中重要的概念，它们涵盖了结点和叶子节点的计算。

这份笔记源于青岛大学王卓老师的数据结构课程，内容围绕树和二叉树展开，记录了课堂讲解的重点内容。

二叉树和二叉查找树是计算机科学中重要的数据结构概念，在数据存储、检索和排序等领域有广泛应用。二叉树每个节点最多有两个子节点，分别为左子节点和右子节点。二叉查找树（BST）是二叉树的特殊形式，其特点包括：1. 每个节点的左子树只包含比节点小的元素；2. 每个节点的右子树只包含比节点大的元素；3. 左右子树也必须分别是二叉查找树。BST的定义通过Node对象实现，包括数据元素、左右子节点引用和显示节点数据的方法。创建BST类表示根节点为null的空树，并实现节点插入操作，根据节点元素大小更新父节点的子节点引用，以实现数据插入。

完全二叉树的主要特点是除了最后一层外，每一层都被完全填满，最后一层的节点从左到右依次填充。与非完全二叉树相比，完全二叉树在节点分布上具有明显的规律性。

二叉搜索树的定义如下：（1）左子树不为空时，所有左子树节点的值都小于根节点的值。（2）右子树不为空时，所有右子树节点的值都大于根节点的值。（3）其左右子树也分别为二叉搜索树。关于二叉搜索树的函数：传入参数i表示在数组和树中的位置；树的当前节点为i，左分支为2i+1，右分支为2i+2；若右分支序列小于T的长度且节点值不等于-1时开始判断：如果右分支小于当前节点，左分支大于当前节点则不是二叉搜索树；在递归判断左子树和右子树时，若有任一不符合条件则不是二叉搜索树。

N个节点的完全二叉树，编号顺序从上到下、从左到右。 根节点编号为1。 若节点编号大于1，其双亲节点编号为[编号/2]。 若节点编号2I大于N，则节点I没有左孩子，否则其左孩子编号为2I。 若节点编号2I+1大于N，则节点I没有右孩子，否则其右孩子编号为2I+1。

使用二叉树（BST）作为数据结构来存储数据 提供了一种插入节点到二叉树的方法 讨论了如何使用二叉树进行查找操作

数据结构第五章概念图