5.1 树和二叉树的定义

思维导图：

 

问题 为什么有树和二叉树？

"树" 和 "二叉树" 都是数据结构中常用的结构，它们分别有其独特的应用和优点。我们可以从它们的定义和特性中理解为什么它们都存在。

1. **树 (Tree)：**
   - **定义**: 树是一个由n个节点组成的集合，每个节点最多只有一个父节点，并且有一个特殊的节点，称为根。
   - **应用**: 
     - 文件系统，其中每个文件或文件夹可以包含多个文件或文件夹。
     - 组织结构图，其中一个经理可能有多个直接下属。
     - 抽象语法树，通常在编译器中使用，表示源代码的结构。
   - **优点**: 
     - 可以表示不同数量的子节点的数据结构。
     - 可以模拟现实生活中的多种结构。

2. **二叉树 (Binary Tree)：**
   - **定义**: 二叉树是一个特殊的树，其中每个节点最多只有两个子节点：左子节点和右子节点。
   - **应用**:
     - 二叉搜索树，用于搜索、插入、删除操作的快速执行。
     - 堆结构，如最大堆和最小堆，用于优先队列。
     - 平衡二叉树，如AVL或红黑树，确保树保持平衡，以获得更好的性能。
   - **优点**:
     - 由于其结构简单和有序，使得许多算法（如搜索、插入、删除等）在二叉树上更高效。
     - 二叉树有助于保持数据平衡，而不是高度偏斜，从而提高算法的效率。

总结:
- **为什么有树**? 树结构非常适合于表示现实世界中的许多层次或分级关系，其中一个元素可以有多个子元素。
- **为什么有二叉树**? 二叉树是一个特殊且简化的树形结构，特别适合于计算机科学中的某些应用，因为它简化了许多算法，并能够高效地实现它们。

两者之间的选择取决于所需的应用和操作的特性。

前言：

这段话主要讲述了树结构和二叉树在计算机科学中的重要性和应用。以下是该段内容的简要概述：

1. **定义和重要性**：
   - 树结构是非线性的数据结构。
   - 树通过分支关系定义了一个层次结构。
   - 树结构不仅在计算机科学中重要，在实际生活中（如社会的族谱和组织结构）也有其影子。

2. **在计算机领域的应用**：
   - 树，特别是二叉树，广泛应用于计算机领域。
   - 操作系统中用树来表示文件的目录结构。
   - 编译系统中，树用来表示源代码的语法结构。
   - 在数据库系统中，树是组织信息的主要方式之一。

3. **本章的内容重点**：
   - 主要讨论二叉树的存储结构及其操作。
   - 研究了树和森林与二叉树之间的转换关系。
   - 最后，介绍了树的实际应用。

总的来说，这段话强调了树结构，尤其是二叉树在计算机科学中的中心地位，并预告了本章将详细讨论的相关主题。

5.1.1 树的定义

**5.1 树和二叉树的定义**
- **5.1.1 树的定义**
  
  树是一个由节点组成的有限集合，它可以是空的（无节点）或包含一个称为“根”的特殊节点，与其他可以分割为多个互不相交子集的节点，其中每个子集本身也是一个树。这种定义是递归的，即树的定义是基于树本身的子集定义的。

  - 图5.1(a) 是一个只有一个节点的树，即只有一个根节点。
  - 图5.1(b) 是一个复杂点的树，它有13个节点，其中A是根。除根节点A外的节点可以分为3个子集: Ti, T₂, T3，这些都是根A的子树。

  有多种方式可以表示树，例如：
  - 图5.2(a) 是通过嵌套集合表示的树。
  - 图5.2(b) 是使用广义表来表示的树。
  - 图5.2(c) 是用凹入表示法表示的。

这些示例和描述突显了树结构在日常生活和计算机程序设计中的重要性。在实际中，任何分等级的分类方案都可以用树结构来表示。

**基本术语**：
- **节点(Node)**: 树中的每一个元素称为节点。
- **根节点(Root Node)**: 没有父节点的节点。
- **叶节点(Leaf Node)**: 没有子节点的节点。
- **子树(Subtree)**: 任一节点与其下级全部节点构成的树称为该节点的子树。
- **父节点(Parent Node)**: 除根节点外，每个节点有且只有一个与它直接上级关联的节点。
- **孩子节点(Child Node)**: 与节点直接下级关联的节点称为它的孩子节点。
- **兄弟节点(Sibling Nodes)**: 具有相同父节点的两个或多个节点。
- **节点的层次(Level)**: 根节点的层次定义为1，其余节点的层次是其父节点的层次加1。

