c语言版本二叉树基本操作示例(先序 递归 非递归)

C语言版本二叉树基本操作示例(先序 递归 非递归)

二叉树是一种重要的数据结构，用于组织和存储数据。C语言是一种常用的编程语言，具有许多优秀的二叉树操作库。本文将介绍C语言版本二叉树的基本操作示例，包括先序遍历的递归和非递归实现。

先序遍历的递归实现

先序遍历是指从根节点开始遍历，先输出根节点，然后递归遍历左子树和右子树。该算法可以简单地通过递归函数来实现。

#include <stdio.h>
#include <stdlib.h>

//定义二叉树节点
typedef struct TreeNode{
    int data;   //节点数据
    struct TreeNode* left;  //左子树
    struct TreeNode* right; //右子树
}TreeNode,*BinTree;

//构建二叉树
BinTree CreateBinTree(){
    BinTree root = NULL;
    int data;
    scanf("%d", &data);

    if(data == -1){ //递归结束
        return NULL;
    }

    root = (BinTree)malloc(sizeof(TreeNode));
    root->data = data;          //根节点
    root->left = CreateBinTree();//左子树
    root->right = CreateBinTree();//右子树

    return root;
}

//先序遍历的递归实现
void PreOrder(BinTree root){
    if(root == NULL){
        return;
    }

    printf("%d ",root->data);   //输出根节点
    PreOrder(root->left);       //遍历左子树
    PreOrder(root->right);      //遍历右子树
}

//主函数
int main(){
    BinTree root = NULL;

    printf("请输入二叉树节点：\n");
    root = CreateBinTree();

    printf("先序遍历的递归结果：\n");
    PreOrder(root);   

    return 0;
}

示例输入：

请输入二叉树节点：
1
2
-1
-1
3
-1
-1

示例输出：

先序遍历的递归结果：
1 2 3

先序遍历的非递归实现

非递归实现先序遍历就是利用栈先进后出的特性，完成遍历。该算法与递归算法相比，不需要额外的函数调用开销，因此效率更高。

#include <stdio.h>
#include <stdlib.h>

//定义二叉树节点
typedef struct TreeNode{
    int data;   //节点数据
    struct TreeNode* left;  //左子树
    struct TreeNode* right; //右子树
}TreeNode,*BinTree;

int stack_size = 100;    //栈的大小
int top = -1;            //栈指针

//构建二叉树
BinTree CreateBinTree(){
    BinTree root = NULL;
    int data;
    scanf("%d", &data);

    if(data == -1){ //递归结束
        return NULL;
    }

    root = (BinTree)malloc(sizeof(TreeNode));
    root->data = data;          //根节点
    root->left = CreateBinTree();//左子树
    root->right = CreateBinTree();//右子树

    return root;
}

//先序遍历的非递归实现
void PreOrder(BinTree root)
{
    BinTree stack[stack_size]; //定义栈
    while(root != NULL || top != -1){ //循环条件
        while(root != NULL){  //往左子树寻找，直到没有左子树
            printf("%d ",root->data);//输出根节点
            stack[++top] = root;     //在栈中保存该节点
            root = root->left;       //遍历左子树
        }
        if(top != -1){          //如果栈不空
            root = stack[top--]; //出栈
            root = root->right;  //遍历右子树
        }
    }
}

//主函数
int main(){
    BinTree root = NULL;

    printf("请输入二叉树节点：\n");
    root = CreateBinTree();

    printf("先序遍历的非递归结果：\n");
    PreOrder(root);   

    return 0;
}

示例输入：

请输入二叉树节点：
1
2
-1
-1
3
-1
-1

示例输出：

先序遍历的非递归结果：
1 2 3

本文介绍了C语言版本二叉树的基本操作示例，包括先序遍历的递归和非递归实现。无论是递归还是非递归实现，都是二叉树基本操作中必不可少的部分，希望本文能够对读者有所帮助。