顺序存储

参照树概念（完全二叉树的性质）

孩子编号i，双亲则为⌊i/2⌋；双亲编号i（设左右孩子均有），左孩子2i，右孩子 2i+1。

阿Q注：此处的编号从1开始

因此呢，先把树通过添加无意义值结点改成完全二叉树，然后存入数组中（此时数组下标建议从1开始，不然还需修改孩子和双亲间的编号关系）。

阿Q想的是这种方式蛮好的，很容易找到通过孩子找双亲或者通过双亲找孩子，但是以下这个情况怎么办呢？

当二叉树结点较为稀疏时，数组也将是稀疏的（空间利用率低）。

算法题

已知一颗二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为 i 和 j 的两个结点的最近的公共祖先结点。

int find_ancestor(int i, int j){
    while(i != j){
        if(i > j) i = i/2;
        else j = j /2;
    }
    return i;
}
// ez，顺序存储找公共祖先确实方便

链式存储

二叉链表

结点结构： lchild + data + rchild

typedef int ElemType;

typedef struct BtNode
{
    /* data */
    ElemType data;
    struct BtNode *lchild, *rchild; 
}BtNode,*Btree;

使用

#include "BTree.h"
#include<stdio.h>

int main(){
    BtNode Root;
    Root.data = 10;
    Btree t = &Root;
    
    BtNode A1;
    A1.data = 2;

    Root.lchild = &A1;
    Root.rchild = NULL;

    printf("%d",t->lchild->data);
    return 0;
}

25-2-27更新：

#pragma once
typedef struct BtNode
{
    /* data */
    BtElemtype data;
    struct BtNode *lchild, *rchild; 
    BtNode(BtElemtype x): data(x), lchild(nullptr), rchild(nullptr){}
}BtNode,*Btree;

// 使用
int main()
{
    Btree Root = new BtNode('A');
    Root->lchild = new BtNode('B');
    Root->rchild = new BtNode('C');
    Root->lchild->lchild = new BtNode('D');
    Root->lchild->rchild = new BtNode('E');
    Root->lchild->lchild->lchild = new BtNode('F');
}

n个结点的二叉链表中，有 2n – (n – 1) = n + 1 个空指针，后续用这些空指针来组成线索链表。

三叉链表

就是多了个指向双亲的指针

结点结构： lchild + data + rchild + parent

---

25-3-6 新增 – 静态链表表示法

物理结构是数组，但是使用了链表的思想，如图：

// 结点
typedef struct
{
    /* data */
    BtElemtype data;
    int lchild, rchild;
}BtNode;

// #define MAXNodeSize 100
// 静态链表
typedef struct
{
    /*data*/
    // BtNode T[MAXNodeSize];   // 静态存储
    BtNode *T;  // 动态存储，初始化分配
    int n;  // 记录节点数
    int r;  // 记录根节点的下标
}Btree;

此外当然可以在节点内新增数据成员 parent（记录双亲结点下标），思想借鉴树存储结构