当前位置：首页 > news >正文

【数据结构】树和二叉树

news 来源：原创 2024/9/20 8:27:37

1.前言

2.树

2.1树的概念

2.2树中的重要概念

2.3树的表示形式

2.4树的应用

3.二叉树

3.1概念

3.2两种特殊的二叉树

3.3二叉树的性质

3.4二叉树的存储

3.5二叉树的遍历方式

3.5.1创建二叉树

3.5.2二叉树的遍历

3.6二叉树的基本操作

4.总结

1.前言

二叉树是数据结构中比较难的数据结构之一，树在计算机中的应用也是非常广泛，例如文件系统、数据库查询、图形处理等。树结构的优点是：可以用来表示关系，可以用来存储和查询大量数据，可以用来实现文件管理和数据库管理等功能。接下来，让我们一起去认识并学习树和二叉树！

2.树

2.1树的概念

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

有一个特殊的结点，称为 根结点，根结点没有前驱结点 ；

除根结点外，其余结点被分成 M(M > 0) 个互不相交的集合 T1 、 T2 、 ...... 、 Tm ，其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每 棵子树的根结点有且只有一个前驱 ，可以有 0 个或多个后继；

树是递归定义的。

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

2.2树中的重要概念

结点的度：一个结点含有子树的个数称为该结点的度；如上图：A的度为6。
树的度：一棵树中，所有结点度的最大值称为树的度；如上图：树的度为6。
叶子结点或终端结点：度为0的结点称为叶结点；如上图：B、C、H、I...等节点为叶结点。
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点。
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点。
根结点：一棵树中，没有双亲结点的结点；如上图：A。
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
树的高度或深度：树中结点的最大层次；如上图：树的高度为4。

2.3树的表示形式

实际中树有很多种表示方式，如： 双亲表示法 ， 孩子表示法 、 孩子双亲表示法 、 孩子兄弟表示法 等等。最常用的是 孩子兄弟表示法 。

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

2.4树的应用

树的应用非常广泛，比如文件系统管理（目录和文件）。

3.二叉树

3.1概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空

2. 或者是由 一个根节 点加上两棵别称为 左子树 和 右子树 的二叉树组成。

从上图可以看出：

1. 二叉树不存在度大于2的结点

2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

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

3.2两种特殊的二叉树

1. 满二叉树:一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是2^k -1，则它就是满二叉树。

2. 完全二叉树 : 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n个结点的二叉树，当且仅当其每一个结点都与深度为K 的满二叉树中编号从 0 至 n-1的结点一一对应时称之为完全二叉树。要注意的是 满二叉树是一种特殊的完全二叉树 。

3.3二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个节点(i > 0)。

2.若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大节点数是2^k - 1(k >= 0)
3.对任何一棵二叉树，如果其叶节点个数为n0，度为2的非叶节点个数为n2，则有n0 = n2 +1
4.具有n个节点的完全二叉树的深度k为log₂(n + 1)向上取整
5.对于具有n个节点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的节点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子

下面给大家来几道例题牛刀小试一下。

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）
A 不存在这样的二叉树
B 200
C 198
D 199

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（）
A n
B n+1
C n-1
D n/2

3.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（）
A 11
B 10
C 8
D 12

答案：
1.B (199+1)
2.A 2n = n0 + n1 + n2，n0 = n2 + 1，n1 = 1，因此 n0 = n
3.B n0 + 0 + n0 - 1 = 767 可得n0 = 384
4.B log₂(531 + 1) 解出h = 10

3.4二叉树的存储

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

下面我们主要以链式存储来讲解。

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式 ，具体如下：

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

本文后面主要采用孩子表示法创建二叉树。

3.5二叉树的遍历方式

3.5.1创建二叉树

目前我们这里是手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，并不是真正的创建二叉树的方式。

public class BinaryTree {public class TreeNode {TreeNode left;TreeNode right;int val;public TreeNode(int val) {this.val = val;}}public TreeNode createTree() {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);node1.left = node2;node1.right = node3;node2.left = node4;node2.right = node5;node3.left = node6;return node1;}
}

3.5.2二叉树的遍历

1. 前中后序遍历

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

根据遍历根节点的先后次序有以下遍历方式：

前序遍历：访问根结点—— > 根的左子树—— > 根的右子树。

中序遍历：根的左子树——>根节点—— >根的右子树。

后序遍历：根的左子树——>根的右子树—— >根节点。

前序遍历

代码实现如下：

    //前序遍历public void preOrder(TreeNode root) {//如果是空树则不需要遍历if (root == null) {return;}System.out.print(root.val + " ");//访问根节点preOrder(root.leftNode);//前序遍历左子树preOrder(root.rightNode);//前序遍历右子树}

中序遍历

