二叉树c语言的实现

二叉树的建立

二叉树的数据结构

typedef struct node
{
    int data;
    struct node* left;
    struct node* right;
    /* data */
} Node;

简单创建节点

int main() {
    Node n1;
    Node n2;
    Node n3;
    Node n4;
​
    n1.data = 5;
    n2.data = 6;
    n3.data = 7;
    n4.data = 8;
    //这时候节点没有连接起来   对节点进行连接
    n1.left = &n2; //n2是一个数据实体 而left需要是一个指针 取n2的地址拼到n1的左边上去
    n1.right = &n3;
    n2.left = &n4;
    n2.right = NULL; //即使没东西也要 给出NULL
    n3.left = NULL;
    n3.right = NULL;
    n4.left = NULL;
    n4.right = NULL;
    //创建成功
    //先序遍历验证
    preorder(&n1);//放入一个指针地址 作为头节点
}

通过遍历树来确认是否是一个真正的二叉树

//先序遍历 递归
void preorder(Node* node){
    if(node != NULL){
        printf("%d\n",node -> data);
        preorder(node -> left);
        preorder(node -> right);
}
}
​

输出结果

中序和后续遍历

//中序遍历 递归
void inorder(Node* node){
    if(node != NULL){
        
        inorder(node -> left);
        printf("%d\n",node -> data);
        inorder(node -> right);
}
}
//后序遍历 递归
void postorder(Node* node){
    if(node != NULL){
        postorder(node -> left);
        postorder(node -> right);
        printf("%d\n",node -> data);
}
}

改写创建树的代码

void createBiTree(BiTree *T)
{
    char ch;
    scanf ("%c", &ch);  //如果是字符型 %c 回车输入 算一个字符，ubutun会一直递归
    if (ch == '#')//扩展二叉树，虚结点 == 0
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree )malloc(sizeof(BiTNode));  //!!! stdlib.h 头文件一定要加！！！
        if (!*T)
        {
            exit(-1);   //错误退出
        }
        (*T)->data = ch;    //生成根结点
        createBiTree(&((*T)->lchild));  //构造左子树
        createBiTree(&((*T)->rchild));  //构造右子树
    }
}

最终代码

#include <stdio.h>
#include <stdlib.h>
 
typedef char ElemType;  //这里用int 作为树结点的数据
 
typedef struct BiTNode
{
    ElemType data;
    struct  BiTNode *lchild, *rchild;   //左右孩子指针
}BiTNode, *BiTree;
 
void createBiTree(BiTree *T);       //创建树
void preOrderTraverse(BiTree T);    //前序遍历
void inOrderTraverse(BiTree T);     //中序遍历
void postOrderTraverse(BiTree T);   //后序遍历
 
int main()
{
    BiTree T = NULL;
    createBiTree(&T);
    preOrderTraverse(T);
    printf("\n");
    inOrderTraverse(T);
    printf("\n");
    postOrderTraverse(T);
    return 0;
}
 
void createBiTree(BiTree *T)
{
    char ch;
    scanf ("%c", &ch);  //如果是字符型 %c 回车输入 算一个字符，ubutun会一直递归
    if (ch == '#')//扩展二叉树，虚结点 == 0
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree )malloc(sizeof(BiTNode));  //!!! stdlib.h 头文件一定要加！！！
        if (!*T)
        {
            exit(-1);   //错误退出
        }
        (*T)->data = ch;    //生成根结点
        createBiTree(&((*T)->lchild));  //构造左子树
        createBiTree(&((*T)->rchild));  //构造右子树
    }
}
 
void preOrderTraverse(BiTree T)
{
    if (NULL == T)
    {
        return;
    }
    printf("%c", T->data);  //显示结点数据，可以改成其他对结点的操作
    preOrderTraverse(T->lchild);    //再先序遍历左子树
    preOrderTraverse(T->rchild);    //最后先序遍历右子树
}
 
void inOrderTraverse(BiTree T)
{
    if (NULL == T)
    {
        return;
    }
    inOrderTraverse(T->lchild); //中序遍历左子树
    printf("%c", T->data);          //显示结点数据，可以改成其他对结点的操作
    inOrderTraverse(T->rchild); //最后再中序遍历右子树
}
 
void postOrderTraverse(BiTree T)
{
    if (NULL == T)
    {
        return;
    }
    postOrderTraverse(T->lchild);   //先后序遍历左子树
    postOrderTraverse(T->rchild);   //再后序遍历右子树
    printf("%c", T->data);          //显示结点数据，可以改成其他对结点的操作
}
​

输入数据

ABDG##H###CE#I##F##

输出数据

c语言_二叉树的建立以及3种递归的相关教程结束。