参考教材: 《2021年王道数据结构复习指导》

$5.3$ 二叉树的遍历和线索二叉树

  • 采用$C$++$11$完成习题
  • 测试结果将写在注释部分
  • 为使代码简介，栈将调用$STL$标准栈
  • 源代码下载

$0$.预定义

# include <iostream>
# include <ctime>
# include <stack> 
using namespace std;

//二叉树节点结构体定义
struct TreeNode
{
	int val;
	TreeNode*left,*right;
	
	TreeNode()
	{
		val = 0;
		left = right = nullptr;
	}
	
	TreeNode(int _val,TreeNode* _left,TreeNode *_right)
	{
		val = _val;
		left = _left;
		right = _right;
	}
	
	TreeNode(int _val)
	{
		val = _val;
		left = right = nullptr;
	}
	
	void display()
	{
		cout<<"    address : "<<this<<endl;
		cout<<"      value : "<<val<<endl;
		cout<<" left-child : "<<left<<endl;
		cout<<"right-child : "<<right<<endl;
	}
	
};

//随机产生一个二叉树节点
TreeNode* Random_TreeNode()
{
	TreeNode* node = new TreeNode(rand()%20);
	return node;
}

//随机构造一棵二叉树
TreeNode* Random_Tree(int round)
{
	TreeNode * root = Random_TreeNode();
	TreeNode *pre = root;
	for(int i = 0;i < round;i++)
	{
		int tag = rand()%2;
		if(tag)
		{
			TreeNode* tmp1 = Random_TreeNode();
			TreeNode* tmp2 = Random_TreeNode();
			pre->left = tmp1;
			pre->right = tmp2;
			pre = (rand()%2)?tmp1:tmp2;
		}
		else
		{
			TreeNode* tmp1 = Random_TreeNode();
			if(rand()%2) pre->left = tmp1;
			else pre->right = tmp1;
			pre = tmp1;
		}
	}
	return root;
}

int main(void)
{
	srand((unsigned)time(0));
	//test_chapter5_binary_tree_1();
	return 0;
}

$1$.编写二叉树三种遍历的非递归形式。

void PreOrder(TreeNode *t)
{
	if(!t) return ;
	printf("%d ",t->val);
	PreOrder(t->left);
	PreOrder(t->right);
}

void InOrder(TreeNode *t)
{
	if(!t) return ;
	InOrder(t->left);
	printf("%d ",t->val);
	InOrder(t->right);
}

void PostOrder(TreeNode *t)
{
	if(!t) return ;
	PostOrder(t->left);
	PostOrder(t->right);
	printf("%d ",t->val);
}

void PreOrderWithStack(TreeNode *t)
{
	stack<TreeNode*> s;
	while(!s.empty() || t)
	{ 
		while(t)                            
		{
			printf("%d ",t->val); 
			s.push(t);
			t = t->left; 
		}
		if(!s.empty())
		{
			t = s.top();
			s.pop();
			t = t->right;
		}
	}
	cout<<endl;
}

void InOrderWithStack(TreeNode *t)
{ 
	stack<TreeNode*> s;
	while(!s.empty() || t)
	{
		while(t)
		{
			s.push(t);
			t = t->left; 
		}
		if(!s.empty())
		{
			t = s.top();
			s.pop();
			printf("%d ",t->val);
			t = t->right;
		}
	}
	cout<<endl;
}

void PostOrderWithStack(TreeNode *t)
{
	stack<TreeNode*> s;
	TreeNode* r = nullptr; //r记录访问过的节点 
	while(!s.empty() || t)
	{
		while(t)
		{
			s.push(t);
			t = t->left; 
		}
		if(!s.empty())
		{
			t = s.top();                  //已经走到最左边，回溯上个节点 
			if(t->right && t->right != r) //如果存在右子树且尚未被访问 
			{
				t = t->right;             //转向右节点 
				s.push(t);                //入栈 
				t = t->left;              //重新一直向左走到底 
			}
			else
			{
				s.pop();                  //左右均无，则再回溯 
				printf("%d ",t->val);     //同时可以访问此时的子节点 
				r = t;                    //记录已经被访问过 
				t = nullptr;              //重置 
			}
		}
	}
	cout<<endl;
}

void test_chapter5_binary_tree_1()
{
	TreeNode *root = Random_Tree(10);
	cout<<"PreOrder in two Ways:"<<endl;
	PreOrder(root);          cout<<endl;
	PreOrderWithStack(root); cout<<endl;
	
	cout<<"InOrder in two Ways:"<<endl;
	InOrder(root);           cout<<endl;
	InOrderWithStack(root);  cout<<endl;
	
	cout<<"PosrOrder in two Ways:"<<endl;
	PostOrder(root);         cout<<endl;
	PostOrderWithStack(root);cout<<endl;
}

/*
* Test Chapter5 Binary Tree 1 Result:
* PreOrder in two Ways:
* 15 6 7 5 16 1 3 7 12 13 7 14 1 5
* 15 6 7 5 16 1 3 7 12 13 7 14 1 5

* InOrder in two Ways:
* 6 15 5 1 7 3 13 1 14 5 7 12 16 7
* 6 15 5 1 7 3 13 1 14 5 7 12 16 7

* PostOrder in two Ways:
* 6 7 1 5 14 7 13 12 3 1 16 5 7 15
* 6 7 1 5 14 7 13 12 3 1 16 5 7 15
*/

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2021-04-08 19:26}$