这些术语帮助我们更好地理解和描述树的结构和性质。

5.1.2 树的基本术语 

你提供了关于“树”的一些基本术语和定义，下面是这些内容的简明总结：

**5.1.2 树的基本术语**

1. **节点(Node)**：树中的独立单元，包含数据元素和指向其子树的分支。
  
2. **节点的度(Degree of Node)**：一个节点有多少个子树。
  
3. **树的度(Degree of Tree)**：树中最大的节点度。
  
4. **叶子(Leaf or Terminal Node)**：没有子节点的节点。
  
5. **非终端节点(Non-terminal or Internal Node)**：有一个或多个子节点的节点。
  
6. **双亲和孩子(Parent and Child)**：一个节点的子节点称为其孩子，反之则为双亲。
  
7. **兄弟(Siblings)**：具有相同父节点的节点。
  
8. **祖先(Ancestor)**：从根到某一节点路径上的所有节点。
  
9. **子孙(Descendant)**：某一节点的所有下级节点。
  
10. **层次(Level)**：从根开始，每一个节点的层次是其父节点的层次加1。
  
11. **堂兄弟(Cousins)**：其双亲在同一层的节点。
  
12. **树的深度(Depth or Height of Tree)**：树中节点的最大层次。
  
13. **有序树和无序树(Ordered and Unordered Trees)**：树中节点的子树有固定次序的是有序树，没有固定次序的是无序树。
  
14. **森林(Forest)**：多棵互不相交的树的集合。

这些术语为我们提供了一个框架来描述和理解树的结构和属性。特别是在计算机科学和数据结构中，这些定义和概念对于算法的设计和理解非常重要。

 5.1.3 二叉树的定义

**5.1.3 二叉树的定义**

**二叉树 (Binary Tree)**：由n个节点组成的集合，可以为空（n=0）或由以下两部分组成：
1. **根节点**：二叉树中唯一的起始节点。
2. **左、右子树**：除根节点外的所有节点可以被分为两个互不相交的子集，分别为左子树和右子树，且它们自身也是二叉树。

**二叉树与常规树的主要区别**：

1. 在二叉树中，每个节点最多只有两个子节点。
2. 二叉树的左、右子树有明确的区分，并且次序不能被颠倒。

**二叉树的五种基本形态**（如图5.3所示）：
a. 空的二叉树。
b. 只有一个根节点的二叉树。
c. 只有左子树的二叉树（右子树为空）。
d. 左、右子树都不为空的二叉树。
e. 只有右子树的二叉树（左子树为空）。

注意：在二叉树中，所有关于“树”的术语（如在5.1.2节中描述的）都适用。

二叉树是数据结构中最常见和最基础的结构之一，它被广泛应用于算法设计，如排序算法、搜索算法等。它的递归性质为理解和应用带来了方便。

 例子：

好的，让我们来看三个二叉树的应用示例：

### 1. 二叉搜索树（BST）

**分析思考**:
- 二叉搜索树是一个二叉树，其中每个节点都有一个键和一个关联的值。对于树中的每个节点：
  * 所有左子树的键都小于节点的键。
  * 所有右子树的键都大于节点的键。
- 这些属性确保了在BST中查找键的操作非常快。

#### C 实现：

typedef struct Node {int key;struct Node* left;struct Node* right;
} Node;Node* newNode(int item) {Node* temp = (Node*)malloc(sizeof(Node));temp->key = item;temp->left = temp->right = NULL;return temp;
}Node* insert(Node* root, int key) {if (root == NULL) return newNode(key);if (key < root->key)root->left = insert(root->left, key);else if (key > root->key)root->right = insert(root->right, key);return root;
}

#### C++ 实现：

struct Node {int key;Node* left;Node* right;Node(int x) : key(x), left(nullptr), right(nullptr) {}
};Node* insert(Node* root, int key) {if (!root) return new Node(key);if (key < root->key)root->left = insert(root->left, key);else if (key > root->key)root->right = insert(root->right, key);return root;
}

#### Java 实现：

、

public class Node {int key;Node left, right;public Node(int item) {key = item;left = right = null;}
}public Node insert(Node root, int key) {if (root == null) {root = new Node(key);return root;}if (key < root.key)root.left = insert(root.left, key);else if (key > root.key)root.right = insert(root.right, key);return root;
}

### 2. 堆（特别是二叉堆）

