二叉树
对于任意一颗二叉树,如果其叶子结点数量为n0,度为2的结点数为n2,则n0 = n2 + 1
具有n个结点的完全二叉树深度为logn + 1
满N叉树,深度为K
结点的个数 为 (n^k - 1)/ (n-1)
图的度
在无向图中,一个顶点的度数就是与该边相连的顶点的数量
有向图中:入度:指向该顶点的边的数量
出度:从该顶点出发的边的数量
完全二叉树
如果一颗完全二叉树自顶向下,同一层从左到右编号结点
1,2,... n
则
1.若i=1,则为根,无父结点
2.若i>1,则其父结点为floor(i/2)
3.若2i > n ,则i无左孩子,否则其左孩子编号为 2i
4.若2i + 1> n,则i无右孩子,否则其左孩子编号为 2i+1
图的存储
带权图的存储 : 二维数组(两点间无连边用0x3f3f 表示)
先序遍历
二叉树重建
二叉树用中序遍历+任意一种遍历方式可以确定唯一一棵二叉树。
先序+后序不行
根据后序(前序)和中序求另一遍历顺序