数据结构 树的存储结构及代码实现

7.3、二叉树的存储结构

二叉树的顺序存储

完全二叉树，实现一些基本操作，如果不是完全二叉树最好使用链表

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

#define MaxSize 100
#define ElemType int
#define boolean int
#define true 1
#define false 0

typedef struct TreeNode{
    ElemType val;   //树的结点的值
    boolean iSEmpty;//树是否为空
}TreeNode;

//初始化树的数组
boolean InitTree(TreeNode trees[]){
    for(int i = 1 ;i < MaxSize;i++){//让0号下标空缺
        trees[i].iSEmpty = true; //把所有的树都置为空
    }
    return true;
}

//第i个结点的左孩子
boolean GetLeftNode(TreeNode * left,TreeNode trees[],int i){
    if(trees[2*i].iSEmpty) printf("第%d个结点没有左孩子\n",i);
    else{
        left->val = trees[2*i].val;
        left->iSEmpty = false;
    }
    return true;
}

//第i个结点的右孩子
boolean GetRightNode(TreeNode * right,TreeNode trees[],int i){
    if(trees[2*i+1].iSEmpty) {
        printf("第%d个结点没有右孩子\n",i);
        return false;
    }
    else{
        right->val = trees[2*i+1].val;
        right->iSEmpty = false;
    }
    return true;
}

//获取第i个结点的父结点
boolean GetFatherNode(TreeNode * father,TreeNode trees[],int i){
    if(i == 1) {
        printf("第1个结点没有父节点\n");
        return false;
    }else{
        father->iSEmpty = false;
        father->val = trees[i/2].val;
        return true;
    }
}

//获取第i个结点所在的层次
int GetNodeLevel(int i){
    double d = log2(i+1);
    int level = (int)d;
    return level+1;
}

测试

int main(){
    TreeNode trees[MaxSize];//定义一个数组来存储树的结点
    InitTree(trees);
    for(int i = 1;i <= 12;i++){//初始化树
        trees[i].val = i;
        trees[i].iSEmpty = false;
    }

    TreeNode left;
    TreeNode right;
    left.iSEmpty = true;
    right.iSEmpty = true;
    GetLeftNode(&left,trees,6);
    GetRightNode(&right,trees,6);
    if(!left.iSEmpty){
        printf("第6个结点的左孩子：%d \n",left.val);
    }
    if(!right.iSEmpty){
        printf("第6个结点的左孩子：%d \n",right.val);
    }

    TreeNode father;
    father.iSEmpty = true;
    GetFatherNode(&father,trees,5);
    if(!father.iSEmpty){
        printf("第5个结点的父结点：%d \n",father.val);
    };

    int level = GetNodeLevel(10);
    printf("第10个结点的层次：%d \n",level);


    return 0;
}

//结果：
第6个结点没有右孩子
第6个结点的左孩子：12 
第5个结点的父结点：2 
第10个结点的层次：4 

7.4、二叉树的链式存储

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

#define MaxSize 100
#define ElemType int
#define boolean int
#define true 1
#define false 0

typedef struct LinkTree{
    ElemType data;
    struct LinkTree *lchild,*rchild;
}*LinkTree,TreeNode;

//初始化一颗二叉树
boolean InitTree(LinkTree *root,ElemType data){
    *root = (LinkTree)malloc(sizeof(TreeNode));
    if(root == NULL) return false;
    (*root)->data = data;
    (*root)->lchild = NULL;
    (*root)->rchild = NULL;
    return true;
}

//添加一个左孩子
boolean AddLeftChild(ElemType data,TreeNode *Node){
    TreeNode *lchild = (TreeNode *)malloc(sizeof(TreeNode));
    if(lchild == NULL) return false;
    lchild->data = data;
    lchild->lchild = NULL;
    lchild->rchild =NULL;
    Node->lchild = lchild;
    return true;
}

//添加一个右孩子
boolean AddRightChild(ElemType data,TreeNode *Node){
    TreeNode *right = (TreeNode *)malloc(sizeof(TreeNode));
    if(right == NULL) return false;
    right->data = data;
    right->lchild = NULL;
    right->rchild =NULL;
    Node->rchild = right;
    return true;
}

测试

int main(){
    LinkTree root;
    InitTree(&root,1);
    AddLeftChild(2,root);
    AddRightChild(3,root);

    printf("根结点的值为：%d \n",root->data);
    printf("根结点的左孩子的值为：%d \n",root->lchild->data);
    printf("根结点的右孩子的值为：%d \n",root->rchild->data);
}

//结果：
根结点的值为：1 
根结点的左孩子的值为：2 
根结点的右孩子的值为：3