目录
本章主要讲解:
数据结构中的树及二叉树的相关知识
树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的
有一个特殊的结点,称为根结点(根节点没有前驱结点) 其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ,其中每一个集合 Ti(1<=i<= m)又是一棵结构与树类似的子树 每棵子树的根结点有且只有一个前驱,可以有 0 个或多个后继,因此,树是递归定义 的
typedef int DataType;//数据类型
struct Node
{
struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
二叉树由一个根节点加上左子树和右子树组成: 1.二叉树度最大为2(度可以为0,1,2) 2.二叉树的子树有左右之分,次序不能颠倒(有序树)(没有左树,一定没有右树;有左树,不一定有右树)
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树 也就是说,如果一个二叉树的层数为K,且结点总数是2^k-1,则它就是满二叉树
完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的(特殊的完全二叉树) 对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树
1.若规定根节点的层数为 1 ,则一棵非空二叉树的 第 i 层上最多有2^(i-1)个结点
2.若规定根节点的层数为 1 ,则 深度为 h的二叉树的最大结点数是2^h-1
3.对任何一棵二叉树 , 设 度为 0 其叶结点个数为n0 , 度为 2 的分支结点个数为n2 , 则有n0=n2 + 1 解释: 当只有一个节点时,n0=1,n2=0(符合) 接下来每增加一度2的树,都会增加2个度0的树(画图归纳理解)(符合)
4.若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1)(是log以2为底,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 否则无右孩子
顺序存储
顺序结构存储就是使用 数组来存储 ,一般使用数组只适合表示完全二叉树(不完全二叉树有空间的浪费)而现实中使用中只有堆才会使用数组来存储
注:二叉树顺 序存储在物理上是一个数组,在逻辑上是一颗二叉树
链式存储
用链表来表示一棵二叉树,即用链来指示元素的逻辑关系 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链(红黑树等结构会用到三叉链)
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
};