二叉树的前中后遍历递归非递归实现

绝地灬酷狼 2022-08-03 15:41 138阅读 0赞

好吧，我终于把前中后 递归和非递归的都写出来了。。如下： 不解释

#include<iostream>
    #include<stack>
    using namespace std;
    struct BTNode
    {
    	BTNode *left;
    	BTNode *right;
    	int data;
    
    };
    void AssertBTN(BTNode *&root1, int a)
    {
    	if (root1 == NULL)
    	{
    		root1 = new BTNode();
    		root1->data = a;
    	}
    	else
    	{
    		if (a>root1->data)
    			AssertBTN(root1->right, a);
    		if (a<root1->data)
    			AssertBTN(root1->left, a);
    	}
    }
    
    //非递归前序遍历
    stack <BTNode *> s_Pre;
    void PreOrder_BT_NoRecursion(BTNode *root)
    {
    	if (root)s_Pre.push(root);
    	while (!s_Pre.empty())
    	{
    
    		BTNode  *temp = s_Pre.top();
    		s_Pre.pop();
    		cout << temp->data<<endl;
    		if (temp->right)s_Pre.push(temp->right);
    		if (temp->left)s_Pre.push(temp->left);
    	}
    
    }
    //递归前序遍历
    void PreOrder_BT_Recursion(BTNode *root)
    {
    	
    	if (root)
    	{
    		cout << root->data<<endl;
    		PreOrder_BT_Recursion(root->left);
    		PreOrder_BT_Recursion(root->right);
    	}
    }
    //非递归中序遍历
    stack<BTNode*>s_In;
    void InOrder_BT_NoRecursion(BTNode *root)
    {
    		while (root || !s_In.empty())
    		{
    			if (root)
    			{
    				s_In.push(root);
    				root = root->left;
    			}
    			else 
    			{
    				root = s_In.top();
    				cout << root->data << endl;
    				s_In.pop();
    				root = root->right;
    			}
    		}
    }
    //递归中序遍历
    void InOrder_BT_Recursion(BTNode *root)
    {
    	if (root)
    	{
    		InOrder_BT_Recursion(root->left);
    		cout << root->data << endl;
    		InOrder_BT_Recursion(root->right);
    	}
    }
    //非递归后序遍历
    void PostOrder_BT_NoRecursion(BTNode *root)
    {
    
    }
    //递归后序遍历
    void PostOrder_BT_Recursion(BTNode *root)
    {
    	if (root)
    	{
    		PostOrder_BT_Recursion(root->left);
    		PostOrder_BT_Recursion(root->right);
    		cout << root->data<<endl;
    	}
    }
    int main()
    {
    	BTNode *root = NULL;
    	AssertBTN(root, 5);
    	AssertBTN(root, 6);
    	AssertBTN(root, 4);
    	AssertBTN(root, 1);
    	AssertBTN(root, 2);
    	AssertBTN(root, 7);
    	AssertBTN(root, 11);
    	AssertBTN(root, 9);
    	//PreOrder_BT_NoRecursion(root);
    	//PreOrder_BT_Recursion(root);
    	//InOrder_BT_NoRecursion(root);
    	//InOrder_BT_Recursion(root);
    	PostOrder_BT_Recursion(root);
    	delete root;
    
    	return 0;
    }