代码实现如下：

    //中序遍历public void inOrder(TreeNode root) {//如果是空树则不需要遍历if (root == null) {return;}inOrder(root.leftNode);//中序遍历左子树System.out.print(root.val + " ");//访问根节点inOrder(root.rightNode);//中序遍历右子树}

后序遍历

代码实现如下：

    //后序遍历public void postOrder(TreeNode root) {//如果是空树则不需要遍历if (root == null) {return;}postOrder(root.leftNode);//后序遍历左子树postOrder(root.rightNode);//后序遍历右子树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.println("前序遍历：");//前序遍历结果：1 2 4 5 3 6binaryTree.preOrder(root);System.out.println();System.out.println("中序遍历：");//中序遍历结果：4 2 5 1 6 3binaryTree.inOrder(root);System.out.println();System.out.println("后序遍历：");//后序遍历结果：4 5 2 6 3 1binaryTree.postOrder(root);}
}

运行结果如下：

上面所创建出来的二叉树画出来就是下面这样子。

2.层序遍历

设二叉树的根节点所在层数为1 ，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推， 自上而下，自左至右 逐层访问树的结点的过程就是层序遍历。

以上面创建的二叉树为例，实现层次遍历的代码如下：

public void levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return;}queue.offer(root);while (!queue.isEmpty()) {TreeNode cur = queue.poll();System.out.print(cur.val + " ");if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}}System.out.println();}

我们通过队列实现层序遍历的功能，只要队列不为空，就把获取到的队头元素给cur，并且同时将这个元素打印出来，在把cur的左右两边代进去，如果左右两边为空的则不能代进去，只有非空才能代入里面。

下面给大家来几道关于二叉树遍历的习题练练手。

1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为 ()

A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA

2. 二叉树的先序遍历和中序遍历如下：先序遍历： EFHIGJK; 中序遍历： HFIEJKG. 则二叉树根结点为 ()

A: E     B: F     C: G     D: H

3. 设一课二叉树的中序遍历序列： badce ，后序遍历序列： bdeca ，则二叉树前序遍历序列为 ()

A: adbce   B: decab    C: debac    D: abcde

4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出 ( 同一层从左到右 ) 的序列为 ()

A: FEDCBA  B: CBAFED  C: DEFCBA  D: ABCDEF

答案：1.A 2.A 3.D 4.A

3.6二叉树的基本操作

1.获取树中节点的个数

//获取树的节点个数//方法1：递归public int size(TreeNode root) {if (root == null) {return 0;}int ret = size(root.left) + size(root.right) + 1;return ret;}//方法2：遍历public static int nodeSize;public void size1(TreeNode root) {if (root == null) {return;}nodeSize++;size1(root.left);size1(root.right);}

public class Test {//二叉树的基本操作public static void main(String[] args) {BinaryTree binaryTree = new BinaryTree();BinaryTree.TreeNode root = binaryTree.createNode();binaryTree.preOrder(root);System.out.println();binaryTree.inOrder(root);System.out.println();binaryTree.postOrder(root);System.out.println();System.out.print("树的节点个数：");System.out.println(binaryTree.size(root));}
}

运行结果如下：

2.获取叶子节点的个数

//获取叶子节点的个数//方法1public int getLeafNodeCount(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);}//方法2：遍历public int leafSize;public void getLeafNodeCount1(TreeNode root) {if (root == null) {return;}if (root.left == null && root.right == null) {leafSize++;}getLeafNodeCount1(root.left);getLeafNodeCount1(root.right);}

3. 获取第K层节点的个数

    //第K层有多少个结点public int getKLeaveNodeCount(TreeNode root, int k) {if (root == null) {return 0;}if (k == 1) {return 1;}return getKLeaveNodeCount(root.left, k - 1)+ getKLeaveNodeCount(root.right, k - 1);}

4.获取二叉树的高度

//求二叉树的高度//时间复杂度：O(N)public int getHeight(TreeNode root) {if (root == null) {return 0;}int leafHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leafHeight > rightHeight ?leafHeight + 1 : rightHeight + 1;}

5.检测值为value的元素是否存在

 // 检测值为value的元素是否存在public TreeNode find(TreeNode root, int val) {if (root == null) {return null;}if (root.val == val) {return root;}TreeNode ret = find(root.left, val);if (ret != null) {return ret;}ret = find(root.right, val);if (ret != null) {return ret;}return null;}

6.判断一棵树是不是完全二叉树

//判断一棵树是不是完全二叉树public boolean isCompleteTree(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return true;}queue.offer(root);while (!queue.isEmpty()) {TreeNode cur = queue.poll();if (cur == null) {break;}queue.offer(cur.left);queue.offer(cur.right);}while (!queue.isEmpty()) {TreeNode node = queue.peek();if (node != null) {return false;} else {queue.poll();}}return true;}