二叉树及其遍历
二叉树概念定义
什么是二叉树
二叉树特点是每个节点最多只能有两棵子树，且有左右之分的树。
注：关于数据结构——树的一些基本概念可以参考《树的概念及基本术语》 - CairBin's Blog
二叉树的基本性质
关于二叉树的基本性质前面已经写的很详细了，可以回顾文章《二叉树》 - CairBin's Blog
二叉树结构体定义
- 结构体定义及其构造函数
//链式二叉树结构体定义
typedef struct _BinTree
{
int data; //存放数据
struct _BinTree* lc; //左儿子
struct _BinTree* rc; //右儿子
//构造函数
_BinTree(int d, struct _BinTree* l = NULL, struct _BinTree* r = NULL) :data(d), lc(l), rc(r) {};
}Node;
- 析构函数
//析构函数
void destroyBinTree(Node* node)
{
//如果不存在该节点说明已经到该路径底部,则返回
if (node == NULL)
return;
//如果没到达该路径尽头则删除路上节点并继续向下走
//保存指向子节点的指针
Node* pl = node->lc;
Node* pr = node->rc;
delete node; //删除当前节点
node = NULL; //指针置为空，防止野指针
//递归,向下走
destroyBinTree(pl);
destroyBinTree(pr);
}
- 创建二叉树并写入数据
//创建二叉树结构并写入数据
//代码参考https://blog.csdn.net/u013575812/article/details/50129435
void buildBinTree(Node** node)
{
int data;
cin >> data;
if (data == -1)
*node = NULL;
else {
*node = (Node*)malloc(sizeof(Node));
(*node)->data = data;
buildBinTree(&(*node)->lc);
buildBinTree(&(*node)->rc);
}
}
二叉树的遍历
宽度优先遍历（BFS）
层序遍历
图解分析
二叉树遍历
二叉树宽度优先遍历就是要一层一层去遍历，故对于二叉树又叫层序遍历。
以上图举例，BFS遍历顺序为EBCADFICH
注：
我们用队列实现搜索过程，关于队列的知识可以看文章《队列》 - CairBin's Blog
此处为了方便，就不手动写队列(queue)了，直接使用C++ STL模板里的Queue
代码
下面给出代码：
//BFS、层序遍历
void levelOrder(Node* node, queue<Node*>& que)
{
if (!node) return;
Node* p = node;
que.push(p);
while (!que.empty())
{
p = que.front(); //p设为队列头部元素
que.pop(); //队列尾部元素出队
cout << p->data << endl;
if (p->lc) que.push(p->lc);
if (p->rc) que.push(p->rc);
}
}
深度优先遍历(DFS)
按深度搜索的顺序访问二叉树，对根（父）节点、左儿子、右儿子进行组合，有三种访问顺序
- 先序遍历
- 中序遍历
- 后序遍历
这些遍历组合有如下性质
- 中序+先序——可确定该树
- 中序+后序——可确定该树
- 先序+后续，且不知道中序——不可确定该树
这些遍历又分别有两种方法：
- 递归方法
- 非递归方法
对于非递归方法需要用到数据结构——栈（stack），关于栈的知识可以参考文章
这里同样用STL模板里的Stack
先序遍历
图解分析
二叉树遍历
我们依旧用该图
- 先序遍历顺序：父节点、左儿子、右儿子
- 本图访问顺序为：EBADCGFIH
代码
- 递归方法
//先序遍历，递归
void preOrder_A(Node* node)
{
if (node == NULL)
return;
cout << node->data << endl;
preOrder_A(node->lc);
preOrder_A(node->rc);
}
- 非递归方法
//先序遍历，非递归
void preOrder_B(Node* node, stack<Node*> &st)
{
if (!node)
return;
Node* p = node;
while (p || !st.empty())
{
//从根节点一直往左入栈
while (p)
{
st.push(p);
cout << p->data << endl;
p = p->lc;
}
//访问栈，从左节点获得右边节点数据
if (!st.empty())
{
p = st.top();
st.pop();
p = p->rc;
}
}
}
中序遍历
图解分析
二叉树遍历
- 中序遍历顺序：左儿子、父节点、右儿子
- 本图遍历顺序：ABCDEFG
- 上述顺序正好为字典顺序，这并不是巧合，这是因为此图是个二叉搜索树，在进行中序遍历时实现了排序功能
- 中序遍历特征：已知根节点，从中序遍历结果来看，排在根节点左边的都在左子树上，排在根节点右边的都在右子树上。例如E是根节点，ABCD都在左子树
代码
- 递归方法
//中序遍历，递归
void inOrder_A(Node* node)
{
if (!node)
return;
inOrder_A(node->lc);
cout << node->data << endl;
inOrder_A(node->rc);
}
- 非递归方法
//中序遍历，非递归
void inOrder_B(Node* node, stack<Node*>& st)
{
if (!node) return;
Node* p = node;
while (p || !st.empty())
{
//左边一直入栈
while (p)
{
st.push(p);
p = p->lc;
}
//从最左下儿子开始向右访问
if (!st.empty())
{
p = st.top();
cout << p->data << endl;
st.pop();
p = p->rc;
}
}
}
后序遍历
图解分析
二叉树遍历
- 后序遍历顺序： 左儿子、右儿子、父节点
- 图中顺序：ACDBFHIGE
- 后续遍历最后一个节点是根节点
代码
- 递归方法
//后序遍历，递归
void postOrder_A(Node* node)
{
if (!node) return;
postOrder_A(node->lc);
postOrder_A(node->rc);
cout << node->data << endl;
}
- 非递归方法
//后序遍历，非递归
void postOrder_B(Node* node)
{
if (!node) return;
stack<Node*> s; // 保证前序遍历
stack<Node*> t; // 反向输出左右根
Node* p = node;
while (p || !s.empty())
{
while (p)
{
s.push(p);
t.push(p);
p = p->lc;
}
if (!s.empty())
{
p = s.top();
s.pop();
p = p->lc;
}
}
while (!t.empty())
{
cout << t.top()->data << endl;
t.pop();
}
}
