二叉树的遍历问题

目录

一、二叉树

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) 从栈中d出一个结点cur

(3) 打印cur

(4) 先压右结点，再压左结点(如果有)

(5) 重复 (2) --- (4) 直到栈为空

代码如下:

//先序非递归
void prenorecursion(BinaryNode* headnode)
{
	printf("先序遍历:");
	if (headnode)
	{
		stack s;
		s.push(headnode);
		while (s.size())
		{
			//1、d出栈顶元素
			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);
			}
		}
	}
}

②非递归中序遍历

中序非递归遍历的思想就是先把左边的结点全部压入到栈，直到为空，然后开始d出结点并打印，d出的时候将右边的结点也压入栈，重复上述步骤。

代码如下：

//中序非递归
void midnorecursion(BinaryNode* headnode)
{
	printf("中序遍历:");
	if (headnode)
	{
		stack s;
		while (s.size() || headnode)
		{
			//只要左结点不为空，一直压入栈中
			if (headnode)
			{
				s.push(headnode);
				headnode = headnode->m_LeftNode;
			}
			//左边压完了，d出结点的同时检查右边是否有结点，如果有，将右边结点压入并重复检测有无左结点
			else
			{
				headnode = s.top();
				printf("%d ", headnode->m_Val);
				s.pop();
				headnode = headnode->m_RightNode;
			}
		}
	}
}

③非递归后序遍历

步骤：

(1) 先压入头结点

(2) d出cur，将cur压入收集栈

(3) 先压左结点，再压右结点(如果有)

(4) 重复(2) --- (4) 直到栈为空

(5) 依次d出收集栈元素并打印

 代码如下:

//后序非递归
void afternorecursion(BinaryNode* headnode)
{
	printf("后序遍历:");
	if (headnode)
	{
		stack s;//容器栈
		stack collectstack;//收集栈
		//1、压入头结点
		s.push(headnode);
		while (s.size())
		{
			//2、d出栈顶元素，并压入收集栈
			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、当栈中元素为空，依次d出收集栈中元素并打印
		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 q;
	//1、先放头节点
	q.push(headnode);
	while (q.size())
	{
		//2、d出结点并打印
		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);
		}
	}
}