基础概念

1. 结点：数据结构的基本组成单位
2. 树：n个点的有限集合，n=0的树为空树，在任意非空树中：
   a. 有且仅有一个根节点
   b. n>1时其他节点可以分为m个互不相交的集合，其中每个集合本身有时一棵树，同时为根的子树，如果集合发生相交，则形成一张图。
3. 度：图中有入度和出度，在树中，度数为指向子节点的数量
4. 结点关系：
   a. 父节点（双亲节点）：当前结点向上指向的结点，仅有一个
   b. 子节点（孩子结点）：当前结点向下指向的结点，有多个
   c. 兄弟节点：具有同一个父节点
5. 叶子结点：无子节点的结点
6. 树的深度（节点层次）：如图所示，最大的层次即为树的深度

二叉树

在上述定义的基础上，一个根节点做多仅有两个子节点的树，称为二叉树
二叉树有左子树和右子树，二者顺序不能颠倒
二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

二叉树的特点：

每个节点最多有两颗子树
左右子树是由顺序的（不同的遍历方式会得到不同的结果）
即是包含空节点，也要明确顺序

二叉树的性质：

1. 第i层上最多有2^(i-1)个结点
2. 深度为k的二叉树最多有(2^k)-1个结点
3. n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数
4. 在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。
5. 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性
   (1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
   (2) 若 2*i>n，则该结点无左孩子， 否则，编号为 2*i 的结点为其左孩子结点；
   (3) 若 2*i+1>n，则该结点无右孩子结点， 否则，编号为 2*i+1 的结点为其右孩子结点。

特殊的树：

斜树，只有左子树（左斜树）或者只有右子树（右斜树）的二叉树
满二叉树，叶子结点均在同一层上，并且其余结点均具有左右节点，因此相同深度的二叉树，满二叉树结点最多，叶子最多
完全二叉树，满二叉树的叶子结点从右向左删除，即形成完全二叉树，满足以下几点
叶子结点仅出现在最下层和次下层，且最下层叶子结点在左边，次下层叶子结点在右边
叶子结点在每一层一定连续
如果节点度数为1则只有左子树没有右子树
同样节点数量的二叉树，完全二叉树深度最小
满二叉树一定是完全二叉树，反之不然

存储方式

顺序存储（指针模拟）

利用数组下标模拟树的节点坐标；
根据二叉树的性质，假定一个节点下标为i，则其父亲节点为i/2，其左节点为i*2，右节点为i*2+1；
但也正因如此，只有当树为完全二叉树的时候才能填数组，其他情况会有数组中存放空节点。
该种存储方式主要用在堆中。

二叉链表

通过链式存储，通过一个数据域两个或三个（包含父指针）指针域构成一个节点，过程类似链表的插入。
结点的定义：

struct node{
    int data;
    node *l,*r;
    node *h;//指向父结点
}

使用数组模拟的方式较为简单再次就不赘述了，主要以链式存储为进行介绍。

二叉树的遍历：

前序遍历
中序遍历
后序遍历
层序遍历
所谓前中后序实际上就遍历到父节点的顺序，前序为父-左-右，中序为左-父-右，后序为左-右-父。
这三种不同的遍历序列，可以建出相同的树。给定中序遍历序列，另外再给出前序或后序遍历的序列即可确定一颗二叉树。
层序遍历即是按照一层一层的顺序进行，就是对树进行了一次BFS

二叉树的建立：

这里使用“,”表示空节点。

struct node{
    int data;
    node *l,*r;
}
node* buildtree(node *root)
{
    if(a[cnt]!=',')
    {
        root=new node;
        root->data=a[cnt++];
        root->l=bulidtree(root->l);
        root->r=bulidtree(root->r);//前序遍历序列生成的树。
    }else {
        root=NULL;
        cnt++;
    }
    return root;
}

如果想根据其他遍历序列建树可以：
中序遍历

node* buildtree(node *root)
{
    if(a[cnt]!=',')
    {
        root=new node;
        root->l=bulidtree(root->l);
        root->data=a[cnt++];
        root->r=bulidtree(root->r);
    }else {
        root=NULL;
        cnt++;
    }
    return root;
}

后序遍历
node* buildtree(node *root)
{
    if(a[cnt]!=',')
    {
        root=new node;
        root->l=bulidtree(root->l);
        root->r=bulidtree(root->r);
        root->data=a[cnt++];
        }else {
        root=NULL;
        cnt++;
    }
    return root;
}

树的遍历的实现：

前中后序

如果已经建好了一棵树，想要得到他的三种序列，可以：

void preorder(node root)
{
    if(root)
    {
        cout<<data; preorder(root->l);
        preorder(root->r);
    }
}

void midorder(node root)
{
    if(root)
    {
        midorder(root->l);
        cout<data; midorder(root->r);
    }
}

void postorder(node root)
{
    if(root)
    {
        cout<data; postorder(root->l);
        postorder(root->r);
    }
}

层序遍历：

一般是一个简单的BFS，需要借助到队列；

struct node{
    int data;
    node *l,*r;
}
queue <node*> q;
q.push(&root);
while(!q.empty())
{
    node *t;
    t=q.front();
    cout<data; q.pop() if(t->l)
    q.push(t->l);
    if(t->r)
    q.push(t->r);
}

根据不同遍历序列生成一棵树

根据前序或后序序列找到根节点；
找到根节点后，在中序序列找到该节点；
通过中序序列重新在对左右子树进行上述操作（递归）
结束条件是定位出的根节点是当前序列中的唯一一个

先序和中序

string pre,mid;
struct node
{
    char data;
    node *l,*r;
};

node* build(int f,int l,int r,node* root)
{
    int i=l;
    while(pre[f]!=mid[i])
    {
        i++;
    }
    root=new node;
    root->data=mid[i];
    if(l<=i-1) 
    { 
        root->l=build(f+1,l,i-1,root->l);
    }else root->l=NULL;
    if(i+1<=r) 
    { 
        root->r=build(f+i-l+1,i+1,r,root->r);
    }else root->r=NULL;
    return root;
}

后序和中序

后序和先序类似，区别在与递归时后序序列中根节点的下标值，

node* build(int f,int l,int r)
{
    int i=l;
    while(post[f]!=mid[i])
    {
        i++;
    }
    node *root=new node;
    root->data=mid[i];
    if(l<=i-1) 
    { 
        root->l=build(f-(r-i+1),l,i-1);
    }else root->l=NULL;
    if(i+1<=r) 
    { 
        root->r=build(f-1,i+1,r);
    }else root->r=NULL;
    return root;
}