AKSZ-图论补充
2024-06-16 16:37:57
发布于:广东
图的度
度:图的顶点所链接的边数
出度:有向图的顶点指向其他顶点的边数
入度:有向图的顶点被其他顶点指向的边数
图的存储
连接矩阵/表(vector
)
使用二维数组,如果存在边<1,4>就在数组[1][4]处标1,如果存在边<4,1>就在数组[4][1]处标1,无向图就两个都标。
注:无向图的连接矩阵沿对角线对称分布
存储权值图时,将标的1换成边权即可。
二叉树性质
满n叉树相关公式
第层节点数:
层全部节点数:
-
令为度为的节点个数,则对于任意二叉树,
-
个节点的完全二叉树深度为
-
如果将一棵二叉树自顶向下,同一层从左往右连续给节点编号,则有以下关系:
1.若,则节点为根,没父节点。
2.若,则的父节点编号为
3.若,则没有左孩子,否则其左孩子编号为
4.若,则没有右孩子,否则其右孩子编号为
二叉树遍历方式
先序(先根、前序)
先访问根节点,再访问左子树,然后右子树,递归下去(根左右)
中序
先访问左子树,再访问根节点,然后右子树,递归下去(左根右)
后序
先访问左子树,再访问右子树,然后根节点,递归下去(左右根)
中序+任意一种顺序可以确定二叉树
注意:先序+后续不能确定一棵二叉树
这里空空如也
有帮助,赞一个