【数据结构与算法】8.二叉树的基本概念|前序遍历|中序遍历|后序遍历

简介: 【数据结构与算法】8.二叉树的基本概念|前序遍历|中序遍历|后序遍历


1. 树形结构(了解)

1.1 概念

树是一种非线性数据结构,它是由n(n>=0)个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一个倒挂的树,也就是说它是根朝上,而叶子朝下。它具有的特点:


  • 有一个特殊的几点,称为根节点,根节点没有前驱节点
  • 除根节点外,其余节点被分成m(m>0)个互不相交的集合 T1、T2、…、Tm,其中每一个集合Ti(1<=i<=m)又是一颗与类似的字数。每颗子树的根节点有且只有一个前驱,可以有0个或多个后继
  • 树是递归定义的。


【注意】:树形结构中,子树间不能有交集,否则就不是树形结构


1.2 概念(重要)

节点的度:一个节点含有子树的个数称为该节点的度;如下图:A的度为2

树的度:一棵树中,所有的节点度的最大值称为树的度;如下图:树的度为3

叶子节点或终端节点:度为0的节点称为叶子节点;如下图:G、H、I、J、F节点为叶子节点

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;如下图:A是B的父节点

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;如下图:B是A的孩子节点

根节点:一棵树中,没有双亲节点的节点;如下图:A

节点的层次:从根节点定义来,根为第1层,根的子节点为第2层,以此类推

树的高度:树中节点的最大层次;如下图:树的高度为4

树的以下概念只需了解,知道是什么意思即可:

非终端节点或分支节点:度不为0的节点;如下图:B、C、D、E节点为分支节点

兄弟节点:具有相同父节点的节点互称为兄弟节点;如下图:B、C是互为兄弟节点

堂兄弟节点:双亲在同一层的节点互为堂兄弟节点;如下图:D、E是互为堂兄弟节点

节点的祖先:从根到该节点所经分支上的所有节点;如下图:A是所有节点的祖先

子孙:以某个节点为根的子树中任一节点都称为该节点的的子孙。

如下图:所有的接地那都是A的子孙森林:由m(m>=0)棵互不相交的树组成的集合称为森林


1.3 树的表示形式(了解)

树的结构相对线性表就比较复杂了,要存储不是起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,孩子表示法,孩子双亲表示法,孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法

class Node {
    int val; // 树中存储的数据
    Node firstChild; // 第一个孩子引用
    Node nextBrother;// 下一个兄弟引用
}

线性结构与树形结构的对比

线性结构 树形结构
第一个数据元素:无前驱 根节点:无双亲,唯一
最后一个数据元素:无后继 叶节点:无孩子,可以多个
中间元素:一个前驱,一个后继 中间节点:一个双亲多个孩子


1.4 树的应用

文件系统管理(目录和文件)



2. 二叉树

2.1 概念

二叉树是n(n>=0)个节点的有限集合,该集合或者空集(空二叉树),或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。



从上图可以看出:

  1. 二叉树不存在度大于2的节点
  2. 二叉树的子树有左右之分,因此二叉树是有序树

总结:对于任意的二叉树都是由以下几种情况复合而成的



大自然中的二叉树:

2.2 特殊的二叉树


满二叉树:一颗二叉树,如果每层的节点数都达到最大值,则这课二叉树就是,满二叉树。也就是说,如果一颗二叉树的层数为K,且节点总数是 2K -1,则它就是满二叉树

完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有 n 个节点的二叉树,每个节点都与深度为 K 的满二叉树中编号从0至 n-1的节点(从上到下,从左到右,依次存放)——对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。



2.3 二叉树的性质

若根节点的层数为1,则一颗非空二叉树的第 i 层上最多有 2i-1 (i > 0)个节点

若只有根节点的二叉树的深度为1,则深度为 k 的二叉树的最大节点数是2k - 1(k >= 0)

对任何一颗二叉树,如果其叶子节点个数为 n0,度为2的非叶子节点个数为n2,则有n0 = n2 + 1

具有 n 个节点的完全二叉树的深度 k 为long2(n+1)上取整

对于具有 n 个节点的完全二叉树,如果按照从上至下、从左至右的顺序对所有节点从0开始编号,则对于序号 i 的节点有:

若 i > 0,双亲序号:(i - 1) / 2;i = 0,i为根节点编号,无双亲节点

若 2i + 1 < n,左孩子序号:2i + 1,否则无左孩子

