首页 > 数据结构 > 树存储结构 阅读：35945

二叉树先序遍历（递归与非递归）及C语言实现

< 上一节下一节 >
通义灵码
二叉树先序遍历的实现思想是：
  1. 访问根节点；
  2. 访问当前节点的左子树；
  3. 若当前节点无左子树，则访问当前节点的右子树；

图 1 二叉树
 
以图  1 为例，采用先序遍历的思想遍历该二叉树的过程为：
  1. 访问该二叉树的根节点，找到 1；
  2. 访问节点 1 的左子树，找到节点 2；
  3. 访问节点 2 的左子树，找到节点 4；
  4. 由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节点 5；
  5. 由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；
  6. 访问节点 3 左子树，找到节点 6；
  7. 由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
  8. 节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；

因此，图 1 中二叉树采用先序遍历得到的序列为：

1 2 4 5 3 6 7

递归实现

二叉树的先序遍历采用的是递归的思想，因此可以递归实现，其 C 语言实现代码为：
  1. #include <stdio.h>
  2. #include <string.h>
  3. #define TElemType int
  4. //构造结点的结构体
  5. typedef struct BiTNode{
  6.     TElemType data;//数据域
  7.     struct BiTNode *lchild,*rchild;//左右孩子指针
  8. }BiTNode,*BiTree;
  9. //初始化树的函数
  10. void CreateBiTree(BiTree *T){
  11.     *T=(BiTNode*)malloc(sizeof(BiTNode));
  12.     (*T)->data=1;
  13.     (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
  14.     (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  15.   
  16.     (*T)->lchild->data=2;
  17.     (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
  18.     (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  19.     (*T)->lchild->rchild->data=5;
  20.     (*T)->lchild->rchild->lchild=NULL;
  21.     (*T)->lchild->rchild->rchild=NULL;
  22.     (*T)->rchild->data=3;
  23.     (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
  24.     (*T)->rchild->lchild->data=6;
  25.     (*T)->rchild->lchild->lchild=NULL;
  26.     (*T)->rchild->lchild->rchild=NULL;
  27.     (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  28.     (*T)->rchild->rchild->data=7;
  29.     (*T)->rchild->rchild->lchild=NULL;
  30.     (*T)->rchild->rchild->rchild=NULL;
  31.     (*T)->lchild->lchild->data=4;
  32.     (*T)->lchild->lchild->lchild=NULL;
  33.     (*T)->lchild->lchild->rchild=NULL;
  34. }
  35.  
  36. //模拟操作结点元素的函数，输出结点本身的数值
  37. void displayElem(BiTNode* elem){
  38.     printf("%d ",elem->data);
  39. }
  40. //先序遍历
  41. void PreOrderTraverse(BiTree T){
  42.     if (T) {
  43.         displayElem(T);//调用操作结点数据的函数方法
  44.         PreOrderTraverse(T->lchild);//访问该结点的左孩子
  45.         PreOrderTraverse(T->rchild);//访问该结点的右孩子
  46.     }
  47.     //如果结点为空，返回上一层
  48.     return;
  49. }
  50. int main() {
  51.     BiTree Tree;
  52.     CreateBiTree(&Tree);
  53.     printf("先序遍历: \n");
  54.     PreOrderTraverse(Tree);
  55. }
运行结果：
先序遍历:
1 2 4 5 3 6 7

非递归实现

而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现，其 C 语言实现代码为：
  1. #include <stdio.h>
  2. #include <string.h>
  3. #define TElemType int
  4. int top=-1;//top变量时刻表示栈顶元素所在位置
  5. //构造结点的结构体
  6. typedef struct BiTNode{
  7.     TElemType data;//数据域
  8.     struct BiTNode *lchild,*rchild;//左右孩子指针
  9. }BiTNode,*BiTree;
  10. //初始化树的函数
  11. void CreateBiTree(BiTree *T){
  12.     *T=(BiTNode*)malloc(sizeof(BiTNode));
  13.     (*T)->data=1;
  14.     (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
  15.     (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  16.     (*T)->lchild->data=2;
  17.     (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
  18.     (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  19.     (*T)->lchild->rchild->data=5;
  20.     (*T)->lchild->rchild->lchild=NULL;
  21.     (*T)->lchild->rchild->rchild=NULL;
  22.     (*T)->rchild->data=3;
  23.     (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
  24.     (*T)->rchild->lchild->data=6;
  25.     (*T)->rchild->lchild->lchild=NULL;
  26.     (*T)->rchild->lchild->rchild=NULL;
  27.     (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  28.     (*T)->rchild->rchild->data=7;
  29.     (*T)->rchild->rchild->lchild=NULL;
  30.     (*T)->rchild->rchild->rchild=NULL;
  31.     (*T)->lchild->lchild->data=4;
  32.     (*T)->lchild->lchild->lchild=NULL;
  33.     (*T)->lchild->lchild->rchild=NULL;
  34. }
  35. //前序遍历使用的进栈函数
  36. void push(BiTNode** a,BiTNode* elem){
  37.     a[++top]=elem;
  38. }
  39. //弹栈函数
  40. void pop( ){
  41.     if (top==-1) {
  42.         return ;
  43.     }
  44.     top--;
  45. }
  46. //模拟操作结点元素的函数，输出结点本身的数值
  47. void displayElem(BiTNode* elem){
  48.     printf("%d ",elem->data);
  49. }
  50. //拿到栈顶元素
  51. BiTNode* getTop(BiTNode**a){
  52.     return a[top];
  53. }
  54. //先序遍历非递归算法
  55. void PreOrderTraverse(BiTree Tree){
  56.     BiTNode* a[20];//定义一个顺序栈
  57.     BiTNode * p;//临时指针
  58.     push(a, Tree);//根结点进栈
  59.     while (top!=-1) {
  60.         p=getTop(a);//取栈顶元素
  61.         pop();//弹栈
  62.         while (p) {
  63.             displayElem(p);//调用结点的操作函数
  64.             //如果该结点有右孩子，右孩子进栈
  65.             if (p->rchild) {
  66.                 push(a,p->rchild);
  67.             }
  68.             p=p->lchild;//一直指向根结点最后一个左孩子
  69.         }
  70.     }
  71. }
  72. int main(){
  73.     BiTree Tree;
  74.     CreateBiTree(&Tree);
  75.     printf("先序遍历: \n");
  76.     PreOrderTraverse(Tree);
  77. }
运行结果
先序遍历:
1 2 4 5 3 6 7
< 上一节下一节 >