✅作者简介：大家好,我是Philosophy7？让我们一起共同进步吧！🏆 📃个人主页：Philosophy7的csdn博客
🔥系列专栏： 数据结构与算法
👑哲学语录: 承认自己的无知，乃是开启智慧的大门
💖如果觉得博主的文章还不错的话，请点赞👍+收藏⭐️+留言📝支持一下博>主哦🤞

文章目录

• 树
• • 树的概念
  • 什么是二叉树?
  • • 二叉树的性质:
    • 完全二叉树
    • 满二叉树
    • 创建二叉树
    • • ①创建结点
      • ②创建二叉树模型
      • ③构建二叉树
    • 二叉树的遍历
    • • 1.深度优先遍历
      • 2.广度优先遍历

树

树和图是典型的非线性结构，现在就让我们来了解一下树的知识吧

学习目标

1. 了解树的基本概念和术语
2. 掌握二叉树的相关概念

树的概念

生活中的树，就含有很多的树叶，我们数据结构当中所述说的树，肯定也要与实际生活相贴切。因此数据结构中的树也有大量叶子。在这里我们就来介绍一下关于树的相关概念

• 树 : 树是由n个结点组成的有限集合。如果n = 0就叫做空树,如果n > 0，有且只有一个就叫做树的根节点。
• 结点 : 树中的每个元素称为结点
• 结点的度 : 该结点拥有的子树个数称为结点或终端结点。例如上图: A的结点度为2，B结点的度为3
• 叶子结点 : 度为0的结点称为叶子结点(也就是没有子结点) 例如:D F G H I J这些结点都是叶子结点
• 分支结点 : 度不为0的称为分支结点 例如 : A B C E是分支结点
• 树的度 : 树的度是树中各结点的度的最大值 例如 : B有三个子结点 所以树的度 = 3
• 孩子结点 : 一个结点的子结点 称为该结点的孩子结点 例如 : B 和 C是A的孩子
• 双亲结点 : 一个结点称为其子节点的双亲结点 例如 ：B和C的双亲结点就是A
• 兄弟结点 : 同一个双亲的孩子之间称为兄弟结点 例如 : B和C是兄弟
• 树的高度 : 树中结点的最大层次树称为树的高度或深度 例如上图 树的最大层数为4
• 森林 : 由n棵树组成的集合称为森林

什么是二叉树?

二叉树是树的一种特殊形式。简单的来说就是，任意结点最多只能拥有两个子节点。

如图所示:

二叉树的性质:

1. 二叉树的第i层上的结点数目最多为2的i-1次方 (i>=1) 例如: 第三层 = 2^3-1次方 = 4
2. 深度为k的二叉树至多有2的k次方-1个结点 例如: 深度 = 3 == 2^3 -1 = 7 也就是深度为3的二叉树 最多有个结点
3. 包含n个结点的二叉树的高度至少为(log2n) + 1 (以2为底) 例如: 若结点是7个 --> log2 7 +1 = 3 高度=3
4. 在任意一个二叉树中，若终端结点的个数为n0,度为2的节点数为n2，则n0=n2+1

二叉树结点的两个子结点，一个被称为左子结点，一个被称为右子结点。

二叉树还有两种特殊的形式: 一个被称为满二叉树，一个被称为完全二叉树

完全二叉树

定义:一颗二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶子结点靠在最左的若干位置上，这样的树就被称为完全二叉树。

特点：

• 叶子结点只能出现在最下层和次下层，叶子结点集中在左子结点。
• 一颗满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

满二叉树

通俗来讲就是除了叶子结点，每个结点都有两个子结点。

满二叉树的性质:

1. 一颗树的深度为h，最大层数为k，深度与最大层数相同，k=h。
2. 叶子数为2h; 例如: 若树的深度为2 则2×2 = 4个叶子结点
3. 第k层的节点数是: 2的k-1次方
4. 总结点数是: 2的k次方 - 1 且总结点数一定是奇数

创建二叉树

①创建结点

