【初阶数据结构】树和二叉树

前言

前面我们学习了顺序表，单链表，栈和队列，它们在逻辑上都是线性结构，从这节开始来学习非线性结构——树。

数据结构专题学习：数据结构学习
C++专题学习：深入学习C++

树的概念与结构

树的概念

树是一种非线性的数据结构，它是由n(n>=0)个有限节点组成一个具有层次关系的集合。
在这里插入图片描述
一棵树如果一个节点都没有，那就叫做空树。
非空树的性质：

一棵树有且仅有一个根节点，根节点没有前驱节点，如上面的A节点。
当n > 1时（即树中不止根节点），其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

在这里插入图片描述
所以树可以看做是“根节点+n棵子树”组成，而每棵子树又可看做是“根节点+n棵子树”组成。所以树是一种递归定义的数据结构。

注意：在树形结构中，子树之间不能有交集，否则就不是树形结构，而是图，如以下两个都不是树。

树的相关概念

在这里插入图片描述

名词	解释
节点的度	一个节点含有孩子，或者是分支的个数，称为该节点的度，如上图，A节点的度为6。
叶子节点（终端节点）	度为0的节点称为叶节点；如上图的B、C、H、I等
分支节点（非终端节点）	度不为0的节点；如上图的D、E、F、G等
父节点（双亲节点）	若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图的A是B的父节点
子节点	一个节点含有的子树的根节点称为该节点的子节点；如上图的B是A的子节点
兄弟节点	具有相同父节点的子节点互称兄弟节点；如上图的B、C是兄弟节点
树的度	一棵树中，最大的节点的度称为树的度；如上图：树的度为6
节点的层次	从根开始，根为第一层，根的子节点为第二层，以此类推
树的高度（深度）	树中节点的最大层次；如上图：树的高度为4.
堂兄弟节点	双亲在同一层的节点互为堂兄弟；如上图：H、I互为堂兄弟节点
路径长度	路径上所经过边的个数
树的路径长度	从根到每个路径长度的总和
有序树	树中节点的各子树从左到右是有次序的，不能互换

树中有一个重要的性质就是：节点数 = 总度数 + 1；

树的表示

由于树是一种非线性结构，相对于线性表，存储表示起来就比较复杂了。既要保存当前结点的值，也要保存结点和结点之间的关系。实际中树有很多种表示方式，例如：双亲表示法（结点的指针指向双亲），孩子表示法（结点的指针指向孩子）、孩子双亲表示法（二者混合）以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
	struct Node* fristChild1;    //指向第一个孩子节点
	struct Node* pNextBrother;   //指向下一个兄弟节点
	DataType data;               //存放节点中的数据域
};

在这里插入图片描述

二叉树的概念及结构

二叉树的概念

二叉树是n（n≥0）个节点的有限集合：
①若为空二叉树，则n=0。
②若为非空二叉树，则由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。（左，右子树也可以是空二叉树）
在这里插入图片描述

二叉树的特点：
①每个节点至多有两棵子树。
②左右子树不能颠倒，因为二叉树是有序树。

下面是二叉树的五种形态：
在这里插入图片描述

几种特殊的二叉树

1.满二叉树

满二叉树：一棵高度为h，且含有2^h - 1个结点的二叉树。也就是它的每一层的节点数都达到了最大值。

满二叉树的特点：

只有最后一层有叶子节点
不存在度为1的节点
按层序从1开始编号，节点i的左孩子为2i，有孩子为2i+1；节点i的父节点为i/2（默认i/2为计算机中直接取整，如：7/2 == 3）。

2.完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树。

完全二叉树的特点：

只有最后两层可能有叶子节点
最多只有1个度为1的节点
如果i≤n/2为分支节点，i大于n/2为叶子节点。

在这里插入图片描述

二叉树的性质

设非空二叉树中度为0、1和2的节点个数分别为n0、n1和n2。则n0=n2+1。
非空二叉树中，规定根节点为第一层，则第i层最多有2^i-1个节点。
非空二叉树中，规定根节点为第一层，高度为h的二叉树最多有2^h-1个节点。
非空二叉树中，规定根节点为第一层，具有n个结点的满二叉树的深度h=log₂(n+1)。

二叉树的存储结构

二叉树的存储结构可以分为顺序存储和链式存储。

1、顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为如果不是完全二叉树就会有空间的浪费。而现实中只有堆会用数组来存储（堆也是一种特殊的完全二叉树）。二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。
在这里插入图片描述
定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个节点。

2、链式存储

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来表示元素的逻辑关系。通常的方法是链表中的每个节点由三个域组成，为数据域和左右指针域。左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址。链式结构又分为二叉链和三叉链，目前我们使用二叉链。
在这里插入图片描述
链式存储的表示如下：

typedef int BTDataType;
//二叉链
struct BinaryTreeNode
{
	struct BinaryTreeNode* left;   //指向当前节点的左孩子
	struct BinaryTreeNode* right;  //指向当前节点的右孩子
	BTDataType data;               //当前节点的值
}

//三叉链
struct BinaryTreeNode
{
	struct BinaryTreeNode* parent;   //指向当前节点的双亲
	struct BinaryTreeNode* left;   //指向当前节点的左孩子
	struct BinaryTreeNode* right;  //指向当前节点的右孩子
	BTDataType data;               //当前节点的值
}