树

基本术语

结点
结点的度：拥有子树的个数
叶子结点：度为0
分支结点：度不为0
孩子，双亲和兄弟
结点的层数
树的深度
树的度：表示树中各结点度的最大值
有序树和无序树：各子树从左到右是有次序的
森林：表示m颗互不相交的树的集合

二叉树

定义

度不大于2，而且是一种有序树

满二叉树和完全二叉树

满二叉树：深度为h且含有2^h-1个结点的二叉树
完全二叉树：

性质

一颗非空二叉树的第i层上最多有2^(i-1)个结点
一颗深度为h的二叉树最多具有2^h-1个结点
对于一颗非空二叉树，若其具有N0个叶子结点，有N2个度为2的结点，则有N0=N2+1
具有n个结点的完全二叉树的深度为【log2^n】+1