二叉树先序遍历C语言实现
来源：SegmentFault 思否
二叉树先序遍历的实现思想是：
-
访问根节点； -
访问当前节点的左子树； -
若当前节点无左子树，则访问当前节点的右子树；
以图 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);}
思想：循环开始，从栈顶节点（除第一次是根节点）开始不断左探，入栈并打印，直到左孩子为空；然后指针指向栈顶元素的右孩子，开启下一轮循环。
- END -