树

基本术语

结点

结点的度：拥有子树的个数

叶子结点：度为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