学步园

//先序遍历 根左右
void preOrderInter(struct Node* root){
	stack<struct Node*> s;
	s.push(root);
		
	while(!s.empty){
		Node* node = s.top();
		cout>>node->data>>endl;
		if(node->right!=NULL){
			s.push(node->right);
		}
		if(node->left!=NULL){
			s.push(node->left);
		}
	}
	
	cout<<endl;
}

//后续遍历	左右根。思路：可以先按照根右左的方式，遍历。然后将结果翻转一下就变成左右根了。利用双栈实现翻转
void afOrderInter(struct Node* root){
	stack<struct Node*> s;
	stack<struct Node*> output;
	
	s.push(root);
	
	while(!s.isEmpty()){
		Node* node = s.top
		cout>>node->data>>endl;
		output.push(node);
		s.pop();
		if(node->left!=NULL){
			s.push(node->left);
		}
		if(node->right!=NULL){
			s.push(node->right)
		}
	}
	
	//翻转
	while(!output.isEmpty()){
		Node* node = output.top();
		cout<<node->data<<endl;
		output.pop()
	}
}

//中序遍历	左根右
void inOrderInter(struct Node* root){
	stack<struct Node*> s;
	while(!s.isEmpty() || root!=NULL){
		if(root!=NULL){
			s.push(root);
			root=root->left;
		}else{
			root = s.top();
			s.pop();
			cout<<root->data;
			root=root->right;
		}
	}
}

校招一面yahoo的时候，就是这些算法题上，死的很难看。现在做个笔记。