[树] 0 树总结 - 记忆版

存储结构

树

双亲表示法

typedef struct PTNode {
    Elem  data;
    int    parent;   // 双亲位置域
} PTNode;
typedef struct {
    PTNode  nodes[MAX_TREE_SIZE];
    int    r, n; //根结点的位置和结点个数
} PTree;

孩子链表

//孩子
typedef struct CTNode {
    int          child;
    struct CTNode *next;
} *ChildPtr;
//双亲
typedef struct {
    Elem    data;
    ChildPtr  firstchild; // 孩子链的头指针
} CTBox;
//树
typedef struct {
    CTBox  nodes[MAX_TREE_SIZE];
    int    n, r; // 结点数和根结点的位置
} CTree;

孩子兄弟表示法

typedef struct CSNode{
    Elem          data;
    struct CSNode  
       *firstchild,  *nextsibling;
} CSNode, *CSTree;

二叉树

顺序存储

#define  MAX_TREE_SIZE  100      
             // 二叉树的最大结点数
typedef TElemType  SqBiTree[MAX_
                TREE_SIZE];   
             // 0号单元存储根结点
SqBiTree  bt;

二叉链表

typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

三叉链表

typedef struct TriTNode { // 结点结构
    TElemType       data;
    struct TriTNode  *lchild, *rchild; //左右孩子指针
    struct TriTNode  *parent;  //双亲指针
} TriTNode, *TriTree;

双亲链表

typedef struct BPTNode { // 结点结构
    TElemType  data;
    int  *parent;     // 指向双亲的指针
    char  LRTag;    // 左、右孩子标志域
} BPTNode
typedef struct BPTree{ // 树结构
    BPTNode nodes[MAX_TREE_SIZE];
    int  num_node;  // 结点数目
    int  root;  // 根结点的位置
} BPTree

线索链表

typedef enum { Link, Thread } PointerThr;  // Link==0:指针，Thread==1:线索
typedef struct BiThrNod {
    TElemType        data;
    struct BiThrNode  *lchild, *rchild;  // 左右指针
    PointerThr         LTag, RTag;    // 左右标志
} BiThrNode, *BiThrTree;

基础内容

二叉树

1. 二叉树有左右之分
2. 完全二叉树：层次遍历的序列中，是没有NULL结点的
3. 满二叉树
   • 判断是否为完全二叉树，并获得总结点数n
   • 结点的总数n和高度h关系：$n=2^{h-1}-1$n=2h−1−1 --> 判断n+1是不是2的次方

【二叉树性质】

1. n个结点，能构造成h(n)中不同的二叉树：$h(n)=\frac{C^{n}_{2n}}{n+1}$h(n)=n+1C2nn​​
2. $n_0 = n_2 + 1$n0​=n2​+1 -->推广： $n_0=1+n_2+2n_3+...+(m-1)n_m$n0​=1+n2​+2n3​+...+(m−1)nm​(m为树的度)
   【例如】树中空指针的个数是多少？
   【技巧】把所有的空指针看作叶子结点，则原来的所有结点都成了n₂ --> 空指针n₀=树中所有结点个数+1
3. n个结点的完全二叉树高度：h = ⌊log₂n⌋+1 = ⌈log₂(n+1)⌉
4. 第i层上最多有节点2^i-1(i≥1)个结点
5. 满二叉树中前k层的结点个数为2^k-1
6. 编号为1~n的完全二叉树
   • i的爸爸=⌊i/2⌋
   • i的左孩子=2i
   • i的右孩子=2i+1