《重学数据结构》之什么是二叉树,2021最新Java面试题目
2021/12/20 20:22:09
本文主要是介绍《重学数据结构》之什么是二叉树,2021最新Java面试题目,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
节点到叶节点的最长路径(边数)
- 树的高度
根节点的高度
- 节点的深度
根节点到该节点所经历的边的个数
- 节点的层数
节点的深度+1
二叉树(Binary Tree)
===============================================================================
最常用的树结构。
每个节点最多有两个子节点:左子节点,右子节点。
- 满二叉树
叶节点全在最底层,除叶节点外,每个节点都有左右两个子节点
- 完全二叉树
叶节点都在最底下两层,最后一层的叶节点都靠左排列,且除最后一层,其他层节点个数都达到最大
为啥就把最后一层的叶子节点靠左排列的叫完全二叉树?靠右排列为啥就不行?
要搞清楚完全二叉树为啥这么定义,先学习
如何存储二叉树?
=======================================================================
基于指针或者引用的二叉链式存储法
![](https://www.www.zyiz.net/i/ll/?i=90ea1a6eb0c74b92951a0c1312c1f2b5.png?x-oss-proc
《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》
【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享
ess=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBASmF2YUVkZ2Uu,size_12,color_FFFFFF,t_70,g_se,x_16)
每个节点有三个字段:
-
一个存储数据
-
另两个指向左右子节点的指针
大部分二叉树代码都是通过这种结构实现的。
基于数组的顺序存储法
若节点X存储在数组中下标为i的位置
2 * i
存储左子节点
2 * i + 1
存储右子节点
i/2
存储其父节点
由于这是个完全二叉树,所以仅“浪费”了一个下标0的存储位置。若是非完全二叉树,就会浪费较多存储空间:
所以完全二叉树用数组存储最省内存,就不像链式存储法,还要存储左、右子节点的指针。所以完全二叉树要求最后一层的子节点都靠左。
堆也是一种完全二叉树,所以其最常用的存储方式就是数组。
二叉树的遍历
=====================================================================
经典遍历
- 前序遍历
对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
- 中序遍历
对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树。
- 后序遍历
对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。
这些都是递归过程。
递归代码的关键就是递推公式,递推公式的关键就是,如果要解决问题A,就假设子问题B、C已经解决,然后再来看如何利用B、C来解决A。
所以可以写出前、中、后序遍历的
递推公式
前序遍历
preOrder® = print r->preOrder(r->left)->preOrder(r->right)
中序遍历
inOrder® = inOrder(r->left)->print r->inOrder(r->right)
后序遍历
postOrder® = postOrder(r->left)->postOrder(r->right)->print r
void preOrder(Node* root) {
这篇关于《重学数据结构》之什么是二叉树,2021最新Java面试题目的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)