二叉树是树的一种，它的每个节点最多只有2个叶子结点，并且左右节点次序不能对调。二叉树的5个特性如下。
（1）在二叉树的第i层上至多有2i-1个节点（i≥1）。
（2）深度为k的二叉树上至多含2k-1个节点（k≥1）。
（3）对任何一棵二叉树，若它含有n0个叶子结点、n1个度为2的节点，则必存在关系式：n0=n1+1。
（4）具有n个结点的完全二叉树的深度为log2n+1。
（5）如果对一棵有n个节点的完全二叉树的节点按层序编号，则对任一节点i（1≤i≤n）有如下规律。
① 若i=1，则节点i是二叉树的根；若i>1，则双亲是节点i/2。
② 若2i>n，则节点i无左孩子；否则，左孩子是节点2i。
③ 若2i+1>n，则节点i无右孩子；否则，右孩子是节点2i+1。
二叉树有三种遍历方式：先根遍历法，中根遍历法，后根遍历法。二叉树遍历是笔试中的常见考题。
先根遍历法步骤如下。
（1）访问根节点。
（2）先序遍历左子树。
（3）先序遍历右子树。
中根遍历法步骤如下。
（1）中序遍历左子树。
（2）访问根节点。
（3）中序遍历右子树。
后根遍历法步骤如下。
（1）后序遍历左子树。
（2）后序遍历右子树。
（3）访问根节点。
试题1．写出如图2.9所示搜索树的先根、中根、后根遍历结果。
图2.9 搜索树（2）
先根遍历结果：ABDCEFGHK。
中根遍历结果：BDCAEHGKF。
后根遍历结果：DCBAHKGFEA。
试题2．根据先根遍历结果ABDCEFGHK、中根遍历结果BDCAEHGKF，写出后根遍历结果。
分析如下。
（1）根据先根遍历结果可以找出整个树的根节点是A。
（2）从中根遍历结果得到A左边的BDC是左子树，EHGKF是右子树。
（3）BDC作为左子树先序，说明B是子树的根，又由于中序BDC，说明DC是在B的右子树上。
（4）的先根遍历结果和中根遍历结果都一样，说明根为D，C是D的右子树。
（5）再回到A的右子树EHGKF几个节点，先根遍历结果为E，子树根为E。
（6）中根遍历结果为EHGKF，说明HGKF在E的右子树。
（7）HGKF的先根遍历结果为FGHK，则F为根节点；中根遍历结果HGKF，则HGK为F的左子树。
（8）HGK的先根遍历结果为GHK，则G为根节点；中根遍历结果HGK，则H为左子树，K为右子树。这样把树形结构还原之后，就可以很容易得出后根遍历结果排列为DCBAHKGFEA。
满二叉树：一棵深度为k，且有2k-1个节点的二叉树，每一层上的结点数都是最大结点数。
完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+1。
图遍历又称图的遍历，指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。
图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。
深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依此类推。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下。
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组 Status (*VisitFunc)(int v); //VisitFunc（）是访问函数，对图的每个顶点调用该函数 void DFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit; for(v=0; v<G.vexnum; ++v) visited[v] = FALSE; //访问标志数组初始化 for(v=0; v<G.vexnum; ++v) if(!visited[v]) DFS(G, v); //对尚未访问的顶点调用DFS（函数） } void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G visited[v]=TRUE; VisitFunc(v); //访问第v个顶点 for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w)) //FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0） //若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点 //若w是v的最后一个邻接点，则返回空（0） if(!visited[w]) DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS（函数） } |
版权声明：51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可，不得对本文内容复制、转载或进行镜像，否则将追究法律责任。
