1. 树的基本概念树是一种重要的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。结点（Node）: 树中的基本单元，包含数据元素以及指向其子树的分支。根结点（Root Node）: 没有父结点的结点，一棵树最多只有一个根结点。子结点（Child Node）: …
平衡二叉树
现在通过实例来分析平衡二叉树的实现过程，以便更好地理解。选取一组数据分别为2，1，0，3，4，5，6，9，8，7的10个结点来构造平衡二叉树。（1）首先数据为2的结点作为根结点插入，接着插入1，仍是平衡的，再插入0时，2的平衡因子变为2，此时出现了不平衡，因此需要进行调整，最低不平衡结点为2，属于LL型，根据上述网址的内容，则调整过程如图1所示。图 1（2） …
前言在讲平衡二叉树（AVL）之前，需要先理清二叉搜索树BST（Binary Search Tree）的基本概念。二叉搜索树，重点记两条：二叉。每个结点的度≤2，这也是“二叉”的由来。左＜中＜右。左中右三个结点满足：左＜中＜右。同理可推断：左子树任意结点<中<右子树任意结点。AVL对于二叉搜索树BST，其平均效率为O(log n)，最坏情况为O(n …
- 1