---
title: "二叉树的遍历（层遍历和深度遍历）"
author: "mywebcode"
date: "2013-10-31T11:33:00Z"
tags: []
slug: "untitled"
draft: false
lastmod: "2014-04-19T16:34:46Z"
id: 2049294
url: "https://mywebcode.iteye.com/blog/2049294"
---

定义：

1、满二叉树：一棵深度为k且有2的k次方减1个结点的二叉树称为满二叉树

2、完全二叉树：如果有深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

性质：

1、二叉树的第i层上至多有2的i-1次方个结点(i&gt;=1)。  
2、深度为k的二叉树至多有2的k次方减1个结点(k&gt;=1)。  
3、对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。  
4、具有n个结点的完全二叉树的深度为以2为底n的对数取下限加1。  
5、如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1=&lt;i=&lt;n)有：  
(1)如果i=1,则结点i是二叉树的根,无双亲;如果i&gt;1,则双亲PARENT(i)是结点\[i/2]  
(2)如果2i&gt;n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i  
(3)如果2i+1&gt;n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1.

存储结构：顺序存储结构（数组方式），链式存储结构（二叉链表）

&lt;wbr&gt;&lt;/wbr&gt;

二叉树链表存储方式：

struct BiNode

{

&lt;wbr&gt;&lt;wbr&gt; Type&lt;wbr&gt; data;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;

&lt;wbr&gt;&lt;wbr&gt; struct BiNode \*lchild,\*rchild;//左右孩子指针&lt;br&gt; }BiNode,\*BiTree&lt;/wbr&gt;&lt;/wbr&gt;

&lt;wbr&gt;&lt;/wbr&gt;

设计一个算法层序遍历二叉树（同一层从左到右访问）。

思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。  
void&lt;wbr&gt;HierarchyBiTree(BiTree Root)&lt;/wbr&gt;

{  
&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; LinkQueue \*Q;&lt;wbr&gt;// 保存当前节点的左右孩子的队列&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; InitQueue(Q);&lt;wbr&gt;// 初始化队列&lt;br&gt;&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; if (Root == NULL) return ; //树为空则返回&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; BiNode \*p = Root;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;// 临时保存树根Root到指针p中&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; Visit(p-&gt;data);&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;// 访问根节点&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; if (p-&gt;lchild)&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;

&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; EnQueue(Q, p-&gt;lchild);&lt;wbr&gt;&lt;wbr&gt;// 若存在左孩子，左孩子进队列&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; if (p-&gt;rchild)&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;

&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;EnQueue(Q, p-&gt;rchild); // 若存在右孩子，右孩子进队列&lt;br&gt;&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; while (!QueueEmpty(Q)) // 若队列不空，则层序遍历&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;

&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;{&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;

&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; DeQueue(Q, p);&lt;wbr&gt;// 出队列&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; Visit(p-&gt;data);// 访问当前节点&lt;br&gt;&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; if (p-&gt;lchild)&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;

&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; EnQueue(Q, p-&gt;lchild);&lt;wbr&gt;// 若存在左孩子，左孩子进队列&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; if (p-&gt;rchild)&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;

&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; EnQueue(Q, p-&gt;rchild); // 若存在右孩子，右孩子进队列&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; }&lt;br&gt;&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; DestroyQueue(Q);&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;// 释放队列空间&lt;br&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt;&lt;wbr&gt; return ;&lt;br&gt; }&lt;br&gt;&lt;br&gt; 算法分析：假设T有n个节点。因为本算法中基本操作是Visit(p-&gt;data)，则时间复杂度为O(n)；由于用一个队列保存当前孩子的节点，所以队列占用的额外空间为该二叉树的叶子节点数，最好情况是一棵只有左分支或只有右分支的单边树，此时占用空间最少，仅为1。最坏情况是该树是满二叉树，此时占用的空间最多为（n+1）/2。&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;&lt;/wbr&gt;

**深度遍历**是软件开发中经常遇到的遍历方法。常用的遍历方法主要有下面三种：（1）前序遍历；（2）中序遍历；（3）后序遍历。按照递归的方法，这三种遍历的方法其实都不困难，前序遍历就是根-左-右，中序遍历就是左-根-右，后续遍历就是左-右-根。代码实现起来也不复杂。

***1）前序遍历***

```
void preorder_traverse(TREE_NODE* pTreeNode)
{
	if(pTreeNode){
		printf("%d", pTreeNode->data);
		preorder_traverse(pTreeNode->left);
		preorder_traverse(pTreeNode->right);
	}
}
```

***2）中序遍历***

```
void inorder_traverse(TREE_NODE* pTreeNode)
{
	if(pTreeNode){
		inorder_traverse(pTreeNode->left);
		printf("%d", pTreeNode->data);
		inorder_traverse(pTreeNode->right);
	}
}
```

***3）后序遍历***

1. voidafterorder\_traverse(TREE\_NODE\*pTreeNode)
2. {
3. if(pTreeNode){
4. afterorder\_traverse(pTreeNode-&gt;left);
5. afterorder\_traverse(pTreeNode-&gt;right);
6. printf("%d",pTreeNode-&gt;data);
7. }
8. }

\----------------------------------------------------------------------------------------------------------------------

***//计算结点的总个数***  
int nodeTotal(binTree \*rootNode)  
{  
if(rootNode==NULL)return 0;  
else  
{  
return 1+nodeTotal(rootNode-&gt;lNode)+nodeTotal(rootNode-&gt;rNode);  
}  
}  
***//计算二叉树的深度***  
int treeDepth(binTree \*rootNode)  
{  
if(rootNode==NULL)return -1;  
else  
{  
int lH=treeDepth(rootNode-&gt;lNode);  
int rH=treeDepth(rootNode-&gt;rNode);  
if(lH&gt;rH)return lH+1;  
return rH+1;  
}  
}  
***//计算叶子结点的个数***  
int leafTotal(binTree \*rootNode)  
{  
if(rootNode==NULL)return 0;  
else  
{  
if(rootNode-&gt;lNode==NULL && rootNode-&gt;rNode==NULL)return 1;  
else  
{  
int lH=leafTotal(rootNode-&gt;lNode);  
int rH=leafTotal(rootNode-&gt;rNode);  
return rH+lH;  
}  
}  
}