数据结构——树

大家好，欢迎来到IT知识分享网。

数据结构教程：树（Tree）

一、定义与概念

树是一种非线性数据结构，由n(n>=1)个有限节点组成，且具有以下特点：

1. 有一个特定的称为根节点的特殊节点。

2. 每个节点可以有零个或多个子节点。

3. 子节点之间没有顺序关系，但它们都通过链接指向其父节点。

4. 树中的每一个节点都可以被唯一标识。

二、树的基本术语和分类

1. 节点（Node）：树的基本单元，包含一个值和可能的指向其子节点的引用。

2. 根节点（Root Node）：树的顶端节点，没有父节点。

3. 子节点（Child Node）：任何节点的直接下级节点。

4. 父节点（Parent Node）：任意子节点的直接上级节点。

5. 兄弟节点（Sibling Nodes）：具有相同父节点的节点互为兄弟节点。

6. 叶子节点（Leaf Node）：没有子节点的节点。

7. 度（Degree）：一个节点的子节点数量。

8. 高度（Height）：从根节点到最远叶子节点的最长路径上的边数。

9. 深度（Depth）：一个节点到根节点的路径长度。

常见的树类型包括：

• 二叉树（Binary Tree）：每个节点最多有两个子节点，分别称为左子节点和右子节点。

• 满二叉树（Full Binary Tree）：所有层都被完全填满，除了最后一层外，每一层的节点数都是最大可能的，并且最后一层的所有节点都靠左排列。

• 完全二叉树（Complete Binary Tree）：除了最后一层之外，其他各层都被完全填满，并且最后一层的所有节点都尽可能地靠左排列。

• 平衡二叉树（Balanced Binary Tree）：左右两个子树的高度差不超过1，例如AVL树、红黑树等。

• 多叉树（Multiary Tree或k-ary Tree）：每个节点最多有k个子节点的树。

• 二叉搜索树（Binary Search Tree, BST）：对于任意一个节点，其左子树中所有节点的值小于该节点的值，而右子树中所有节点的值大于或等于该节点的值。

三、C++实现示例 – 二叉树节点类

class TreeNode { public: int val; TreeNode* left; TreeNode* right; // 构造函数 TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

四、基本操作与复杂度分析

1. 插入操作：在二叉搜索树中插入新节点的时间复杂度为O(log n)，但在最坏情况下（如树退化成链表），时间复杂度为O(n)。

2. 删除操作：同样在理想条件下是O(log n)，最坏情况为O(n)。

3. 查找操作：查找给定值在二叉搜索树中的节点，最佳情况下的时间复杂度为O(log n)，最坏情况下为O(n)。

五、遍历方式

二叉树主要有三种遍历方式：

• 前序遍历（Preorder Traversal）：先访问根节点，然后递归遍历左子树，最后遍历右子树。

• 中序遍历（Inorder Traversal）：先递归遍历左子树，然后访问根节点，最后遍历右子树。对二叉搜索树来说，中序遍历的结果是一个递增序列。

• 后序遍历（Postorder Traversal）：先递归遍历左子树，再遍历右子树，最后访问根节点。

六、示例代码 – 前序遍历二叉树

void preorderTraversal(TreeNode* node) { if (node != nullptr) { std::cout << node->val << " "; preorderTraversal(node->left); preorderTraversal(node->right); } }

总结：树作为一种基础的数据结构，在计算机科学中有广泛的应用，如文件系统、数据库索引、表达式解析、游戏AI等。理解并掌握树的各种类型及其遍历方法，有助于设计和优化算法性能。