二叉树先序遍历C语言实现
二叉树先序遍历的实现思想是：
访问根节点；
访问当前节点的左子树；
若当前节点无左子树，则访问当前节点的右子树；
以图 1 为例，采用先序遍历的思想遍历该二叉树的过程为：
访问该二叉树的根节点，找到 1；
访问节点 1 的左子树，找到节点 2；
访问节点 2 的左子树，找到节点 4；
由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节点 5；
由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；
访问节点 3 左子树，找到节点 6；
由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；
因此，图 1 中二叉树采用先序遍历得到的序列为：
1 2 4 5 3 6 7
代码实现
char emptyData = '#'; /* 当一个节点没有左右孩子的时候,输出emptyData的值 */
// 树的结构体定义
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode,*BiTree;
递归
void PreOrderTraverse(BiTree T)
{
if (T == NULL)
{
printf("#");
return;
}
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
非递归(链栈)
栈定义
// 栈
typedef int SElemType;
typedef struct StackNode
{
BiTree TreeNode;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
}LinkStack;
栈方法
// 栈
/* 构造一个空栈S */
void InitStack(LinkStack *S)
{
S->top = (LinkStackPtr)malloc(sizeof(StackNode));
S->top = NULL;
S->count = 0;
}
/* 进栈 */
void Push(LinkStack *S,BiTNode **q)
{
LinkStackPtr p;
p = (LinkStackPtr)malloc(sizeof(StackNode));
p->TreeNode = *q;
p->next = S->top;
S->top = p;
S->count++;
}
/* 出栈 */
void Pull(LinkStack *S,BiTNode **q)
{
LinkStackPtr p;
if (S->top)
{
*q = S->top->TreeNode;
p = S->top;
S->top = S->top->next;
S->count--;
free(p);
}
}
/* 返回S的元素个数，即栈的长度 */
int StackLength(LinkStack S)
{
return S.count;
}
非递归函数
void PreOrderTraverseBak1(BiTree T,LinkStack *S)
{
BiTNode *p=T,*q;
// 表示空结点
q->data = emptyData;
q->lchild = NULL;
q->rchild = NULL;
Push(S,&p);
while(S->count != 0)
{
Pull(S,&p);
printf("%c",p->data);
if(p->rchild)
{
Push(S,&(p->rchild));
}
else if (p->data != emptyData)
{
Push(S,&q);
}
if(p->lchild)
{
Push(S,&(p->lchild));
}
else if (p->data != emptyData)
{
Push(S,&q);
}
}
printf("\n");
}
思想:使用栈，首先将头节点首先入栈 ，保证栈中开始至少有一个元素。使用一个while循环，只要栈还非空就一直进行。循环体中首先获取栈顶节点，将其打印后直接出栈，并将其的右孩子和左孩子依次入栈(如果存在的话)。根据栈的FILO特性，最后入栈的左孩子将在下一轮中成为栈顶元素。这样就能满足前序遍历的特点。
第二种非递归函数
void PreOrderTraverseBak2(BiTree T,LinkStack *S)
{
BiTNode *p=T;
while(S->count != 0 || p)
{
while(p)
{
printf("%c",p->data);
Push(S,&p);
p = p->lchild;
}
printf("%c",emptyData);
Pull(S,&p);
p = p->rchild;
}
printf("%c",emptyData);
}
思想：循环开始，从栈顶节点(除第一次是根节点)开始不断左探，入栈并打印，直到左孩子为空；然后指针指向栈顶元素的右孩子，开启下一轮循环。
