还是因为写作业，就是严蔚敏那版数据结构的作业，这次的文件结构就一个头文件 + 一个.cpp文件，拉到底能看见两个文件的完整代码。
前面就简单复习一下：
先复习一下二叉树：
二叉树，每个结点最多只能有两棵子树。那么以单个结点来看，是不是就三个元素？——“左子树、右子树、该节点的内容”。
那我们就可以定义出这样的一个二叉树结构体：
class Node
{
public:
char data;// data表示该节点代表的内容；
Node* L;//左子树
Node* R;//右子树
};
Node* T;//创个指针，指向二叉树的根节点；头文件里面就需要包含二叉树结构体，以及声明我们要实现的功能：
#include<iostream>
#pragma once
using namespace std;
Node* T;//创个指针，指向二叉树的根节点；
void creatNode(Node*& T);//创建二叉树
void preOrder(Node*& T);//前序遍历
void inOrder(Node*& T);//中序遍历
void posOrder(Node*& T);//后续遍历
void levOrder(Node*& T);//层序遍历
void deleNode(Node* T);//销毁二叉树前序遍历（递归）：
前序（先序）遍历：1.访问根节点；2.先序遍历左子树；3.先序遍历右子树
void preOrder(Node*& T)
{
if (T == NULL)
{
return;//如果该结点为空就返回;
}
else
{
cout << T->data << " "; //先输出根节点的那个数字
preOrder(T->L); //然后访问左孩子，开始递归
preOrder(T->R); //左孩子访问完成，开始右孩子递归
}
}然后是中序遍历（递归）：
1.中序遍历左子树；2.访问根节点；3.中序遍历右子树
void inOrder(Node*& T)
{
if (T == NULL)
return;
else
{
inOrder(T->L);
cout << T->data << " ";
inOrder(T->R);
}
}
后序遍历（递归）：
1.后序遍历左子树；2.后序遍历右子树；3.访问根节点
void posOrder(Node*& T)
{
if (T == NULL)
return;
else
{
posOrder(T->L);
posOrder(T->R);
cout << T->data << " ";
}
}层序遍历：
从上到下、从左到右逐层访问
这个没有用递归，用的是另一种数据结构——队列。
（我之前也写了个队列的作业，里面有关于队列的基础操作的具体函数：）C++实现数据结构—顺序队列
https://mp.csdn.net/mp_blog/creation/editor/127811895 不过写二叉树的层序遍历，为了简便，我用的是queue库里面的函数。
层序遍历我写的时候感觉如果不用队列，还怪不好写的，所以就再具体说一下 。
层序的思路是：将根节点丢进去，获得内容，然后出队；又让左子树入队，获得内容，出队；再让右子树入队，获得内容，出队……如此这样循环进行。
层序的代码思路是这样的：
1.建立一个队列，用来管理该二叉树的结点；再建一个变量T1，用来放一个二叉树结点
2.将二叉树头结点入队列
3.判断队列是否为空，若不为空则进行如下循环操作
4. 队列获取队头，赋给T1，然后出队，打印出T1的内容
5.访问T1，如果它有左子树，则将左子树的根结点入队
6.如果它有右子树，则将右子树的根结点入队
void levOrder(Node*& T)
{
queue<Node*> q;
Node* T1;
if (!T)
return;
q.push(T);
while (!q.empty()) {
T1 = q.front();
q.pop();
printf("%c ", T1->data);
if (T1->L)q.push(T1->L);
if (T1->R)q.push(T1->R);
}
}以下是二叉树的原型：
头文件的完整代码：
#include<iostream>
#pragma once
using namespace std;
class Node
{
public:
char data;// data表示该节点代表的内容；
Node* L;//左子树
Node* R;//右子树
};
Node* T;//创个指针，指向二叉树的根节点；
void creatNode(Node*& T);//创建二叉树
void preOrder(Node*& T);//前序遍历
void inOrder(Node*& T);//中序遍历
void posOrder(Node*& T);//后续遍历
void levOrder(Node*& T);//层序遍历
void deleNode(Node* T);//销毁二叉树
然后是main.cpp的完整代码：
#include<iostream>
#include"BiTree.h"
#include<queue>
using namespace std;
void creatNode(Node*& T)
{
char ch;
if ((ch = getchar()) == '#')//按照一个二叉树的前序遍历输入若子节点为空就输入 #
{
T = NULL;
}
else
{
T = new Node;
T->data = ch;
creatNode(T->L);
creatNode(T->R);
}
}
void preOrder(Node*& T)
{
if (T == NULL)
{
return;//如果该结点为空就返回;
}
else
{
cout << T->data << " "; //先输出根节点的那个数字
preOrder(T->L); //然后访问左孩子，开始递归
preOrder(T->R); //左孩子访问完成，开始右孩子递归
}
}
void inOrder(Node*& T)
{
if (T == NULL)
return;
else
{
inOrder(T->L);
cout << T->data << " ";
inOrder(T->R);
}
}
void posOrder(Node*& T)
{
if (T == NULL)
return;
else
{
posOrder(T->L);
posOrder(T->R);
cout << T->data << " ";
}
}
void levOrder(Node*& T)
{
queue<Node*> q;
Node* T1;
if (!T)
return;
q.push(T);
while (!q.empty()) {
T1 = q.front();
q.pop();
printf("%c ", T1->data);
if (T1->L)q.push(T1->L);
if (T1->R)q.push(T1->R);
}
}
void deleNode(Node* T)
{
if (T == NULL)
{
return;
}
else
{
deleNode(T->L);//后序遍历挨个删；
deleNode(T->R);
T->data = NULL;
}
}
int main()
{
cout << "输入一个二叉树(按照这个二叉树的前序遍历输入，若子节点为空就输入 # ):" << endl;
creatNode(T);
cout << "前序遍历:";
preOrder(T);
cout << endl;
cout << "中序遍历:";
inOrder(T);
cout << endl;
cout << "后序遍历:";
posOrder(T);
cout << endl;
cout << "层序遍历:";
levOrder(T);
cout << endl;
cout << "销毁二叉树";
deleNode(T);
cout << "已销毁" << endl;
return 0;
}运行结果放一下：
