树的基本概念

(1) 树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。
(2) 空集合也是树，称为空树。空树中没有节点；
(3) 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
(4) 节点的度：一个节点含有的子节点的个数称为该节点的度；
(5) 叶节点或终端节点：度为0的节点称为叶节点；
(6) 非终端节点或分支节点：度不为0的节点；
(7) 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
(8) 兄弟节点：具有相同父节点的节点互称为兄弟节点；
(9) 树的度：一棵树中，最大的节点的度称为树的度；
(10) 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
(11) 树的高度或深度：树中节点的最大层次；
(12) 节点的祖先：从根到该节点所经分支上的所有节点；
(13) 子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
(14) 森林：由棵互不相交的树的集合称为森林。

二叉树

(1) 二叉树的定义及其主要特征
a. 二叉树的基本形态：空二叉树、单节点二叉树、左子树、右子树
b. 性质：
[1] 在非空二叉树中，第i层上至多有2^(i-1) 个结点。
[2] 深度为k的二叉树至多有2^k - 1个结点 // 二叉树的边数等于节点数n-1
[3] 对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
[4] n个结点的完全二叉树深度为：log2(n)向下取整 + 1 //每个节点的父节点是p/2下取整
[5] 二叉树的堆式存储: 节点p的左儿子：2x，右儿子：2x+1
c. 两种特殊的二叉树
[1] 满二叉树：一颗深度为k且有2^k-1个结点的二叉树
[2] 如果深度为k,有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树
(2) 二叉树的顺序存储结构和链式存储结构
(3) 二叉树的遍历
a. 前序遍历
b. 中序遍历
c. 后序遍历
d. 根据前序 + 中序重建二叉树（AcWing 18)
(4) 线索二叉树的基本概念和构造
对二叉树节点的指针域做如下规定：
a. 若节点有左孩子，则Lchild指向左孩子，否则指向直接前驱；右孩子同理；
b. 增加两个标志域，Ltag表示指向的是子节点还是前驱；Rtag同理
c. 指向前驱和后继的指针叫做线索。按照某种次序遍历，加上线索的二叉树称之为线索二叉树

树、森林

(1) 树的存储结构
a. 只存父节点
b. 邻接表存储所有子节点
c. 左儿子右兄弟
(2) 森林F与二叉树T的转换
a. 原树中叶子节点数 = 转换后的树中有右儿子的节点数 + 1
b. F的前序遍历就是T的前序遍历
c. F的后序遍历就是T的中序遍历
(3) 树和森林的遍历
a. 前序遍历
b. 后序遍历
4. 考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4
5. 押题：AcWing 18、AcWing 19

代码题

typedef struct BiTNode{
    Elemtype data; // 数据域
    struct BiTNode *lchild, //左孩子指针域
                   *rchild; // 右孩子指针域
// 结构体名,结构体指针指向根节点
}BiTNode,*BiTree;


void visit(BiTNode *node){
    cout << node->data << endl;
}
// PLR
void preOrder(BiTree T){
    if(T != NULL){ 
        visit(T);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}
// LPR
void inOrder(BiTree T){
    if(T != NULL){ 
        inOrder(T->lchild);
        visit(T);
        inOrder(T->rchild);
    }
}

// LRP
void postOrder(BiTree T){
    if(T != NULL){ 
        postOrder(T->lchild);
        postOrder(T->rchild);
        visit(T);
    }
}

typedef struct BiTNode{
    Elemtype data; // 数据域
    struct BiTNode *lchild, //左孩子指针域
                   *rchild; // 右孩子指针域
// 结构体名,结构体指针指向根节点
}BiTNode,*BiTree;

// 二叉树的奇偶层Z向遍历
void zigzagLevelOrder(BiTree root){
    if(root == NULL) return;

    BiTree stack[MaxSize]; // 定义栈
    int top;
    BiTree queue[MaxSize]; // 定义队列
    int front = -1,rear = -1;

    queue[++ rear] = root; // 根入队
    int countL = 0;        // 层次

    while(rear > front){ // 队列非空
        countL ++; // 层数 + 1
        top = -1;  // 栈设置为空
        int curSize = rear - front; // 当前队列中元素的个数:同一层的

        while(curSize -- > 0){
            BiTNode *aux = queue[ ++ front];

            stack[++ top] = aux; // 入栈

            if(aux -> lchild != NULL) // 入队孩子
                queue[++ rear] = aux->lchild;
            if(aux->rchild != NULL)
                queue[++ rear] = aux->rchild;
        }
        if(countL % 2 == 0){
            while(top != -1) cout << stack[top --]->data << " ";
        }else {
            int idx = 0;
            while(index <= top) cout << stack[index ++]->data << " ";
        }
        cout << ",";
    }
}

3.设置一个算法将二叉树的叶子结点按照从左到右的顺序连成一个单链表，表头指针为head,二叉树按照二叉链表方式存储，链接时用叶节点的右指针域来存放单链表指针

思想：中序遍历
1.第一个叶子节点由head指向
2.后面指针curLeaf记录当前最新叶子，当出现新的叶子节点时，将curLeaf的右孩子指向这个新出现的叶子，并更新curleaf
3.直到遍历完成

BiTNode *head = NULL, // 链表头[不含头结点]
        *curleaf = NULL; // 指向当前访问的叶子结点

void stringLeaves(BiTree T){
    if(T == NULL) return; // 空树,没有叶子
    stringLeaves(T->lchild); // 在左子树进行串连

    if(!T->lchild && !T->rchild){ // 当前结点是叶子结点
        if(curLeaf == NULL)       // 第一个叶子结点: 设置head
            head = T;
        else
            curLeaf->rchild = T;
        curLeaf = T;              // 更新当前叶子结点
    }

    stringLeaves(T->right);
}