C语言中关于树和二叉树的相关概念

时间:2023-03-20 [Pokemon]大猫猫人气:0

树是一种非线性的数据结构，由 n(n >= 0) 个有限节点组成一种具有层次关系的集合

一、树

树的结构可以递归定义为：

根节点除根节点之外，其余节点被分成 M(M >= 0) 个互不相交的集合，每个集合分别是一棵子数

0 个结点的树就称为空树

森林：由 M(M > 0) 棵互不相交的树构成的集合，将上图中 A 节点去掉后，便构成由以 B、C、D 为根节点的三颗树构成的森林

在树的结构中可以发现，树是不易于用数组来存储的，因此采用链式的方式来存储树

结构1:

由于树的结构中每个节点的孩子个数是不确定的，因此每个节点需要使用一个顺序表存储孩子的指针

typedef int TreeDataType;
typedef struct TreeNode
{
	TreeDataType data;
	SeqList childs;	//顺序表，并且每个元素的类型是 struct TreeNode*
}TreeNode;

结构2：

孩子兄弟表示法：节点的第一个孩子用该节点中的孩子指针指向，第二个孩子用该结点的第一个孩子结点的兄弟指针指向，第三个孩子用该节点的第二个孩子结点的兄弟指针指向…

typedef int TreeDataType;
typedef struct TreeNode
{
	TreeDataType data;
	struct TreeNode* child;
	struct TreeNode* brother;
}TreeNode;

存储树的方法还有双亲表示法，孩子表示法、孩子双亲表示法等，感兴趣的读者可以自行查阅

树中所有结点的度都小于等于 2 的树，即树的度小于等于 2 的树，称为二叉树

在二叉数中子树有左右区分，次序不能颠倒，左边的称为左子树，右边的称为右子树

二叉树的递归定义为：

左子树和右子树可以为空树，这里的子树也是一颗二叉树

假定根节点的层数为 1

假设一颗二叉树有 n 个节点，度为 0 的节点数为 n0，度为 1 的节点数为 n1，度为 2 的节点数为 n2，根据 n 个节点的二叉树有 n - 1 条边，可得到如下关系：

解得：n0 = n2 + 1

满二叉树：如果二叉树中每一个层的节点数都达到最大值，则这棵二叉树称为满二叉树

假设一棵二叉树的层数为 K，且节点总数是 2^K - 1，则它就是满二叉树

完全二叉树：假设一颗二叉树有 K 层，如果这颗二叉数的前 K - 1 层是满二叉树，并且第 K 层是从左往右还是连续的节点，则这棵二叉树称为完全二叉树

假设一棵完全二叉树的层数为 K ，则完全二叉树节点数的范围：2^(K - 1) ~ 2^K - 1

完全二叉树中度为 1 的节点有 0 个或 1 个

满二叉树可以认为是一种特殊的完全二叉树

由于完全二叉树中从第二层开始，每一层的结点都是偶数个，因此左孩子的编号都均为奇数，右孩子的编号都均为偶数

在 n 个节点的完全二叉树中，对于合法的编号为 i 的节点有：

加载全部内容