若 2i + 2 < n,右孩子序号:2i + 2,否则无右孩子

2.4 二叉树的存储

二叉树的存储结构分为:顺序存储类似于链表的链式存储

二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方法有孩子表示法和孩子双亲表示法,具体如下:

// 孩子表示法
class Node {
   int val;// 数据域
   Node left;// 左孩子的引用,常常代表左孩子为根的整棵左子树
   Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
   int val;// 数据域
   Node left;// 左孩子的引用,常常代表左孩子为根的整棵左子树
   Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
   Node parent;    // 当前节点的根节点
}

3. 二叉树的基本操作

3.1 前置说明

在学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树的结构掌握还不够深入,为了降低学习成本,此处手动创建一颗二叉树,快速进入二叉树的学习。

public class BinaryTree {
    // 节点类
    static class TreeNode{
        public char val;
        public TreeNode left; // 左节点
        public TreeNode right; // 右节点

        // 构造方法
        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 以穷举的方式 创建一颗二叉树
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return A; // 返回根节点
    }
}


注意:上诉代码并不是创建二叉树的方式。

回顾一下二叉树的概念:

  1. 空树
  2. 非空:根节点,根节点的左子树、根节点的右子树组成的



从概念可以看出:二叉树的定义是递归式的,因此后续的基本操作中都是按照该概念实现的。

3.2 二叉树的遍历

学习二叉树的结构,最简单的方式就是遍历,所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如:打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一,是二叉树上进行其它运算之基础。

1. 前序遍历

前序遍历的顺序: 根节点-> 左子树 -> 右子树

遍历演示 :


代码 :

// 前序遍历
void preOrder(TreeNode root) {
  // 判断是否为空树
  if (root == null) {
    return;
  }
  // 打印当前节点的值
  System.out.print(root.val + " ");
  // 递归左子树
  preOrder(root.left);
  // 递归右子树
  preOrder(root.right);
}


2. 中序遍历

中序遍历的顺序: 左子树 -> 根结点 -> 右子树

遍历演示:

代码 :

// 中序遍历
void inOrder(TreeNode root) {
  if (root == null) {
    return;
  }
  // 递归左子树
  inOrder(root.left);
  // 打印当前节点的值
  System.out.print(root.val + " ");
  // 递归右子树
  inOrder(root.right);
}

3. 后序遍历

后序遍历的顺序: 左子树 -> 右子树 -> 根结点

代码:

// 后序遍历
void postOrder(TreeNode root) {
  if (root == null) {
    return;
  }
  // 递归左子树
  postOrder(root.left);
  // 递归右子树
  postOrder(root.right);
  // 打印当前节点的值
  System.out.print(root.val + " ");
}

测试代码:

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree();

        System.out.print("前序遍历:");
        binaryTree.preOrder(root);

        System.out.println();

        System.out.print("中序遍历:");
        binaryTree.inOrder(root);

        System.out.println();

        System.out.print("后序遍历:");
        binaryTree.postOrder(root);
    }
}

运行结果:

相关文章
|
26天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
2月前
|
存储
【初阶数据结构篇】二叉树基础概念
有⼀个特殊的结点,称为根结点,根结点没有前驱结点。
|
3月前
|
存储
【数据结构】树和二叉树的概念及结构
数据结构——树和二叉树的概念及结构
65 3
【数据结构】树和二叉树的概念及结构
|
2月前
|
机器学习/深度学习 算法
【机器学习】解释对偶的概念及SVM中的对偶算法?(面试回答)
解释了对偶的概念,指出对偶性在优化问题中的重要性,尤其是在强对偶性成立时可以提供主问题的最优下界,并且详细阐述了支持向量机(SVM)中对偶算法的应用,包括如何将原始的最大间隔优化问题转换为对偶问题来求解。
55 2
|
2月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
|
2月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
65 0
|
2月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
34 0
|
3月前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
29 1
|
3月前
|
机器学习/深度学习 人工智能 自然语言处理
机器学习之深度学习算法概念
深度学习算法是一类基于人工神经网络的机器学习方法,其核心思想是通过多层次的非线性变换,从数据中学习表示层次特征,从而实现对复杂模式的建模和学习。深度学习算法在图像识别、语音识别、自然语言处理等领域取得了巨大的成功,成为人工智能领域的重要技术之一。
71 3
|
3月前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
29 3
下一篇
无影云桌面