面试专题2-二叉树，轻松搞定面试中的二叉树有关问题

面试专题2-------------二叉树，轻松搞定面试中的二叉树问题

在面试中我们经常碰到二叉树的题目以及相关的题目，本文是本人对于面试中二叉树相关题目的一个总结。

二叉树的数据结构：包含数据以及左右孩子节点.

struct binary_tree_node
{
	int data;
	binary_tree_node* left_child;
	binary_tree_node* right_child;
};

关于二叉树的的创建请看我另外一篇博文：使用数组的方法建立一颗二叉树
在面试中我们经常碰到的相关的题目有：

1.三种遍历二叉树的方式

2.顶部开始逐层打印二叉树结点就是按层次输出二叉树

3.三种非递归版本遍历二叉树

4.二叉树节点的个数

1.三种遍历二叉树的方式：

前序：root 、 left、 right

中序：left 、root、right

后序：left、right、root

//Preorder traversing binary tree
void preoder_traverse(binary_tree_node *root)
{
	if (root == NULL)
		return;
	else
	{
		cout << root->data << " ";
		preoder_traverse(root->left_child);
		preoder_traverse(root->right_child);
	}
}

//inorder traversal
void inorder_traverse(binary_tree_node *root)
{
	if (root == NULL)
		return;
	else
	{
		inorder_traverse(root->left_child);
		cout << root->data << " ";
		inorder_traverse(root->right_child);
	}
}

//postorder traversal
void postorder_traverse(binary_tree_node *root)
{
	if (root == NULL)
		return;
	else
	{
		postorder_traverse(root->left_child);
		postorder_traverse(root->right_child);
		cout << root->data << " ";
	}
}

2.顶部开始逐层打印二叉树结点就是按层次输出二叉树

//-------------------------------------------------------------------------
//顶部开始逐层打印二叉树结点
void level_print(binary_tree_node*root)
{
	if (root == NULL)
		return;
	queue<binary_tree_node*> q;
	q.push(root);
	while (!q.empty())
	{
		binary_tree_node*temp = q.front();
		cout << temp->data << " ";
		if (temp->left_child != NULL)
			q.push(temp->left_child);
		if (temp->right_child != NULL)
			q.push(temp->right_child);
		q.pop();
	}
}

3.三种非递归版本遍历二叉树

<pre name="code" class="cpp">//------------------------------------------------------------------------------------
//非递归前序遍历
void preOrder_tree(binary_tree_node *root)     //非递归前序遍历 
{
	stack<binary_tree_node*> s;
	binary_tree_node *p = root;
	while (p != NULL || !s.empty())
	{
		if (p != NULL)
		{
			cout << p->data << " ";
			s.push(p);
			p = p->left_child;
		}
		else
		{
			p = s.top();
			s.pop();
			p = p->right_child;
		}
	}
}

//中根遍历，使用stack实现
void inorder_tree(binary_tree_node*root)
{
	if (root == NULL)
		return;
	stack<binary_tree_node*> s;
	binary_tree_node* temp = root;

	while (NULL != temp || !s.empty())
	{
		if (NULL != temp)
		{
			s.push(temp);
			temp = temp->left_child;
		}
		else
		{
			temp = s.top();
			s.pop();
			cout << temp->data << " ";
			temp = temp->right_child;
		}
	}
}

//非递归后序遍历
//要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
//如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，
//但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，
//则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子
//前面被访问，左孩子和右孩子都在根结点前面被访问。
void postOrder_tree(binary_tree_node *root)     //非递归后序遍历
{
	stack<binary_tree_node*> s;
	binary_tree_node *cur;                      //当前结点 
	binary_tree_node *pre = NULL;              //前一次访问的结点 
	s.push(root);
	while (!s.empty())
	{
		cur = s.top();
		if ((cur->left_child == NULL&&cur->right_child == NULL) ||
			(pre != NULL && (pre == cur->left_child || pre == cur->right_child)))
		{
			cout << cur->data << " ";  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
			s.pop();
			pre = cur;
		}
		else
		{
			if (cur->right_child != NULL)
				s.push(cur->right_child);
			if (cur->left_child != NULL)
				s.push(cur->left_child);
		}
	}
}

面试专题2-二叉树，轻松搞定面试中的二叉树有关问题

相关推荐