五分钟C语言数据结构之二叉树先序遍历

Python编程爱好者

发布于 2020-09-08 15:24:13

5610

发布于 2020-09-08 15:24:13

文章被收录于专栏：Python编程爱好者Python编程爱好者

五分钟C语言实现常见数据结构之二叉树先序遍历

二叉树先序遍历

二叉树的遍历方式主要由先序遍历、中序遍历和后续遍历，然后就是层次遍历

关于二叉树的详细遍历方式，这里不详细赘述了，主要的还是代码的实现

本文主要是关于二叉树的先序遍历，或者说是前序遍历

先序遍历过程

a. 访问根节点；

b. 先序遍历其左子树；

c. 先序遍历其右子树；

然后就是一直递归下去，在访问到节点的时候，可以进行节点的相关处理，比如说简单的访问节点值

下图是一棵二叉树，我们来手动模拟一下遍历过程

按照上述先序遍历的过程，得到先序遍历序列：

A B D H I E C F G

递归实现

二叉树的先序遍历利用上述的递归思想进行C语言代码实现：

树形结构按照上述树形结构进行初始化

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define ElementType char

//结点结构体
typedef struct BinTNode{
    ElementType data; 
    struct BinTNode * left; 
    struct BinTNode * right;
}BinTNode, *BinTree;

// 初始化树形结构
BinTNode * CreateBiTree(BinTNode *T){
    T=(BinTNode*)malloc(sizeof(BinTNode));
    T->data='A';
    T->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->data='B';
    T->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->data='C';
  
    T->left->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->data='D';
    T->left->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->right->data='E';
    T->left->right->left=NULL;
    T->left->right->right=NULL;  
    T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->left->data='H';
    T->left->left->left->left=NULL;
    T->left->left->left->right=NULL;
    T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->right->data='I';
    T->left->left->right->left=NULL;
    T->left->left->right->right=NULL;
      
    T->right->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->left->data='F';
    T->right->left->left=NULL;
    T->right->left->right=NULL;
    T->right->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->right->data='G';
    T->right->right->left=NULL;
    T->right->right->right=NULL;

    return T;
}

// 遍历过程中，输出节点值
void printElement(BinTNode * T){
    printf("%c ",T->data);
}

//先序遍历
void PreOrderTraverse(BinTNode * T){
    if (T) {
        printElement(T);            //输出节点值
        PreOrderTraverse(T->left);  //递归访问左孩子
        PreOrderTraverse(T->right); //递归访问右孩子
    }
    // 当节点为空的时候，返回
    return;
}

int main() {
    BinTNode * Tree;
    Tree = CreateBiTree(Tree);  // 初始化树形结构
    printf("先序遍历: ");
    PreOrderTraverse(Tree);     // 先序递归进行
    printf("\n");               // 最后换行
    return 0;
}

运行结果：

先序遍历: A B D H I E C F G

非递归实现

非递归时，由于在遍历过程中需要保存中间值，将符合遍历的节点优先输出

所以，非递归的基本思路：使用堆栈

遇到一个结点，就访问它，并去遍历它的右子树；
如果有右孩子，压栈;
然后先序再去遍历它的左孩子。

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define ElementType char
int top = -1;   //定义top栈顶元素所在位置

// 结点结构体
typedef struct BinTNode{
    ElementType data; 
    struct BinTNode * left; 
    struct BinTNode * right;
}BinTNode, *BinTree;

// 初始化树形结构
BinTNode * CreateBiTree(BinTNode *T) {
    T=(BinTNode*)malloc(sizeof(BinTNode));
    T->data='A';
    T->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->data='B';
    T->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->data='C';
  
    T->left->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->data='D';
    T->left->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->right->data='E';
    T->left->right->left=NULL;
    T->left->right->right=NULL;  
    T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->left->data='H';
    T->left->left->left->left=NULL;
    T->left->left->left->right=NULL;
    T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->right->data='I';
    T->left->left->right->left=NULL;
    T->left->left->right->right=NULL;
      
    T->right->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->left->data='F';
    T->right->left->left=NULL;
    T->right->left->right=NULL;
    T->right->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->right->data='G';
    T->right->right->left=NULL;
    T->right->right->right=NULL;

    return T;
}

// 栈 - 进栈push
void push(BinTNode** stack,BinTNode * elem) {
    stack[++top] = elem;
}

//栈 - 弹栈pop
void pop(){
    if (top == -1) {
        return ;
    }
    top--;
}

// 遍历过程中，输出节点值
void printElement(BinTNode* elem) {
    printf("%c ",elem->data);
}

//获取栈顶元素
BinTNode* getTop(BinTNode** a){
    return a[top];
}

//非递归遍历 - 根左右
void PreOrderTraverse(BinTNode * Tree) {
    BinTNode * stack[20];     // 定义一个顺序栈PreOrderTravers_nonrecursive
    BinTNode * p;             // 定义临时指针
    push(stack, Tree);        // 将根结点入栈
    while (top != -1) {
        p = getTop(stack);    // 取栈顶元素
        pop();
        while (p) {
            printElement(p);   // 调用结点的操作函数
            if (p->right) {    // 先遍历右孩子
                push(stack, p->right);
            }
            p = p->left;       // 再遍历左孩子
        }
    }
}

int main() {
    BinTNode * Tree;
    Tree = CreateBiTree(Tree);
    printf("看到这样就对了: A B D H I E C F G\n");
    printf("先序遍历:\t");
    PreOrderTraverse(Tree);
    printf("\n");
    return 0;
}

运行结果

看到这样就对了: A B D H I E C F G
先序遍历:      A B D H I E C F G

后续会将更多的数据结构用C语言代码实现，欢迎大家关注!

作者：Johngo

图片：凡科快图

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-05-06，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

c 语言

数据结构

本文分享自计算广告生态微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

五分钟C语言数据结构之二叉树先序遍历

五分钟C语言数据结构之二叉树先序遍历

二叉树先序遍历

先序遍历过程

递归实现

非递归实现

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

五分钟C语言数据结构 之 二叉树先序遍历

五分钟C语言数据结构 之 二叉树先序遍历

二叉树先序遍历

先序遍历过程

递归实现

非递归实现

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

五分钟C语言数据结构之二叉树先序遍历

五分钟C语言数据结构之二叉树先序遍历