두 갈래 나무의 앞차례, 중차례, 후속 반복, 귀속, 비귀속 실현

순차 반복:

#include 
#include 
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void pre_order_recursive(TreeNode* root, vector& result) {
	if(!root) return;
	result.push_back(root->val);
	if(root->left)
		pre_order_recursive(root->left, result);
	if (root->right)
		pre_order_recursive(root->right, result);
}


/*
	   1
	  /  \
	 2    3
	/ \  / \
       4  5 6   7
*/
int main(){
	TreeNode* n1 = new TreeNode(1);
	TreeNode* n2 = new TreeNode(2);
	TreeNode* n3 = new TreeNode(3);
	TreeNode* n4 = new TreeNode(4);
	TreeNode* n5 = new TreeNode(5);
	TreeNode* n6 = new TreeNode(6);
	TreeNode* n7 = new TreeNode(7);

	n1->left = n2; n1->right = n3;
	n2->left = n4; n2->right = n5;
	n3->left = n6; n3->right = n7;

	vector res;
	pre_order_recursive(n1, res);
	for(int i = 0; i < res.size(); i++){
		cout << res[i] << " ";
	}
	system("PAUSE");
}

중순으로 두루 돌아가다

void in_order_recursive(TreeNode* root, vector& result) {
	if(root->left)
		in_order_recursive(root->left, result);
	if(root)
		result.push_back(root->val);
	if(root->right)
		in_order_recursive(root->right, result);
}

후속 반복

void post_order_recursive(TreeNode* root, vector& result) {
	if(root->left)
		post_order_recursive(root->left, result);
	if(root->right)
		post_order_recursive(root->right, result);
	if(root)
		result.push_back(root->val);
}

이전 순서가 비귀속 반복되다

void pre_order(TreeNode* root, vector& result) {
	stack st;
	while(root || !st.empty()){
		while (root){
			st.push(root);
			result.push_back(root->val);
			root = root->left;
		}
		if(!st.empty()){
			root = st.top();
			st.pop();
			root = root->right;
		}
	}
}

비귀속

void in_order(TreeNode* root, vector& result) {
	stack st;
	while(root || !st.empty()){
		while (root){
			st.push(root);
			root = root->left;
		}
		if(!st.empty()){
			root = st.top();
			result.push_back(root->val);
			st.pop();
			root = root->right;
		}
	}
}

후속 반복 비귀속 (포인터가 이전 반복 노드를 가리키며 창고의push 순서가 전 순서, 중 순서와 다르다는 것을 주의하십시오)
4

void post_order(TreeNode* root, vector& result) {
	stack st;
	TreeNode* pre = NULL;
	st.push(root);
	while(!st.empty()){
		root = st.top();
		if((root->left == NULL && root->right == NULL) || (pre == root->right) || (root->right == NULL && pre == root->left)){
			result.push_back(root->val);
			cout << root->val << " ";
			pre = root;
			st.pop();
		}
		else{
			if(root->right)
				st.push(root->right);
			if(root->left)
				st.push(root->left);
		}
	}
}

(전) 다른 방식(각 노드마다 방문 횟수 표지를 증가하고push 순서는 이전과 일치)

void postOrder2(BinTree *root)    // 
{
    stack s;
    BinTree *p=root;
    BTNode *temp;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)              // ，  
        {
            BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
            btn->btnode=p;
            btn->isFirst=true;
            s.push(btn);
            p=p->lchild;
        }
        if(!s.empty())
        {
            temp=s.top();
            s.pop();
            if(temp->isFirst==true)     //  
             {
                temp->isFirst=false;
                s.push(temp);
                p=temp->btnode->rchild;    
            }
            else                        //  
             {
                cout<btnode->data<