数据结构专升本学习，二叉树篇
前言
上一篇文章博主简单讲解了树逻辑结构，今天我们来学习树结构里面比较特殊的树状结构因为它比较简单,二叉树是树形结构的一个重要类型，二叉树虽然是树，但是二叉树和树是有区别的，二叉树的左右子树区分严格，树却没有。在许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要，嘿嘿，让我们开始学习吧哈哈哈！！！
每日一遍，防止颓废！！
1.二叉树的定义
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树，画一个图给大家分析一下二叉树的几个形态。(讲人话:就是一棵树结点最大的度2,然后不像之前的树左右没区别,二叉树是有左右区别)
使用三个结点A，B，C来展示所有形态的二叉树。
2.二叉树性质
**性质1：二叉树的第i层上至多有2^(i-1) （i≥1）个节点 **
性质1图解如下：只要知道层我们就可以知道这一层最多有多少结点
性质2：深度为h的二叉树中至多含有(2^h)-1个节点
性质2图解如下：只要知道深度我们就可以求出这棵树有多少结点.或者我们能反推知道有多少结点问我们有多少层考试经常出这样的题目.
**性质3：**若在任意一棵二叉树中，有度为零n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1
我们考试经常遇到求叶子结点个数,只要我们知道度为2的结点个数就可以求出来了,这个一般都是针对完全二叉树出题.
性质3图解如下：
完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树.
(另一种记忆方法,你可以把这棵树的满二叉树推出了,然后依次减去,直到你想要的)或者你看这个题目有没有出现突然从莫个结点跳过去的哪就不是完全二叉树了.
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树(一棵树深度为h并且满足（2^k）-1个结点我们称为满二叉树)
讲人话就是:最后一层,这一层没有缺一个结点,没少也没多结点就是满二叉树.
**性质4：**具有n个节点的完全二叉树深为(log2)x+1（(log2)表示以2为底,其中x表示不大于n的最大整数）
讲人话就是这个性质求树深,根据n个结点得到,这个x就是取最后一层最接近n的2的次方,例如n为6,最接近它的是4,2的平方,我们就可以用x=4.
性质4图解如下:
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点 当i>1时，该节点的双亲节点的编号为i/2 若2i≤n，则有编号为2i的左节点，否则没有左节点 若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点
可以根据结点来推测我们这个结点是否有左右结点,双亲结点的编号.
性质5图解如下：
3.二叉树的遍历
在二叉树的一些应用中，常常要求在树中查找具有莫种特征的结点，或者对树中全部结点进行莫种处理。这就需要用到我们的遍历了，遍历有着四种方法,分别是先序遍历,中序遍历,后序遍历,层次遍历,这四种,前三种遍历的顺序都是针对根结点的输出顺序而言的,根先输出就是先序,根在中间输出就是中序,根最后输出就是后序,那么我们有这么多种遍历找到适合我们的遍历方法吧.
先序遍历
先序遍历步骤：（1）先遍历根结点----->(2)先序遍历左子树----->(3)先序遍历右子树
中序遍历
中序遍历步骤: (1)中序遍历左子树------>(2)遍历根结点----->(3)中序遍历右子树
后序遍历
后序遍历步骤:(1)后序遍历左子树----->(2)后续遍历右子树----->(3)遍历根节点
总结:先序,中序,后序遍历===>这三个序都是针对根结点的,先序就是先遍历根,中序就是先遍历左子树再根再右子树,根在中间,后序遍历就是从左到右再到根,这三个顺序都是针对根结点而言的.
层次遍历
层次遍历就是从上到下从左到右遍历.
总结
二叉树的一些基础方面的知识我们就讲解完了,对于代码的操作需要关注博主的下一篇文章,这一篇主要是用图来教大家学会逻辑,逻辑思维是非常重要滴,二叉树的几个性质需要大家背下来,考试考的比较勤快,二叉树的遍历,先序中序后序都是针对根而言的,根最先遍历就是先序,根在中间遍历就是中序,根在最后遍历就是后序,层次遍历就是讲解从上到下,从左到右的顺序进行遍历,好了创作不易,希望大家点赞关注,评论,收藏. 上一篇：数据结构专升本学习，树篇（一张图教会你，树结点的关系，画图教你树的四种表示法（树状，文氏图标，凹入表示法，括号表示法），三种遍历（先根，后根层次遍历））