二叉树-先序遍历-递归实现

视频链接

构造一个二叉树，如图

使用递归的方式遍历此二叉树。

C语言实现代码：

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

typedef int DataType;

typedef struct Node
{
    DataType data;                  //数据域
    struct Node * lchild;           //指向左孩子
    struct Node * rchild;           //指向右孩子
}BtNode;


//访问节点的函数
void visit(BtNode * node)
{
    printf("data = %d\n",node->data);
}

//先序遍历二叉树  根 - 左 - 右
void PreOrder(BtNode * root)
{
    if(root)
    {
       //访问根
       visit(root);
       PreOrder(root->lchild);          //先序遍历左子树
       PreOrder(root->rchild);          //先序遍历右子树
    }
}

int main()
{
    
    //构造一个二叉树

    BtNode * tree = (BtNode *)malloc(sizeof(BtNode));          //从内存中分配空间
    tree->data = 1;

    BtNode * node2 = (BtNode *)malloc(sizeof(BtNode));
    node2->data = 2;

    BtNode * node3 = (BtNode *)malloc(sizeof(BtNode));
    node3->data = 3;

    BtNode * node4 = (BtNode *)malloc(sizeof(BtNode));
    node4->data = 4;

    BtNode * node5 = (BtNode *)malloc(sizeof(BtNode));
    node5->data = 5;

    BtNode * node6 = (BtNode *)malloc(sizeof(BtNode));
    node6->data = 6;

    BtNode * node7 = (BtNode *)malloc(sizeof(BtNode));
    node7->data = 7;

    tree->lchild = node2;
    tree->rchild = node3;
    node2->lchild = node4;
    node2->rchild = node5;
    node3->lchild = NULL;
    node3->rchild = node6;
    node4->lchild = NULL;
    node4->rchild = NULL;
    node5->lchild = node7;
    node5->rchild = NULL;
    node6->lchild = NULL;
    node6->rchild = NULL;
    node7->lchild = NULL;
    node7->rchild = NULL;

    PreOrder(tree);

    return 0;
}

以上代码可在Linux中使用Gcc编译。