4.2 二叉树的概念（p105）

4.2.2 二叉树的存储结构（p108）

2.链式存储结构 结点类型定义

typedef struct BiTNode {                //链式二叉树定义
    ElemType data;                        //数据域
    struct BiTNode *lchild, *rchild;    //左、右孩子指针
} BiTNode, *BiTree;

4.3 二叉树的遍历和线索二叉树（p114）

1.先序遍历
void PreOrder(BiTree T) {
    //递归前序遍历
    if (T != NULL) {
        visit(T);                //访问根结点
        PreOrder(T->lchild);    //递归遍历左子树
        PreOrder(T->rchild);    //递归遍历右子树
    }
}
2.中序遍历
void InOrder(BiTree T) {
    //递归中序遍历
    if (T != NULL) {
        InOrder(T->lchild);        //递归遍历左子树
        visit(T);                //访问根结点
        InOrder(T->rchild);        //递归遍历右子树
    }
}
3.后序遍历
void PostOrder(BiTree T) {
    //递归后序遍历
    if (T != NULL) {
        PostOrder(T->lchild);    //递归遍历左子树
        PostOrder(T->rchild);    //递归遍历右子树
        visit(T);                //访问根结点
    }
}

4.递归算法和非递归算法的转换

void InOrder2(BiTree T) {
    //二叉树中序遍历的非递归算法，算法需要借助一个栈
    InitStack(S); BiTree p = T;    //初始化栈；p是遍历指针
    while (p||!IsEmpty(S)) {    //栈不空或p不空时循环
        if (p) {                //根指针进栈，遍历左子树
            Push(S,p);            //每遇到非空二叉树先向左走
            p = p->lchild;
        }
        else {                    //根指针退栈，访问根结点，遍历右子树
            Pop(S,p); visit(p); //退栈，访问根结点
            p = p->rchild;        //再向右子树走
        }
    }
}

5.层次遍历

void LevelOrder(BiTree T) {
    //层次遍历
    InitQueue(Q);                 //初始化辅助队列
    BiTree p;
    EnQueue(Q,T);                 //将根结点入队
    while (!IsEmpty(Q)) {         //队列不空循环
        DeQueue(Q,p);             //队头元素出队
        visit(p);                 //访问当前p所指向结点
        if (p->lchild!=NULL)
            EnQueue(Q,p->lchild);//左子树不空，则左子树入队列
        if (p->rchild!=NULL)
            EnQueue(Q,p->rchild);//右子树不空，则右子树入队列
    }
}

4.3.2 线索二叉树（p117）

1.线索二叉树的基本概念 结点类型定义

typedef struct ThreadNode {
    //线索二叉树定义
    ElemType data;            //数据元素
    struct ThreadNode *lchild, *rchild;    //左、右孩子指针
    int ltag, rtag;            //左、右线索标志
} ThreadNode, *ThreadTree;

2.线索二叉树的构造 通过中序遍历对二叉树线索化的递归算法

void InTread(ThreadTree &p,ThreadTree &pre) {
    //中序遍历对二叉树线索化的递归算法
    if (p!=NULL) {
        InTread(p->lchild, pre);        //递归，线索化左子树
        if (p->lchild == NULL) {        //左子树为空，建立前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre!=NULL && pre->rchild == NULL) {
            pre->rchild = p;            //建立前驱结点的后继线索
            pre->rtag = 1;
        }
        pre = p;                        //标记当前结点成为刚刚访问过的结点
        InTread(p->rchild, pre);        //递归，线索化右子树
    }//if{p!=NULL}
}

通过中序遍历建立中序线索二叉树线的主过程算法
void CreateInThread(ThreadTree T) {
    //中序遍历建立中序线索二叉树
    ThreadTree pre = NULL;
    if (T!=NULL) {                //非空二叉树，线索化
        InTread(T, pre);        //线索化二叉树
        pre->rchild = NULL;        //处理遍历的最后一个结点
        pre->rtag = 1;
    }
}

3.线索二叉树的遍历

