二叉树遍历01

0x00 二叉树的递归遍历

void preordertraversal(list* p){
	if(p){
		printf("%d",p->data);
		preordertraversal(p->left);
		preordertraversal(p->right);
	}
}
void inordertraversal(list* p){
	if(p){
		preordertraversal(p->left);
		printf("%d",p->data);
		preordertraversal(p->right);
	}
}
void postordertraversal(list* p){
	if(p){
		preordertraversal(p->left);
		preordertraversal(p->right);
		printf("%d",p->data);
	}
}

0x01 非递归遍历（堆栈实现）

递归实现既是使用系统的·函数堆栈实现，只要清楚访问到底是在左子树进堆栈前还是后，就可以自己构堆栈实现。

先序遍历

void preordertraversal(node* head){
	stack* s=createstack(1000);
	node p=head;
	while(p||s->top!=-1){
		while(p){
			printf("(%d)",p->data);
			push(s,p);
			p=p->left;
		}
		p=pop(s);
		p=p->right;
	}
	return ;
}

中序遍历

相对于先序遍历只是简单的改变了访问的顺序，在左子树出堆栈返回时才访问本身，这和递归遍历是一致的！

void inordertraversal(node* head){
	stack* s=createstack(1000);
	node p=head;
	while(p||s->top!=-1){
		while(p){
			push(s,p);
			p=p->left;
		}
		p=pop(s);
		printf("(%d)",p->data);
		p=p->right;
	}
	return ;
}

后序遍历

后续遍历比较麻烦一点，1 什么时候该访问节点，按照递归版本，先访问左节点，当左节点没有时，访问右节点，右节点如果有，指针就指向右节点，又循环这个过程，如果没有，那么久该出栈一个节点，也就是最近的父节点A，访问他。但是如果循环继续，发现，又会重复的访问这个A的左右节点，所以我们给每个节点加一个flag初始为0，在入栈的时候判断下，如果为0就允许入栈，并改成1，这样左节点就不会重复访问。同样，访问右节点时也判断下，没有右节点或者右节点被访问过都表示该出栈父节点了。

void postordertraversal(node* head){
	stack* s=createstack(1000);
	node p=head;
	while(p||s->top!=-1){
		while(p){
			if(!p->flag){
				p->flag=1;
				push(s,p);
				p=p->left;
			}else{
				break;
			}	
		}
		if(s->top!=-1){
			p=s->data[s->top];
		}	
		p=p->right;
        if(!p||p->flag){
			if(s->top!=-1){
			p=pop(s);
			printf("(%d) ",p->data);	
			}else{
				break;
			}
			
		}
	}
	return;
} 

以上代码均测试通过

二叉树遍历1