数据结构 | 二叉树的概念及前中后序遍历（一）

一、树概念及结构

下面内容来自百度百科

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。

常见的树结构包括二叉树（Binary Tree）、二叉搜索树（Binary Search Tree）、AVL树、红黑树等。树的应用非常广泛，例如在数据库中的索引结构、文件系统的组织、图形算法中的优先队列等。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

1.1 树的相关概念

树（Tree）是一种重要的数据结构，它在计算机科学中被广泛应用。树是由节点（Node）和边（Edge）组成的集合，节点之间通过边相连。树的一个特点是它是一个层次结构，顶部的节点称为根节（Root），最底部的节点称为叶节点（Leaf），中间的节点称为内部节点（Internal Node）。

节点的度： 一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

叶节点或终端节点： 度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点

非终端节点或分支节点： 度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

双亲节点或父节点： 若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

孩子节点或子节点： 一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

兄弟节点： 具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

树的度： 一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

节点的层次： 从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度： 树中节点的最大层次； 如上图：树的高度为4

堂兄弟节点： 双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

节点的祖先： 从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙： 以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林： 由m（m>0）棵互不相交的树的集合称为森林；

二、树的表示

• 有多种方法可以表示树，其中两种主要的表示方法是：儿子表示法（Child Representation）和父母表示法（Parent Representation）。此外，对于二叉树，还有更特定的表示方法，如数组表示法和链接表示法。
• 儿子表示法（Child Representation）：
• 在儿子表示法中，每个节点包含一个指向其所有子节点的指针。这种表示方法通常用于多叉树，其中一个节点可以有多个子节点。

A
   / \
  B   C
 / \
D   E

父母表示法（Parent Representation）：

• 在父母表示法中，每个节点包含一个指向其父节点的指针。这种表示方法通常用于树的深度优先遍历。

codeA -> NULL
B -> A
C -> A
D -> B
E -> B

2.2 树在实际中的运用（表示文件系统的目录树结构）

• 树结构在实际中广泛应用，而表示文件系统的目录树结构是树结构的一个典型应用之一。文件系统的目录结构可以很自然地用树来表示
• 比如学过Linux的同学就知道这个linux是一个树状结构，根就是/

三、二叉树概念及结构

• 二叉树（Binary Tree）是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的结构和性质使得它在计算机科学中有着广泛的应用。

3.1 二叉树的基本概念

• 节点（Node）： 二叉树的基本单元，每个节点包含一个数据元素和指向左右两个子节点的指针。
• 根节点（Root）： 二叉树的顶端节点，是树的起始点，没有父节点。
• 叶节点（Leaf）： 没有子节点的节点称为叶节点，位于树的末端。
• 内部节点（Internal Node）： 除了根和叶节点之外的节点，有至少一个子节点的节点称为内部节点。
• 子节点（Child）： 一个节点的直接下层节点称为其子节点。
• 父节点（Parent）： 一个节点的直接上层节点称为其父节点。
• 兄弟节点（Sibling）： 具有相同父节点的节点称为兄弟节点。
• 深度（Depth）： 一个节点到根节点的路径长度称为节点的深度，根节点的深度为0。
• 高度（Height）： 一个节点到其最远叶节点的路径长度称为节点的高度，树的高度是根节点的高度。

3.2 二叉树的结构：

a. 满二叉树（Full Binary Tree）：

• 在满二叉树中，除了叶节点，每个节点都有两个子节点。所有叶节点都在同一层上。

1
      /   \
     2     3
    / \   / \
   4   5 6   7

b. 完全二叉树（Complete Binary Tree）：

• 在完全二叉树中，除了最后一层的叶节点外，其他层都是满的，且最后一层的叶节点都靠左排列。

1
      /   \
     2     3
    / \   /
   4   5 6

c. 二叉搜索树（Binary Search Tree，BST）：

• 在二叉搜索树中，每个节点的左子树都比该节点小，右子树都比该节点大，这使得查找、插入和删除等操作非常高效。

4
      /   \
     2     6
    / \   / \
   1   3 5   7

四、二叉树的应用

1. 搜索和排序： 二叉搜索树用于实现快速的搜索和排序操作。
2. 表达式树： 用于表示数学表达式，方便进行求值。
3. 文件系统： 用于表示文件目录的层次结构。
4. 编译器： 在语法分析阶段，使用语法树（通常是二叉树）表示程序的语法结构。
5. 哈夫曼树： 用于数据压缩算法中构建最优的编码树。
6. 游戏树： 在博弈论中，用于表示游戏的决策树。

数据结构 | 二叉树的概念及前中后序遍历（二）:https://developer.aliyun.com/article/1426955