数据结构—一生二 从一点构全树

树是一种常用的数据结构 用于构建一系列具有一定层次结构的逻辑对象，我们最常用到的树是二叉树。

存储二叉树
顺序存储-层次遍历，可以第一个结点空缺，保证编号一致
#define MaxSize 100
struct TreeNode{

    ElemType value;
    bool  isEmpty;

};
TreeNode t[MaxSize]

链式存储-线索二叉树

struct ElemType{
    int value;
}
typedef struct BiTNode{
    ElemType data;
    struct BitNode *lchild,*rchild;            
}BiTNode，*BitTree
BiTree root=NULL;
root=(BiTNode*)malloc(sizeof(BiTNode));
root->date={1};
root->lchild=NULL;
root->rchild=NULL;
BiTNode *p=(BiTNode*)malloc(sizeof(BiTNode));
p->date={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;     

三种遍历

根据根遍历的位置判断是哪种遍历方式

线索化——定义一个pre指针访问当前结点的前驱

先序遍历
根左右
void
线索化可以找后继

中序遍历
左根右

线索化可以找前驱后继

后序遍历可以找前驱
左右根

线索化

树与森林

树与树的存储方式

双亲表示法

顺序存储，数据+双亲下标，逆向表示，查找孩子要遍历
删除时，第一种 是删除数据后，将下标变为-1
第二种 删除数据后将最后一个挪到该位置

孩子表示法

顺序存储+链式存储
每个节点保存孩子链的表头指针

孩子兄弟表示法

应用

并查集

通过双亲表示法，记录树的每一个结点。便于查找与合并结点所在的集合树，并用-1或-n表示该集合的根节点，其中n是集合的结点数量。有时为了节省时间复杂度，直接将路径的多个双亲结点跳过，直接记录到对应的根节点，提高时间复杂度。

Find() //o(n->log2n->f(n))(最坏树高)

Union() //o(n^2->nlog2n->nf(n))