(1)求中序线索二叉树中序序列下的第一个结点
ThreadNode *Firstnode(ThreadTree p) {
    //求中序线索二叉树中序序列下的第一个结点
    while (p->ltag == 0)
        p = p->lchild;        //最左下结点(不一定是叶结点)
    return p;
}
(2)求中序线索二叉树中结点p在中序序列下的后继结点
ThreadNode *Nextnode(ThreadNode *p) {
    //求中序线索二叉树中结点p在中序序列下的后继结点
    if (p->rtag == 0)
        return Firstnode(p->rchild);
    else
        return p->rchild;    //rtag==1直接返回后继线索
}
(1-1)求中序线索二叉树中序序列下的最后一个结点
ThreadNode *Lastnode(ThreadTree p) {
    //求中序线索二叉树中序序列下的最后一个结点
    while (p->rtag == 0)
        p = p->rchild;
    return p;
}
(2-1)求中序线索二叉树中结点p在中序序列下的前驱结点
ThreadNode *Prenode(ThreadNode *p) {
    //求中序线索二叉树中结点p在中序序列下的前驱结点
    if (p->ltag == 0)
        return Lastnode(p->lchild);
    else
        return p->lchild;
}
(3)不带头结点的中序线索二叉树的中序遍历
void InOrder(ThreadTree T) {
    //不带头结点的中序线索二叉树的中序遍历
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
        visit(p);
}

4.4 树、森林（p142）

4.4.1 树的存储结构（p142）

1.双亲表示法 结点类型定义

#define MAX_TREE_SIZE 100    //树中最多结点数
typedef struct {            //树的结点定义
    ElemType data;            //数据元素
    int parent;                //双亲位置域
} PTNode;
typedef struct{                //树的类型定义
    PTNode nodes[MAX_TREE_SIZE];//双亲表示
    int n;                    //结点数
}PTree;

3.孩子兄弟表示法 结点类型定义

typedef struct CSNode{
    ElemType data;                   //数据域
    struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;

4.4.4 树的应用——并查集（p145）

并查集的结构定义

#define SIZE 100
int UFSets[SIZE]；            //集合元素数组(双亲指针数组)

并查集的初始化操作(S即为并查集)

void Initial(int S[]) {
    for (int i = 0; i < MaxSize; i++)   //每个自成单元素集合
        S[i] = -1;
}

Find操作（函数在并查集S中查找并返回包含元素x的树的根）

int Find(int S[], int x) {
    while (S[x] >= 0)        //循环寻找x的根
        x = S[x];
    return x;                //根的S[]小于0
}

Union操作（函数求两个不相交子集合的并集）

void Union(int S[], int Root1, int Root2) {
    //Root1与Root2不同并且表示子集合的名字
    S[Root2] = Root1;        //将根Root2连接到另一根Root1下面
}

4.5 树与二叉树的应用（p153）

4.5.1 二叉排序树（p153）

2.二叉排序树的查找 二叉排序树的非递归查找算法

BSTNode *BST_Search(BiTree T, ElemType key, BiTNode *&p) {
//查找函数返回指向关键字值为key的结点指针，若不存在，返回NULL
    p = NULL;//p指向被查找结点的双亲结点，用于插入删除操作
    while (T != NULL && key != T->data) {
        p = T;
        if (key < T->data)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

3.二叉排序树的插入

int BST_Insert(BiTree &T, KeyType k) {
//在二叉排序树T中插入一个关键字为k的结点
    if (T == NULL) {                //原树为空，新插入的记录为根结点
        T = (BiTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;                    //返回1，表示成功
    }
    else if (k == T->key)            //树中存在相同关键字的结点
        return 0;
    else if (k < T->key)            //插入到T的左子树中
        return BST_Insert(T->lchild, k);
    else                            //插入到T的右子树中
        return BST_Insert(T->rchild, k);
}

4.二叉排序树的构造

void Creat_BST(BiTree &T, KeyType str[], int n) {
//用关键字数组str[]建立一个二叉排序树
    T = NULL;                    //初始时bt为空树
    int i = 0;
    while (i < n){                //依次将每个元素插入
        BST_Insert(T, str[i]);
        i++;
    }
}