数据结构笔记——二叉存储结构

川长思鸟来 2023-02-13 03:17 179阅读 0赞

**目录**

一、二叉树的顺序存储

二、二叉树的链式存储

三、总结

## **一、二叉树的顺序存储** ##

#define MaxSize 100
    struct TreeNode{
        ElemType value;    //结点中的数据元素
        bool isEmpty;    //结点是否为空
    };
    TreeNode t[MaxSize];

定义一个长度为MaxSize的数组t,按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点

![20200526211221193.png][]

几个重要常考的基本操作：

![20200526211345406.png][]

若完全二叉树中共有n个结点，则

![20200526211451251.png][]

若不是完全二叉树，依次按层序将各节点顺序存储，无法从结点编号反映出结点间的逻辑关系

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

![20200526211909592.png][]

![20200526211937743.png][]

## **二、二叉树的链式存储** ##

typedef struct BiTNode{
        ElemType data;
        struct BiTNode *lchild,rchild;
    }BiTNode,*BiTree;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]

n个结点的二叉链表共有n+1个空链域，可用于构造线索二叉树

struct ElemType{
        int value;
    };
    typedef struct BiTNode{
        ElemType data;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    //定义一棵空树
    BiTree root = NULL;
    
    //插入根节点
    root = (BiTree)malloc(sizeof(BiTNode));
    root->data = {1};
    root->lchild = NULL;
    root->rchild = NULL;
    
    //插入新结点
    BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
    p->data = {2};
    p->lchild = NULL;
    p->rchild = NULL;
    root->lchild = p; //作为根节点的左孩子

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

思考：

如何找到指定结点p的父节点？

只能从根开始遍历寻找

typedef struct BiTNode{
        ElemType data;
        struct BiTNode *lchild,*rchild;
        struct BiTNode *parent;  //父节点指针  三叉链表——方便找父节点
    }BiTNode,*BiTree;

## **三、总结** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]

[20200526211221193.png]: https://img-blog.csdnimg.cn/20200526211221193.png
[20200526211345406.png]: https://img-blog.csdnimg.cn/20200526211345406.png
[20200526211451251.png]: https://img-blog.csdnimg.cn/20200526211451251.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526211757202.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200526211909592.png]: https://img-blog.csdnimg.cn/20200526211909592.png
[20200526211937743.png]: https://img-blog.csdnimg.cn/20200526211937743.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020052621204911.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200526212822121.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200526213207229.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70