二叉树的遍历：
二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。（二叉树的遍历方式可以很多，如果限制从左到右的方式，那么主要分为四种）
前序遍历（根左右）：
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树，即以“根左右”的顺序进行遍历。
下图中的二叉树前序遍历（假设遍历即为输出该结点数据）：
1、整棵树的根结点为A，由于前序遍历顺序为“根->左子树->右子树”，故先输出A
2、遍历左子树，其根结点为B，故输出B，此时已经得到了：AB
3、遍历左子树的左子树，其根结点为D，故输出D，此时得到：ABD
4、由于结点D没有左子树和右子树，故根结点B的左子树已经遍历完，接下来遍历其右子树
5、根结点B的右子树的根结点为E，输出E，此时得到：ABDE
6、遍历根结点E的左子树，其根结点为G，输出G，得到：ABDEG
7、遍历根结点E的右子树，其根结点为H，输出H，得到：ABDEGH
8、此时整棵子树的左子树已经遍历完成，开始遍历右子树
9、根结点A的右子树的根结点为C，故输出C，得到：ABDEGHC
10、再遍历其左子树，其根结点为F，输出F，得到：ABDEGHCF，遍历完成。
注：时刻以“根->左->右”的顺序遍历，由于根在最前，故称为前序遍历
前序遍历
中序遍历（左根右）：
若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点）， 中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。上图中的二叉树中序遍历结果为：DBGEHAFC
后序遍历（左右根）：
若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。上图中的二叉树后序遍历结果为：DGHEBFCA
层序遍历：
若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。上图中的二叉树层序遍历结果为：ABCDEFGH
二叉树的建立
二叉树的建立：
如果我们要在内存中建立左图的二叉树，为了能让每个结点确认是否有左右孩子，对它进行扩展，变成右图中的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，如“#”，称这种处理后的二叉树为原二叉树的扩展二叉树，扩展二叉树可以确定唯一的一棵二叉树。
扩展二叉树
代码
BiTree.h
#pragma once
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
//数据类型
typedef char TElemType;
typedef struct BiTNode
{
TElemType data; //结点数据
struct BiTNode* lchild, * rchild; //左右孩子指针
}BiTNode, * BiTree;
//遍历二叉树结点
void visit(TElemType e);
//创建二叉树
Status CreateBiTree(BiTree& T);
//前序遍历
void PreOrderTraverse(BiTree T);
//中序遍历
void InOrderTraverse(BiTree T);
//后序遍历
void PostOrderTraverse(BiTree T);
//使用栈进行遍历(中序)
void InOrderTraverseStack(BiTree T);
//层序遍历
void LeverOrderTraverse(BiTree T);
//复制二叉树
void Copy(BiTree T, BiTree& NewT);
//计算二叉树的深度
int Depth(BiTree T);
//计算二叉树结点总数
int NodeCount(BiTree T);
//计算二叉树叶子结点数
int LeafCount(BiTree T);
BiTree.cpp
#include "BiTree.h"
void visit(TElemType e)
{
cout << e << " ";
}
Status CreateBiTree(BiTree& T)
{
TElemType ch;
cin >> ch;
if (ch == '#')
{
T = NULL;
}
else
{
T = new BiTNode;
if (!T)
{
exit(OVERFLOW);
}
T->data = ch; //生成根节点
CreateBiTree(T->lchild); //构造左子树
CreateBiTree(T->rchild); //构造右子树
}
return OK;
}
//前序遍历
void PreOrderTraverse(BiTree T)
{
if (T == NULL)
{
return;
}
visit(T->data); //根
PreOrderTraverse(T->lchild); //左
PreOrderTraverse(T->rchild); //右
}
//中序遍历
void InOrderTraverse(BiTree T)
{
if (T == NULL)
{
return;
}
InOrderTraverse(T->lchild); //左
visit(T->data); //根
InOrderTraverse(T->rchild); //右
}
//后序遍历
void PostOrderTraverse(BiTree T)
{
if (T == NULL)
{
return;
}
PostOrderTraverse(T->lchild); //左
PostOrderTraverse(T->rchild); //右
visit(T->data); //根
}
//层序遍历
void LeverOrderTraverse(BiTree T)
{
queue<BiTNode> q;
BiTNode p;
q.push(*T);
while (!q.empty())
{
visit(q.front().data);
p = q.front(); //队头结点
q.pop(); //出队
if (p.lchild) //队头结点是否有左孩子
q.push(*(p.lchild));
if (p.rchild) //队头结点是否有右孩子
q.push(*(p.rchild));
}
}
//使用栈进行遍历(中序)
void InOrderTraverseStack(BiTree T)
{
stack<BiTNode> s;
BiTNode* p = T;
//s.push(*p);
while (p || !s.empty())
{
if (p) //如果根节点存在，则入栈
{
s.push(*p);
p = p->lchild;
}
else //如果左子树为空
{
visit(s.top().data); //弹栈，输出根节点
p = s.top().rchild; //访问右子树
s.pop();
}
}
}
//复制二叉树（先序）
void Copy(BiTree T, BiTree& NewT)
{
if (T == NULL)
{
NewT = NULL;
return;
}
else
{
NewT = new BiTNode; //创建新结点（子树）
NewT->data = T->data;
Copy(T->lchild, NewT->lchild);
Copy(T->rchild, NewT->rchild);
}
}
//计算二叉树的深度
int Depth(BiTree T)
{
int m = 0, n = 0;
if (T == NULL)
{
return 0;
}
else
{
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n)
return m + 1;
else
return n + 1;
}
}
//计算二叉树结点总数
int NodeCount(BiTree T)
{
int l = 0, r = 0;
if (T == NULL)
{
return 0;
}
else
{
l = NodeCount(T->lchild); //左子树中结点个数
r = NodeCount(T->rchild); //右子树中结点个数
return l + r + 1;
}
}
//计算二叉树叶子结点数
int LeafCount(BiTree T)
{
int l = 0, r = 0;
if (T == NULL) //空树返回0
{
return 0;
}
else
{
if (T->lchild == NULL && T->rchild == NULL)
{
return 1; //叶子结点返回1
}
else
{
l = LeafCount(T->lchild);
r = LeafCount(T->rchild);
return l + r;
}
}
}
main.cpp
#include "BiTree.h"
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
BiTree T;
CreateBiTree(T); //创建二叉树
cout << "前序遍历：";
PreOrderTraverse(T); //前序遍历
cout << endl;
cout << "中序遍历：";
InOrderTraverse(T); //中序遍历
cout << endl;
cout << "后序遍历：";
PostOrderTraverse(T); //后序遍历
cout << endl;
cout << "层序遍历：";
LeverOrderTraverse(T);
cout << endl;
cout << "非递归遍历（中序）：";
InOrderTraverseStack(T);
cout << endl;
BiTree NewT;
Copy(T, NewT); //复制二叉树T到NewT中
cout << "层序遍历：";
LeverOrderTraverse(NewT);
cout << endl;
cout << "T的深度：";
int d = Depth(T);
cout << d << endl;
cout << "T中结点个数：";
int num = NodeCount(T);
cout << num << endl;
cout << "T中叶子结点个数：";
int leafNum = LeafCount(T);
cout << leafNum << endl;
return 0;
}
网友评论