2011年计算机二级公共基础知识考点知识6

　　1.6.1树的基本概念 (P26—P28)

　　在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。

　　在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。

　　在树结构中，一个结点所拥有的后件个数称为该结点的度

　　在树中，所有结点中的最大的度称为树的度。

　　根结点在第1层。

　　树的最大层次称为树的深度。

　　1.6.2二叉树及其基本性质 (P28—P31)

　　1. 什么是二叉树

　　二叉树具有以下两个特点：

　　① 非空二叉树只有一个根结点；

　　② 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

　　2. 二叉树的基本性质

　　性质1在二叉树的第K层上，最多有2^K-1(K≥1)个结点。

　　性质2深度为m的二叉树最多有2^m-1个结点。

　　性质3在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。

　　3. 满二叉树与完全二叉树

　　(1)满二叉树

　　所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点，这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2^K-1个结点，且深度为m的满二叉树有2^m-1个结点。

　　(2)完全二叉树

　　所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边若干结点。

　　满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。

　　性质6设完全二叉树共有n个结点。从根结点开始，按层序用自然数1,2，…，n给结点进行编号，则对于编号为k(k=1,2,…,n)的结点有以下结论：

　　① 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)。

　　② 若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点。

　　③ 若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。

　　1.6.3二叉树的存储结构 (P31—P32)

　　在计算机中，二叉树通常采用链式存储结构。

　　1.6.4二叉树的遍历 (P32—P33)

　　二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。

　　1. 前序遍历(DLR)

　　2. 中序遍历(LDR)

　　3. 后序遍历(LRD)