树与二叉树
2023-08-18 20:36:56
发布于：浙江
树与二叉树：
树：树是一种非线性的结构数据，是由n个节点组成的有限集合。
如果n==0时，称为空树，如果n>0，树有且仅有一个特定的节点——根节点。
树的度：节点拥有的子树的数量为节点的度，度为0的节点为叶子节点，度不为 0的节点为分支节点，树的度定义为树的所有节点中的最大值
树的前驱和后驱：除根节点没有前驱外，其余每个节点都有唯一的一个前驱节点。每个节点可以有0或多个后继节点。节点的直接后继称为节点的孩子，节点的直接前驱为孩子的父亲。有同一个双亲的不同节点互称兄弟。
树中节点的层次：树中根节点为第1层，根的孩子为第2层，以此类推。树中节点的最大层次称为深度或高度。注意：部分题目中根的节点为第0层
除根节点没有父节点外，其余节点有且仅有一个父节点，n个节点的数，有且仅有n-1条边，数中任意两个节点之间有且仅有一条简单路径（路径上的节点都不相同的路径）
双亲表示法：从上到下，从左到右依次给每个点编号，记录的方式可以简单表示为：tree[i] = j 表示编号为i的树节点的父亲是j。
下标： 1 2 3 4 5 6 7 8 9
父节点下标： 0 1 1 2 3 3 4 4 4
孩子表示法：即每个节点存储自己孩子的位置信息。根据结构，可以选择使用vector进行存储。
核心代码：
vector<int> tree[N];
tree[i].push_back(idx);
表示i节点是idx节点的双亲
下标 1 2 3 4
孩子下标： 2/3 4 5/6 7/8/9
二叉树：二叉树是一种度数最大为2的树形结构，即二叉树的每个节点最多有两个子节点，每个节点的子节点严格区分左节点和右节点，它的两颗子树称为左子树和右子树。
性质1：
在二叉树的第i层上最多右2的i-1次方个节点（i>=1）。
性质2：
深度为k的二叉树至多2的k次方-1个节点（k>=1）。
性质3：
任意一颗二叉树，若其叶子节子（度为1节点）的数量为n，度为2的节点数量为n2，则：与n2一定满足：n0=n2+1
性质4：
具有n个节点的完全二叉树的深度为[log2(n)]+1.[]表示下取整。
性质5：
若将一颗有n个节点的完全二叉树自上而下，同一层自左向右连续给节点编号1,2…，n，则：
- 若节点编号i=1，则节点i为根，无父节点；
- 若i>1，则i的父节点编号为i/2;
- 针对编号i的节点：
3.1其左孩子编号为2i；
3.2其右孩子编号为2i+1；
满二叉树：指某一二叉树“子孙满堂”，即除叶子节点外，其他节点的度均为2，且每一层的节点总数最大值，这种特殊的状态的二叉树，称为满二叉树（即二叉树深k层共2的k次方-1个节点）
完全二叉树：若某一二叉树深k层，除第k层外，其他层的节点总数达到最大值，即第i（i<k）层节点点数为2的i-1次方。且第k层节点点数小于等于2的k-1次方并靠左侧连续，这种特殊状态的二叉树，称为完全二叉树。
二叉树的存储：
- 顺序存储法：当二叉树节点较少，呈现完全二叉树时，以二叉树性质5为基础，用顺序数组来模拟二叉树。
核心代码：
DateType tree[N];
tree[i]是tree[2*n]和tree[2*n+1]的父节点
tree[2*n]是tree[i]的左孩子节点
tree[2*i+1]是tree[i]的右孩子节点
- 链式存储法：当二叉树节点较多，且并非具有完全二叉树时，为了避免可能在使用顺序存储时，导致的内存堆栈溢出则使用链式存储法
核心代码：
struct asd{
DataType data;
int father;
int left,right;
};
asd tree[N];
tree[i].left = idx1;
tree[i].right = idx2;
tree[idx1].father = i;
tree[idx2].father = i;
二叉树的遍历：
- 先序遍历：根，左，右的深度优先搜索；
- 中序遍历：左，根，右的深度优先搜索；
- 后序遍历：左，右，根的深度优先搜索；
这里空空如也
有帮助，赞一个