深度优先搜索

深度优先搜索

构造一棵树

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
#define tree_size 9
struct dot{
	int self;
	dot * left;
	dot * right;
}s1[maxn];
stack<dot*>s;
dot *temp;
int main()
{
	for( int i=0; i<tree_size; i++ ){
		s1[i].self=i;
		int child=i*2+1;
		if(child<tree_size) s1[i].left=&s1[child];
		else s1[i].left=NULL;
		child++;
		if(child<tree_size) s1[i].right=&s1[child];
		else s1[i].right=NULL;
	}
	return 0;
}

前序遍历

	s.push(&s1[0]);
	while(!s.empty()){
		temp=s.top();
		s.pop();
		cout<<temp->self;
		if(temp->right!=NULL) s.push(temp->right);
		if(temp->left!=NULL) s.push(temp->left);
	}

中序遍历

	temp=&s1[0];
	while(temp!=NULL||!s.empty()){
		while(temp!=NULL){
			s.push(temp);
			temp=temp->left;
		}
		if(!s.empty()){
			temp=s.top();
			s.pop();
			cout<<temp->self;
			temp=temp->right;
		}
	}
}

后序遍历

	s.push(&s1[0]);
	while(!s.empty()){
		temp=s.top();
		s.pop();
		v.push_back(temp->self);
		if(temp->left!=NULL) s.push(temp->left);
		if(temp->right!=NULL) s.push(temp->right);
	}
	reverse(v.begin(),v.end());
	for( int i=0; i<v.size(); i++ )cout<<v[i];