程序员怎能不会二叉树系列(一)简单了解二叉树

简介: 程序员怎能不会二叉树系列(一)简单了解二叉树

       本来想直接接着算法系列写选择排序的升级版堆排序的,但是写到完全二叉树这一块,我估计很多初学的朋友一脸懵圈,可能脑海中有二叉树这个东西的概念,知道是一种数据结构,但实际上是什么,却不知道,那么我们就来讲一讲二叉树。二叉树系列会后于基础算法系列更新


二叉树:

       二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树二叉堆。他的结构是这个样子的:

e9dd298a21f6d06291d6b38f6e933cef_640_wx_fmt=jpeg&wxfrom=5&wx_lazy=1&wx_co=1.jpg

       A为二叉树的根节点,B,E为A的子节点,CD为B的子节点,F为E的子节点。看起来是不是很像一颗倒着的大树啊!!每个节点分成两个枝桠,因而叫二叉树


二叉树又分为满二叉树完全二叉树平衡二叉树(AVL树)。

平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构;在本文中就不多介绍了,后续有机会我会单独开一章进行讲解。


满二叉树与完全二叉树:

一棵深度为k,且有2^k-1个结点的二叉树,称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且或者最后一层是满的,或者是在右边缺少连续若干结点,则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树,至少有2k-1个叶子结点,至多有2k-1个结点。见下图:

74e85bfabd5d5eeed15ccad7f1b7cbb2_640_wx_fmt=jpeg&wxfrom=5&wx_lazy=1&wx_co=1.jpg



可能有些初学者看到上面的介绍一脸蒙圈,那么我用通俗的话语总结一下:


满二叉树就是除了叶子节点(最底下一层)没有任何子节点之外,其他的节点每一个都需要有两个子节点。


完全二叉树就是叶子节点(最底下一层)的节点必须是从左边开始连着的,不能断掉,而且去掉最后一层,要是一颗满二叉树,两个条件缺一不可。


二叉树简单介绍就到这了,我会尽力写得让初学者能看懂,而且篇幅也不会太长,方便各位读者在碎片时间能够刷刷我的文章,下一章我们讲讲二叉树的几种遍历方式。


相关文章
【五一专栏】1. 迭代版二叉树的前、中、后序遍历
【五一专栏】1. 迭代版二叉树的前、中、后序遍历
|
存储 算法 编译器
一篇文章教会你什么是二叉搜索树(上)
二叉搜索树概念 二叉搜索树(Binary Search Tree,BST)是一种二叉树的特殊形式,它具有以下关键性质:
|
4月前
|
算法 关系型数据库 MySQL
一网打尽二叉树系列
文章全面介绍了二叉树的定义、分类和搜索(遍历)方式,包括满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树的概念,以及前序、中序、后序和非递归遍历方法,旨在帮助读者深入理解二叉树的基本概念和应用场景。
一网打尽二叉树系列
|
存储 算法 C++
婉约而深刻:二叉树的中序遍历之旅
婉约而深刻:二叉树的中序遍历之旅
65 0
|
程序员
程序员怎能不会二叉树系列(二)二叉树的四种遍历
程序员怎能不会二叉树系列(二)二叉树的四种遍历
|
前端开发 算法 API
[LeetCode算法]有了二叉树层序遍历,妈妈再也不用担心我不会做二叉树层级题了
博主最近在刷`leetcode`,做到二叉树套题的时候发现很多题的解题思路都是基于二叉树的层序遍历来完成的,因此写下这篇文章,记录一下二叉树层序遍历这件"神器"在实战的运用。
151 1
[软考]之树和二叉树
[软考]之树和二叉树
84 0
|
存储
【2020团体程序设计天梯赛】L2-3 完全二叉树的层序遍历(后序遍历转层次遍历)
【2020团体程序设计天梯赛】L2-3 完全二叉树的层序遍历(后序遍历转层次遍历)
209 1