计算机二级公共基础知识总结_2017年计算机二级公共基础知识学习教程：树与二叉树

　　（六）树与二叉树

　　1．树的基本概念

　　树是一种简单的非线性结构。在树结构中，数据元素之间有着明显的层次结构。在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。

　　在树结构中，每一个结点只有一个前件，称为父结点。如A即为结点B、C、D的父结点。

　　没有父结点的结点只有一个，称为根结点。如上图所示，结点A即为根结点。

　　每一个结点可以有多个后件，它们均称为该结点的子结点。如结点G、H、I是结点D的子结点。

　　没有后件的结点，称为叶子结点。上图中，叶子结点有：J、M、N、L、C、G、H、I。

　　在树结构中，一个结点所拥有的后件结点个数称为该结点的度。例如，结点D的度为3，结点E的度为1等，按此原则，所有叶子结点的度均为0。

　　在树中，所有结点中的度称为该树的度。上图所示的树中，所有结点中的度是3，所以该树的度为3。

　　树分层，根结点为第一层，往下依次类推。同一层结点的所有子结点均在下一层。如上图：A结点在第1层，B、C、D结点在第2层；E、F、G、H、I在第3层；J、K、L在第4层；M、N在第5层。

　　树的层次称为树的深度。上图树的深度为5。

　　在树中，某结点的一个子结点为根构成的树称作该结点的子树。叶子结点没有子树。

　　在计算机中，可以用树来表示算术表达式。原则如下：

　　（1）表达式中每一个运算符在树中对应一个结点，称为运算符结点

　　（2）运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）

　　（3）运算对象中的单变量均为叶子结点

　　树在计算机中用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域（即指针域）个数将随着树中该结点的度而定义。

　　如果在树中，每一个结点的子结点的个数不相同，因此在多重链中各结点的链域个数也不相同，会导致算法太复杂。因此，在树中，常采用定长结点来表示树中的每一个结点，即取树的度作为每个结点的链域的个数。这样，管理相对简化了，但会造成空间的浪费，因为有许多的结点存在空链域。

　　2．二叉树及其基本性质

　　1）二叉树的定义

　　二叉树的特点：

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

　　每一个结点最多只有两个子结点，且结点分左右。则一个结点最多可以有两棵子树，分别称为左子树和右子树

　　在二叉树中，每一个结点的度为2，即二叉树的度为2。在二叉树中，任何的子树也均为二叉树。

　　在二叉树中，每一个结点的子树被分为左子树和右子树。在二叉树中，允许某一个结点只有左子树或只有右子树。如果一个结点既没有左子树，也没有右子树，则该结点为叶子结点。

　　2）二叉树的性质

　　性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点。

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

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

　　性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。

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

　　（1）满二叉树

　　满二叉树的特点：

　　除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树中，每一层上的结点数都达到值，即在满二叉树上的第k层上有2k-1个结点。如下即为一棵满二叉树。

　　（2）完全二叉树

　　特点：除最后一层外，每一层上的结点数均达到值，在最后一层上只缺少右边的若干个结点。

　　即如果从根结点开始，对二叉树的结点自上而下、自左而右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应，则是完全二叉树。

　　对于完全二叉树，叶子结点只能在层次的两层中出现；对于任何一个结点，若其右分支下的子树结点的层次为p，则其分支下的子孙结点的层次为p或p+1。

　　完全二叉树具有的性质：

　　性质5：具有n个结点的完全二叉树的深度为[log2n]+1

　　性质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；否则该结点无右子结点。

　　3．二叉树的存储结构

　　二叉树的存储常采用链式存储结构。

　　存储二叉树中各元素的存储结点由两个部分组成：数据域和指针域。在二叉树中，由于每个结点可有两个子结点，则它的指针域有两个：一个用于存储该结点的左子结点的存储地址，即称为左指针域；一个用于存储指向该结点的右子结点的存储地址，称为右指针域。

　　存储结构如下：

　　即二叉树的存储结构中每一个存储结点都有两个指针域，因此，二叉树的链式存储结构也称为二叉树的链表。在二叉树在存储中，用一个头指针指向二叉树的根结点的存储地址。

　　如图所示的二叉树：

　　如果我们将该二叉树的所有结点顺序编号，顺序存放在存储空间里，则它们在内存空间中的存放方式是：

　　当然，对于满二叉树或完全二叉树而言，也可采用顺序存储的方式，但顺序存储的方式不适合其他的二叉树。

　　4．二叉树的遍历

　　二叉树的遍历即是不重复地访问二叉树的所有结点。

　　在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，二叉树的遍历又可分为三种：前序遍历、中序遍历和后序遍历。

　　1）前序遍历

　　前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。

　　操作的具体方式：

　　若二叉树为空，则结束返回。

　　否则：访问根结点前序遍历左子树前序遍历右子树

　　如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O

　　2）中序遍历

　　中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。

　　具体的操作方式：

　　若二叉树为空，则结束返回。

　　否则：中序遍历左子树访问根结点 中序遍历右子树

　　这里强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。

　　如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O

　　3）后序遍历

　　后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结点。

　　具体的操作方式：

　　若二叉树为空，则结束返回。

　　否则：前序遍历左子树前序遍历右子树访问根结点

　　如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A

本文来源：https://www.wddqw.com/gZUO.html