树结构的常用表示方法
第一个儿子/下一兄弟的表示方法
struct TreeNode
{
Object element;
Treenode *firstchild
Treenode *nextSibling
}
树结构的基本操作
树结构的遍历
前序遍历
对节点的处理工作在其子节点被处理前执行
后续遍历
对节点的处理工作在其子节点被处理后执行
中序遍历
对节点的处理工作在其左节点之后, 右节点之前
数据结构---树(Tree)
1 - AVL树(Tree)
描述
AVL(Adelson-Velskii and Landis) 是带有 平衡条件(balance condition) 的 二叉查找树(BST),通过自动调整树的结构，AVL树可以确保查找、插入和删除操作的时间复杂度为 \(O(\log{n})\)。
用来衡量其"平衡程度"的标准是树中某个节点的左右子树的高度差
树的 高度 是指树中 层数 的总数。
平衡条件
AVL树中的每个节点的左右子树高度差（称为平衡因子）最多为1，(这样的约束确保了树的高度在\(O(\log{n})\)范围内)。即左右子树的高度差为 -1、0 或 1。否则，树需要通过旋转操作进行重新平衡。
树的旋转（为了保证平衡性）
- 左左(外-单)
- 左右(内-双)
- 右左(内-双)
- 右右(外-单)
单旋转
双旋转
2 - 查找树ADT---二叉查找树(Binary Search Tree)
描述
二叉查找树， 是二叉树在查找中的应用。 使二叉树变为二叉查找树的方法， 是增加一个性质： 对于树中的每个结点Node， 它的左子树中的所有项的值， 都小于X中的项， 而它的右子树中所有的项目的值大于 X 中的项。 其中(小于&大于)仅表达某种的排列规则在结点之间递归传递
二叉查找树的框架
template<typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree &node);
~BinarySearchTree();
const Comparable &findMin() const;
const Comparable &findMax() const;
bool contains(const Comparable &node) const;
bool isEmpty() const;
void printTree() const;
void makeEmpty();
void insert(const Comparable &node);
void remove(const Comparable &node);
const BinarySearchTree & operator=(const BinarySearchTree &rhs);
private:
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const Comparable &theelement, BinaryNode *lt, BinaryNode *rt): element(theelement), left(lt), right(rt)
}
BinaryNode *root;
// =========== recuris sub progress
void insert(const Comparable &node, BinaryNode *&t) const;
void remove(const Comparable &node, BinaryNode *&t) const;
BinaryNode *findMin(BinaryNode *t) const;
BinaryNode *findMax(BinaryNode *t) const;
bool contains(const Comparable &x, BinaryNode *&t) const;
void makeEmpty(BinaryNode *&t);
void printTree(BinaryNode *t) const;
BinaryNode *clone(BinaryNode *t) const;
}
随机生成二叉查找树
3 - 二叉树(Binary Tree)
描述
一颗每个结点的子节点不多于两个
实现
struct BNode
{
Object element; // The data in the node
BNode *left; // Left child
BNode *right; // Right child
}
应用
表达式树
表达树中的树叶是 操作数(operand)
其他的节点是 操作符(operator)
中缀表达式(infix expresion) / 中缀遍历(inorder traversal)
写一种算法将后缀表达式 转变为 表达式树
将 中缀表达式 转变为 后缀表达式 的算法
从两种常用类型的输入生成表达式树
4 - 平衡二叉查找树(Balanced Binary Search Tree)
描述
平衡二叉树（Balanced Binary Tree）是一种二叉树结构，其中任意节点的左右子树的高度差（通常称为平衡因子）不超过1。这种特性确保了树的高度接近于最小，使得在最坏情况下的查找、插入和删除操作的时间复杂度为O(log n)，其中n是树中节点的数量。
常见的平衡二叉树类型
AVL 树
- 在AVL树中，任意节点的左右子树高度差不超过1。
- 在插入或删除节点后，AVL树会通过旋转操作来重新平衡树结构。
- AVL树以其高度平衡的性质著称，查找效率非常高。
红黑树
- 红黑树是一种相对松散的平衡二叉树，它放宽了AVL树的平衡要求。
- 在红黑树中，树的每个节点都有一个颜色属性（红色或黑色），并且通过一系列的规则确保树大致平衡。
- 红黑树的查找、插入和删除操作时间复杂度同样为O(log n)，但是它在频繁插入和删除的情况下表现得比AVL树更好。