二叉树先序遍历，代码及详解

二叉树的便历主要有四种方式：
（D根节点 L左子树 R右子树）
（1）先序遍历DLR
（2）中序遍历LDR
（3）后序遍历LRD
（4）按层遍历

（1）先序遍历
递归算法：

void PreOrder(BTNode *bt)
{
	if(bt!=NULL)
	{
		printf("%d",bt->data);
		PreOrder(bt->lchild);
		PreOrder(bt->rchild);
	}
}

非递归算法

#difine NULL 0
Void PreOrder(BTNode *bt)
{
	BTNode *p=bt;
	printf("\npreorder travel:\n");
	While(!（p==NULL&&top==NULL）)
	{
		if(p!=NULL)
		{
			printf("%d",p->data);
			push(p);
			p=p->lchild;
		}
		else
		{
			pop();
			p=p->rchild;
		}
	}
}

以本图为例,演示非递归的先序遍历算法：

1.首先，程序通过BTNode *p=bt将根节点的地址赋给p，此时p指向A；
2.执行if中的内容；打印A，将A放入栈中，指针指向A的左孩子B；
3.执行if中的内容；打印B，将B放入栈中，指针指向B的左孩子D；
4.执行if中的内容：打印D，将D放入栈中，指针指向D的左孩子，左孩子为空；
5.执行else中的内容；从栈中弹出D，指针指向D的右孩子；
6.执行if中的内容：打印G，将G放入栈中，指针指向G的左孩子，左孩子为空；
7.执行else中的内容；从栈中弹出G，指针指向G的右孩子，右孩子为空；
8.执行else中的内容；从栈中弹出B，指针指向B的右孩子E；
9.执行if中的内容：打印E，将E放入栈中，指针指向E的左孩子H；
10.执行if中的内容：打印H，将H放入栈中，指针指向H的左孩子，左孩子为空；
11.执行else中的内容；从栈中弹出H，指针指向H的右孩子，右孩子为空；
12.执行else中的内容；从栈中弹出E，指针指向E的右孩子，右孩子为空;
13.执行else中的内容；从栈中弹出A，指针指向A的右孩子C;
14.执行if中的内容：打印C，将C放入栈中，指针指向C的左孩子F;
15.执行if中的内容：打印F，将F放入栈中，指针指向F的左孩子I;
16执行if中的内容：打印I，将I放入栈中，指针指向I的左孩子,左孩子为空；
17.执行else中的内容；从栈中弹出I，指针指向I的右孩子，右孩子为空；
18.执行else中的内容；从栈中弹出F，指针指向F的右孩子，右孩子为空；
19.执行else中的内容；从栈中弹出C，指针指向C的右孩子，右孩子为空；
20.栈中无元素，遍历结束。