**分析思考**:
- 二叉堆是一种特殊的完全二叉树，可以作为优先队列的有效数据结构。
- 最大堆：父节点的值总是大于或等于其子节点的值。
- 最小堆：父节点的值总是小于或等于其子节点的值。
- 这里为了简洁，我们只展示插入操作的C++版本实现。

#### C++ 实现：

#include <vector>class MaxHeap {
private:std::vector<int> heap;int parent(int i) { return (i - 1) / 2; }int left(int i) { return 2 * i + 1; }int right(int i) { return 2 * i + 2; }void siftUp(int i) {while (i > 0 && heap[parent(i)] < heap[i]) {std::swap(heap[parent(i)], heap[i]);i = parent(i);}}public:void insert(int key) {heap.push_back(key);int index = heap.size() - 1;siftUp(index);}
};

### 3. 平衡二叉搜索树（例如AVL树）

**分析思考**:
- 在普通的二叉搜索树中，当你连续插入已排序的数据时，树可能会变得非常偏斜，导致查找、插入和删除的时间复杂度降为O(n)。
- 平衡二叉搜索树（例如AVL树）保持树的平衡状态，即确保树的左子树和右子树的高度差不会超过1。这保证了在平衡二叉搜索树中的操作始终保持O(log n)的时间复杂度。

#### C 实现：

typedef struct Node {int key;int height;struct Node* left;struct Node* right;
} Node;int height(Node* N) {if (N == NULL)return 0;return N->height;
}int max(int a, int b) {return (a > b) ? a : b;
}Node* newNode(int key) {Node* node = (Node*)malloc(sizeof(Node));node->key = key;node->left = node->right = NULL;node->height = 1;return node;
}Node* rightRotate(Node* y) {Node* x = y->left;Node* T2 = x->right;x->right = y;y->left = T2;y->height = max(height(y->left), height(y->right)) + 1;x->height = max(height(x->left), height(x->right)) + 1;return x;
}Node* leftRotate(Node* x) {Node* y = x->right;Node* T2 = y->left;y->left = x;x->right = T2;x->height = max(height(x->left), height(x->right)) + 1;y->height = max(height(y->left), height(y->right)) + 1;return y;
}int getBalance(Node* N) {if (N == NULL)return 0;return height(N->left) - height(N->right);
}Node* insert(Node* node, int key) {if (node == NULL)return newNode(key);if (key < node->key)node->left = insert(node->left, key);else if (key > node->key)node->right = insert(node->right, key);elsereturn node;node->height = 1 + max(height(node->left), height(node->right));int balance = getBalance(node);if (balance > 1 && key < node->left->key)return rightRotate(node);if (balance < -1 && key > node->right->key)return leftRotate(node);if (balance > 1 && key > node->left->key) {node->left = leftRotate(node->left);return rightRotate(node);}if (balance < -1 && key < node->right->key) {node->right = rightRotate(node->right);return leftRotate(node);}return node;
}

#### C++ 实现：

class AVLNode {
public:int key;int height;AVLNode* left;AVLNode* right;AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};class AVLTree {
private:AVLNode* root;int height(AVLNode* N) {if (!N) return 0;return N->height;}int balanceFactor(AVLNode* N) {if (!N) return 0;return height(N->left) - height(N->right);}AVLNode* rightRotate(AVLNode* y) { /*... Similar to C ...*/ }AVLNode* leftRotate(AVLNode* x) { /*... Similar to C ...*/ }public:AVLTree() : root(nullptr) {}void insert(int key) {root = insert(root, key);}AVLNode* insert(AVLNode* node, int key) { /*... Similar to C ...*/ }
};

#### Java 实现：

class AVLNode {int key, height;AVLNode left, right;AVLNode(int d) {key = d;height = 1;}
}public class AVLTree {AVLNode root;int height(AVLNode N) {if (N == null)return 0;return N.height;}int getBalance(AVLNode N) {if (N == null)return 0;return height(N.left) - height(N.right);}AVLNode rightRotate(AVLNode y) { /*... Similar to C ...*/ }AVLNode leftRotate(AVLNode x) { /*... Similar to C ...*/ }AVLNode insert(AVLNode node, int key) { /*... Similar to C ...*/ }public void insert(int key) {root = insert(root, key);}
}

上述代码只展示了部分实现，因为 AVL 树的完整实现包括其他操作，如删除节点，并且需要处理各种平衡情况。上述代码应该为你提供了一个基本的理解，但在实际应用中可能需要进一步的完善和优化。