数据结构之二叉树
创始人
2024-05-24 19:24:22
0

🎈一.二叉树相关概念

1.树

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合,树结构通常用来存储逻辑关系为 "一对多" 的数据。例如:

关于树的几个重要概念:

1)树的度:一棵树中,所有结点度的最大值称为树的度,如上图,这棵树的度为3;

2)节点的度:一个结点含有子树的个数称为该结点的度,如上图,A节点的度为3;

3)根节点:一棵树中,没有双亲结点的结点,如上图,A就是根节点;

4)叶子节点:简单来说,度为0的就是叶子节点,如上图,K,L,F,M等都是叶子节点;

5)树的高度或深度:树中结点的最大层次,如上图,树的高度为4;


  那么什么是二叉树呢? 

简单地理解,满足以下两个条件的树就是二叉树:

  1. 本身是有序树;
  2. 树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2;

 如图:

🎈二.二叉树的性质

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

2.若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是2^k-1 (k>=0);

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1;

✅关于此结论的推导:

对于任意一棵二叉树,一棵有N个节点的树就有N-1条边

假设度为0的节点为n0,度为1的节点为n1,度为2的节点为n2,度为0的节点没有边,度为1的节点有1条边,度为2的节点有2条边,由此可得:

N-1=n1*1+n2*2   ----------------产生的边的关系

N=n0+n1+n2       ----------------产生节点的关系

联立就可以得出这个结论:n0=n2+1

4.具有n个结点的完全二叉树的深度k为 log2(n+1)上取整;

✅习题:

1)  在具有 2n 个结点的完全二叉树中,叶子结点个数为(A);

A .n            B. n+1            C. n-1           D. n/2

解析:

 完全二叉树分奇偶数俩种情况,如上图,本题有2n个节点,是偶数,那么度为1的节点数只有1个,所以可知:

2n=n0+n1+n2;

n0=n2+1;

代入可求:n0=n;

2)一个具有767个节点的完全二叉树,其叶子节点个数为(B);

A. 383         B. 384             C. 385           D. 386

解析:因为它是一棵完全二叉树,节点数为奇数,说明它是一棵满二叉树,所以没有度为1的节点,由此可知:

767=n0+n2;

n0=n2+1;

联立上式可以求出答案

🎈三.构造二叉树

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

构造一个类,里面存放左子树,右子树,数据域;

public static class TreeNode {public char val;//数据域public TreeNode left;//左节点public TreeNode right;//右节点public TreeNode(char val) {this.val = val;}}//构造树public TreeNode createTree() {TreeNode node1 = new TreeNode('A');TreeNode node2 = new TreeNode('B');TreeNode node3 = new TreeNode('C');TreeNode node4 = new TreeNode('D');TreeNode node5 = new TreeNode('E');TreeNode node6 = new TreeNode('F');TreeNode node7 = new TreeNode('G');node1.left = node2;node1.right = node3;node2.left = node4;node2.right = node5;node3.left = node6;node3.right = node7;return node1;}
}

🎈四.二叉树的相关操作

1.前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。

//前序遍历public void preOrder(TreeNode root) {if (root == null) {return;}System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);}

2.中序遍历

中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。

//中序遍历public void inOrder(TreeNode root) {if (root == null) {return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}

3.后序遍历

后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。

//后序遍历public void postOrder(TreeNode root) {if (root == null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");}

4.获取书中节点的个数

// 获取树中节点的个数public int size(TreeNode root) {if (root == null) {return 0;}int leftSize = size(root.left);int rightSize = size(root.right);return leftSize + rightSize + 1;//个数=左树的节点树+右树的节点树+1}

5.获取叶子节点数

// 获取叶子节点的个数public int getLeafNodeCount(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;//如果左右两边都为空,那么一定是叶子节点}int leftSize = getLeafNodeCount(root.left);int rightSize = getLeafNodeCount(root.right);return leftSize + rightSize;}

6.获取第k层的节点数

// 获取第K层节点的个数public int getKLevelNodeCount(TreeNode root, int k) {if (root == null) {return 0;}if (k == 1) {return 1;}int leftSize = getKLevelNodeCount(root.left, k - 1);int rightSize = getKLevelNodeCount(root.right, k - 1);return leftSize + rightSize;}

7.获取二叉树的高度

// 获取二叉树的高度public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}

8.查找value值是否存在树中

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

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF,目录中的页码并非PDF中直接索引的页码...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...