二叉树的遍历问题
目录
一、二叉树
1、二叉树结点结构
2、递归遍历
3、非递归遍历
①非递归先序遍历
②非递归中序遍历
③非递归后序遍历
4、二叉树的宽度优先遍历
①宽度优先遍历
一、二叉树
1、二叉树结点结构
struct BinaryNode
{
int val;
BinaryNode* left;
BinaryNode* right;
}2、递归遍历
①先序遍历：对每一棵树和子树都是先遍历头结点，然后再是左结点，最后是右结点。
②中序遍历：对每一棵树和子树都是先遍历左结点，然后再是头结点，最后是右结点。
③后序遍历：对每一棵树和子树都是先遍历左结点，然后再是右结点，最后是头结点。
void recursion(struct BinaryNode * root)
{
if (root == NULL)
{
return;
}
//先序遍历
printf("%d ", root->val);
recursion(root->lChild);
recursion(root->rChild);
}
void recursion(struct BinaryNode * root)
{
if (root == NULL)
{
return;
}
recursion(root->lChild);
//中序遍历
printf("%d ", root->val);
recursion(root->rChild);
}
void recursion(struct BinaryNode * root)
{
if (root == NULL)
{
return;
}
recursion(root->lChild);
recursion(root->rChild);
//后序遍历
printf("%d ", root->val);
}
总结：第一次来到结点的时候打印就是先序遍历、第二次来到结点打印就是中序遍历、第三次来到结点打印就是后续遍历
3、非递归遍历
二叉树的非递归遍历需要用到栈容器，下面会对非递归遍历进行详细介绍
①非递归先序遍历
步骤：
(1) 先压入头节点
(2) 从栈中弹出一个结点cur
(3) 打印cur
(4) 先压右结点，再压左结点(如果有)
(5) 重复 (2) --- (4) 直到栈为空
代码如下:
//先序非递归
void prenorecursion(BinaryNode* headnode)
{
printf("先序遍历:");
if (headnode)
{
stack<BinaryNode*> s;
s.push(headnode);
while (s.size())
{
//1、弹出栈顶元素
headnode = s.top();
s.pop();
//2、打印
printf("%d ", headnode->m_Val);
//3、如果有左右结点，先压入右结点，再压入左结点
if (headnode->m_RightNode)
{
s.push(headnode->m_RightNode);
}
if (headnode->m_LeftNode)
{
s.push(headnode->m_LeftNode);
}
}
}
}②非递归中序遍历
中序非递归遍历的思想就是先把左边的结点全部压入到栈，直到为空，然后开始弹出结点并打印，弹出的时候将右边的结点也压入栈，重复上述步骤。
代码如下：
//中序非递归
void midnorecursion(BinaryNode* headnode)
{
printf("中序遍历:");
if (headnode)
{
stack<BinaryNode*> s;
while (s.size() || headnode)
{
//只要左结点不为空，一直压入栈中
if (headnode)
{
s.push(headnode);
headnode = headnode->m_LeftNode;
}
//左边压完了，弹出结点的同时检查右边是否有结点，如果有，将右边结点压入并重复检测有无左结点
else
{
headnode = s.top();
printf("%d ", headnode->m_Val);
s.pop();
headnode = headnode->m_RightNode;
}
}
}
}③非递归后序遍历
步骤：
(1) 先压入头结点
(2) 弹出cur，将cur压入收集栈
(3) 先压左结点，再压右结点(如果有)
(4) 重复(2) --- (4) 直到栈为空
(5) 依次弹出收集栈元素并打印
代码如下:
//后序非递归
void afternorecursion(BinaryNode* headnode)
{
printf("后序遍历:");
if (headnode)
{
stack<BinaryNode*> s;//容器栈
stack<BinaryNode*> collectstack;//收集栈
//1、压入头结点
s.push(headnode);
while (s.size())
{
//2、弹出栈顶元素，并压入收集栈
headnode = s.top();
s.pop();
collectstack.push(headnode);
//3、将栈顶元素的左结点、右节点压入栈中(如果有的话)
if (headnode->m_LeftNode)
{
s.push(headnode->m_LeftNode);
}
if (headnode->m_RightNode)
{
s.push(headnode->m_RightNode);
}
}
//4、当栈中元素为空，依次弹出收集栈中元素并打印
while (collectstack.size())
{
headnode = collectstack.top();
printf("%d ", headnode->m_Val);
collectstack.pop();
}
}
}4、二叉树的宽度优先遍历
如何完成二叉树的宽度优先遍历（常见题目：求一颗二叉树的宽度）
①宽度优先遍历
宽度优先遍历上图中就是 1->2->3->4->5->6->7->8->9
算法思想： 使用一个队列（可以是数组或链表）来完成。初始时只有一个根节点，然后每次取出一个结点，就把它的左右儿子（如果有）放入队列。
代码如下:
void treewidth(BinaryNode* headnode)
{
queue<BinaryNode*> q;
//1、先放头节点
q.push(headnode);
while (q.size())
{
//2、弹出结点并打印
headnode = q.front();
printf("%d ", headnode->m_Val);
q.pop();
//3、放入左结点和右节点(如果有)
if (headnode->m_LeftNode)
{
q.push(headnode->m_LeftNode);
}
if (headnode->m_RightNode)
{
q.push(headnode->m_RightNode);
}
}
}