树与二叉树的那点事(一)
什么是树？
树是n个节点的有限集合。当n==0时为空树，n>0时为非空树；
-
树只有一个根节点 -
除了根结点的其他所有节点又是一个新树，称为根节点的子树。
树的根节点为第一层，根节点的孩子为第二层，以此类推。（示例图共四层）
树的度，即子节点的个数；（如图中A节点的度为：2，D的度为：3，G的度为0）
度数为0的节点；（如：G，H，I，J，F）
二叉树？？
-
在二叉树的第i层至多含有2^(n-1)个节点 -
深度为k的二叉树最多含有(2^k)-1个节点 -
对于任意一个二叉树，度为0的节点个数=度为2节点个数+1
-
深度为k，且含有(2^k)-1个节点的二叉树成为满二叉树； -
每一层节点数都为最大节点数
-
叶子节点只能在层次最大的两成出现 -
具有n个节点的完全二叉树深度为：⌊log₂n⌋+1 -
对于一个含有n个节点的完全二叉树，对于任意一个节点i: -
如果 i=1，则i节点为根节点 -
如果 i>1，则i节点的双亲节点为⌊i/2⌋ -
如果 2i>n，则i节点为叶子节点（无子节点）,否则，i节点的左孩子节点为2i -
如果2i+1>n，则i节点无右子节点，否则，右子节点为2i+1