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

简介: 数据结构 | 二叉树的概念及前中后序遍历(一)

一、树概念及结构

下面内容来自百度百科

二叉树(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

相关文章
|
11天前
|
算法
【算法与数据结构】二叉树(前中后)序遍历2
【算法与数据结构】二叉树(前中后)序遍历
|
7天前
|
算法 索引
【算法与数据结构】深入二叉树实现超详解(全源码优化)
【算法与数据结构】深入二叉树实现超详解(全源码优化)
|
7天前
|
存储 算法
【算法与数据结构】深入解析二叉树(二)之堆结构实现
【算法与数据结构】深入解析二叉树(二)之堆结构实现
|
17天前
|
存储 算法 搜索推荐
数据结构-概念版(七)
数据结构-概念版
48 0
|
17天前
|
存储 算法 Serverless
数据结构-概念版(六)
数据结构-概念版
35 0
|
18天前
|
存储 算法 程序员
【数据结构】【版本2.0】【树形深渊】——二叉树入侵
【数据结构】【版本2.0】【树形深渊】——二叉树入侵
|
19天前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
11 0
|
19天前
|
存储 算法 C语言
【C/C++ 数据结构 树】探索C/C++中的二叉树:从理论到实践
【C/C++ 数据结构 树】探索C/C++中的二叉树:从理论到实践
59 0
|
6天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
22 0
|
30天前
【栈】数据结构栈的实现
【栈】数据结构栈的实现