package com.philosophy7.binary;public class BinaryTreeNode {    //结点数据    private String data;    //左子结点 + 右子结点    private BinaryTreeNode leftChild;    private BinaryTreeNode rightChild;    public BinaryTreeNode() {    }    public BinaryTreeNode(String data, BinaryTreeNode leftChild, BinaryTreeNode rightChild) { this.data = data; this.leftChild = leftChild; this.rightChild = rightChild;    }    public String getData() { return data;    }    public void setData(String data) { this.data = data;    }    public BinaryTreeNode getLeftChild() { return leftChild;    }    public void setLeftChild(BinaryTreeNode leftChild) { this.leftChild = leftChild;    }    public BinaryTreeNode getRightChild() { return rightChild;    }    public void setRightChild(BinaryTreeNode rightChild) { this.rightChild = rightChild;    }}

②创建二叉树模型

package com.philosophy7.binary;/*    创建二叉树 初始化根节点 初始化空的二叉树 */public class BinaryTree {    private BinaryTreeNode root; //初始化根节点    //初始化一个二叉树    public BinaryTree(){    }    public BinaryTreeNode getRoot() { return root;    }    public void setRoot(BinaryTreeNode root) { this.root = root;    }}

③构建二叉树

package com.philosophy7.binary;public class BinaryTreeTest {    public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); //空的二叉树 //创建结点 BinaryTreeNode dNode = new BinaryTreeNode("D",null,null); BinaryTreeNode eNode = new BinaryTreeNode("E",null,null); BinaryTreeNode fNode = new BinaryTreeNode("F",null,null); BinaryTreeNode cNode = new BinaryTreeNode("C",fNode,null); BinaryTreeNode bNode = new BinaryTreeNode("B",dNode,eNode); BinaryTreeNode root = new BinaryTreeNode("A",bNode,cNode); //创建二叉树 binaryTree.setRoot(root);    }}

二叉树的遍历

二叉树的遍历可分为

• 深度优先遍历
  • 先序遍历
  • 中序遍历
  • 后序遍历
• 广度优先遍历
  • 层级遍历

1.深度优先遍历

这是一种抽象的算法思想，决定着访问某些复杂数据结构的顺序。比如我们常见的数据结构树和图这些复杂的数据结构，深度优先遍历和广度优先遍历经常会被提及到。

深度优先遍历，顾名思义，就是直接深入到底的一种访问方式。

下面我们通过二叉树的先序遍历、中序遍历、后序遍历，来一一介绍深度优先是怎么回事。

先序遍历:

访问顺序是: 先根节点 --> 左子树 --> 右子树

中序遍历:

访问顺序是: 先左子树 --> 根节点 --> 右子树

后序遍历:

访问顺序是: 先左子树 --> 右子树 --> 根节点

在这里我们使用递归的方式来实现二叉树的深度优先遍历

 //先序遍历    public static void preOrderTraver(BinaryTreeNode node){ if (node == null){     return; } System.out.print(node.getData() + "--->"); preOrderTraver(node.getLeftChild()); preOrderTraver(node.getRightChild());    }    //中序遍历    public static void inOrderTraver(BinaryTreeNode node){ if (node == null){     return; } inOrderTraver(node.getLeftChild()); System.out.print(node.getData() + "--->"); inOrderTraver(node.getRightChild());    }    //后序遍历    public static void postOrderTraver(BinaryTreeNode node){ if (node == null){     return; } postOrderTraver(node.getLeftChild()); postOrderTraver(node.getRightChild()); System.out.print(node.getData() + "--->");    }

2.广度优先遍历

上面我们已经了解了深度优先遍历，可见深度优先遍历是直接深入进去，那么广度优先恰恰相反:

它是访问一层然后遍历一层 : 从上到下，从左到右

实现层序遍历的方式，我们需要借助另一种数据结构，那就是队列

层序遍历的过程:

①根节点A入队，然后出队，输出结点A信息，并得到结点A的左子树和右子树，让结点B和C入队。

②结点B出队 输出结点B 并得到结点B的左子树和右子树。让结点D和E入队

③结点C出队 输出结点C 并得到其左子树和右子树 让其入队

④结点D出队，输出结点D 由于该结点是叶子结点 所以没有新结点入队 了

⑤结点E出队 输出结点E 同上述一样

⑥结点F出队 输出结点F 同上述一样。

//层序遍历public static void levelOrderTraversal(BinaryTreeNode node){    if (node == null) { return;    }    Queue<BinaryTreeNode> queue = new LinkedList<>();    queue.offer(node);    while (!queue.isEmpty()){ BinaryTreeNode top = queue.poll(); System.out.print(top.getData() + "-->"); if (top.getLeftChild() != null){     queue.offer(top.getLeftChild()); } if (top.getRightChild()!=null){     queue.offer(top.getRightChild()); }    }}