二叉树递归和非递归遍历

拼搏现实的明天。 2021-12-17 04:07 366阅读 0赞

## 二叉树递归和非递归遍历 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]  
源码：

#include<queue>
    #include<stack>
    #include<vector>
    #include<iostream>
    using namespace std;
    //假设空节点的值为-1
    //const int arrrlens = 18;
    //char arr[arrrlens] = { 'A', 'B', 'D' , '#', 'H', '#', '#', 'E', '#', '#',\
               'C', 'F' , '#', '#', 'G', '#', '#'};
    //A B D # H # # E # # C F # # G # #
    class Node {
    public:
    
    	Node(int el = 0, Node * l = NULL, Node * r = NULL) {
    		data = el;
    		mark = 0;
    		left = l;
    		right = r;
    	}
    	char data;
    	int mark;
    	Node* left, * right;
    };
    class Tree {
    public:
    
    	Tree() { root = NULL; }
    	~Tree() { delete root; }
    	int create(Node* &);
    	int preOrder();
    	int infxOrder();
    	int postOrder();
    	int print_preOrder(Node*);
    	int print_infixOrder(Node*);
    	int print_postOrder(Node*);
    public:
    	Node* root;
    };
    int Tree::print_preOrder(Node* root)
    {
    	//递归先序遍历
    	if (root != NULL)
    	{
    		cout << root->data << " ";
    		print_preOrder(root->left);
    		print_preOrder(root->right);
    	}
    	return 0;
    }
    int Tree::print_infixOrder(Node* root)
    {
    	//递归中序遍历
    	if (root != NULL)
    	{
    		print_infixOrder(root->left);
    		cout << root->data << " ";
    		print_infixOrder(root->right);
    	}
    	return 0;
    }
    int Tree::print_postOrder(Node* root)
    {
    	//递归后序遍历
    	if (root != NULL)
    	{
    		print_postOrder(root->left);
    		print_postOrder(root->right);
    		cout << root->data << " ";
    	}
    	return 0;
    }
    int Tree::preOrder()
    {
    	/*先序遍历，采用非递归的方法*/
    	cout << endl << "先序遍历，采用非递归的方法" << endl;
    	Node* p = root;
    	stack<Node*> S;
    	while (p != NULL || !S.empty())
    	{
    		if (p != NULL)
    		{ 
    			cout << p->data << " ";
    			S.push(p);
    			p = p->left;
    		}
    		else
    		{
    			p = S.top();
    			S.pop();
    			p = p->right;
    		}
    	}
    	return 0;
    }
    int Tree::infxOrder()
    {
    	/*中序遍历，采用非递归的方法*/
    	cout << endl << "中序遍历，采用非递归的方法" << endl;
    	Node* p = root;
    	stack<Node*> S;
    	while (p != NULL || !S.empty())
    	{
    		if (p != NULL)
    		{ 
    			S.push(p);
    			p = p->left;
    		}
    		else {
    			p = S.top();
    			S.pop();
    			cout << p->data << " ";
    			p = p->right;
    		}
    	}
    	return 0;
    }
    int Tree::postOrder()
    {
    	/*后序遍历，采用非递归的方法*/
    	cout << endl << "后序遍历，采用非递归的方法" << endl;
    	Node* p = root;
    	vector<Node*> S;
    	vector<char> res;
    	while (p != NULL || !S.empty())
    	{
    		if (p != NULL)
    		{
    			S.push_back(p);
    			res.push_back(p->data);
    			p = p->right;
    		}
    		else
    		{
    			p = S.back();
    			S.pop_back();
    			p = p->left;
    		}
    	}
    	reverse(res.begin(), res.end());
    	vector<char>::iterator ite = res.begin();
    	for (; ite != res.end(); ite++) {
    		cout << *ite <<" ";
    	}
    	cout << endl;
    	return 0;
    }
    int Tree::create(Node*& root)
    {
    	// input: A B D # H # # E # # C F # # G # #
    	char val;
    	cin >> val;
    	if (val != '#')
    	{
    		root = new Node(val);
    		create(root->left);
    		create(root->right);
    	}
    	else
    		root = NULL;
    	return 0;
    }
    int main()
    {
    	Tree tree;
    	//intpu: A B D # H # # E # # C F # # G # #
    	tree.create(tree.root);
    	cout << " 递归先序遍历" << endl;
    	tree.print_preOrder(tree.root);
    	cout << endl << " 递归中序遍历" << endl;
    	tree.print_infixOrder(tree.root);
    	cout << endl << " 递归后序遍历" << endl;
    	tree.print_postOrder(tree.root);
    	tree.preOrder();
    	tree.infxOrder();
    	tree.postOrder();
    	return 0;
    }

结果:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]: /images/20211213/dd5dbd039b0c49aea164541a79568363.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70 1]: /images/20211213/7dc1f68ecca54822adeeb340f47b5a26.png