数据结构 -- 二叉树

目录

1、二叉树概念及结构

1.1、概念

1.2、特殊的二叉树

1.3、二叉树的性质

1.4、二叉树的存储结构

1.4.1、顺序存储 -- 看截图：二叉树的顺序存储

1.4.2、链式存储 -- 非完全二叉树用这种方式存储

2、二叉树的遍历

2.1、前序、中序以及后序遍历2.2、层序遍历

---

1、二叉树概念及结构

1.1、概念

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

1. 为空
2. 只有一个根节点
3. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

二叉树的概念：

        

从图中可看出：

1. 二叉树不存在度大于2的结点 -- 二叉树不一定度为2(可能是空树，或者只有一个孩子)，但度为2的树可以认为是二叉树
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

二叉树的几种形式：

补充：普通二叉树的增删查改没有价值！！
原因：用二叉树这么复杂的结构来存储数据，太麻烦，不如用链表、数组...

补充：任何一颗二叉树都要拆解成三部分来看
1.根
2.左子树
3.右子树

1.2、特殊的二叉树

1.满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1(等比数列之和，公比为2)，则它就是满二叉树。-- 就是每一层都是满的。
2.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。-- 就是前K-1层都是满的，最后一层不一定满(但至少有一个)，但是从左到右必须连续。
注：完全二叉树的结点数：2^(k-1) ~ 2^k-1。

注意：满二叉树是一种特殊的完全二叉树。

1.3、二叉树的性质

1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
2.若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1(就是满二叉树的结点个数)。
3.对任何一棵二叉树，如果度为0的节点(叶结点)个数为n0，度为2的分支结点个数为n2，则一定有n0＝n2＋1。(举几个栗子，就能找到规律了)
4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)。 
5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

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

6.对于完全二叉树来说，度为1的结点个数只有 1 个或 0 个。
7.如果一颗完全二叉树的结点个数为奇数，说明度为 1 的结点个数为 0。
                            为偶数，说明度为 1 的结点个数为 1。
 

1.4、二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1.4.1、顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

补充：

父子结点间的下标有一个规律关系：
leftchild = parent*2+1
rightchild = parent*2+2
parent = (child-1)/2 // 无所谓是左孩子还是右孩子都行

1.4.2、链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链(红黑树、AVL树)。

2、二叉树的遍历

2.1、前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。
所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。
访问结点所做的操作依赖于具体的应用问题。
遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 -- 根左右
2.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。 -- 左根右
3.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 -- 左右根
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。
NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

2.2、层序遍历

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

补充：深度优先遍历和广度优先遍历
深度优先遍历：前序遍历的本质就是一种深度优先遍历(dfs--Depth First Search)
注：中序遍历和后序遍历也算是不太正规的深度优先遍历
广度优先遍历：层序遍历的本质就是一种广度优先遍历(bfs--Breadth First Search)
ex：扫雷的展开就可以使用这两种遍历来实现(就是点一下直接打开一堆的效果)