二叉树的链式存储结构 C语言实现

二叉树的二叉链表

含有两个指针域的结点结构
2662051187.png

#include<stdio.h>
#include<malloc.h>
#define ElemType char

typedef struct BiTNode {
    ElemType Data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode;

//构造空二叉树(结点)
BiTNode* InitBiTree(ElemType data) {
    BiTNode* newtree = malloc(sizeof(BiTNode));
    newtree->lchild = NULL;
    newtree->rchild = NULL;
    newtree->Data = data;
    return newtree;
}

//根据LR为0或1,插入insert给定结点tree的左子树或右子树
void InsertChild(BiTNode* tree, int LR, BiTNode* insert) {
    if (LR == 0)
        tree->lchild = insert;
    else if (LR == 1)
        tree->rchild = insert;
}

//删除给定结点tree
void DelNode(BiTNode* tree) {
    if (tree->lchild) {
        DelNode(tree->lchild);
        tree->lchild = NULL;
    }
    if (tree->rchild) {
        DelNode(tree->rchild);
        tree->rchild = NULL;
    }
    free(tree);
}

//根据LR为0或1,删除给定结点tree的左子树或右子树
void DelChild(BiTNode* tree, int LR) {
    if (LR == 0)
        if (tree->lchild) {
            DelNode(tree->lchild);
            tree->lchild = NULL;
        }
        else
            printf("该结点无左子树");
    else if (LR == 1)
        if (tree->rchild) {
            DelNode(tree->rchild);
            tree->rchild = NULL;
        }
        else
            printf("该结点无右子树");
}

//给给定结点tree赋值
void Assign(BiTNode* tree, ElemType data) {tree->Data = data;}

//返回给定结点tree的右子树
BiTNode* RightChild(BiTNode* tree) {return tree->rchild;}

//返回给定结点tree的左子树
BiTNode* LeftChild(BiTNode* tree) {return tree->lchild;}

//返回给定结点tree的值
ElemType Value(BiTNode* tree) {return tree->Data;}

测试:生成如图所示二叉树
未标题-1.png

int main() {
    BiTNode* top = InitBiTree('-');
    InsertChild(top, 0, InitBiTree('+'));
    InsertChild(top, 1, InitBiTree('/'));
    InsertChild(top->lchild, 0, InitBiTree('a'));
    InsertChild(top->lchild, 1, InitBiTree('*'));
    InsertChild(top->rchild, 0, InitBiTree('e'));
    InsertChild(top->rchild, 1, InitBiTree('f'));
    InsertChild(top->lchild->rchild, 0, InitBiTree('b'));
    InsertChild(top->lchild->rchild, 1, InitBiTree('-'));
    InsertChild(top->lchild->rchild->rchild, 0, InitBiTree('c'));
    InsertChild(top->lchild->rchild->rchild, 1, InitBiTree('d'));
}

其他函数

留下你的评论