树和二叉树相关练习

1.二叉树的顺序存储

#define MaxSize 100
struct TreeNode {
    ElemType value; //结点中的数据元素
    bool isEmpty;   //结点是否为空
};

TreeNode t[MaxSize];

for (int i = 0; i < MaxSize; i++) {
    t[i].isEmpty = true;
}

2.二叉树的链式存储

struct ElemType {
    int value;
};

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//定义一棵空树
BiTree root = NULL;

//插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root->data. = { 1 };
root->lchild = NULL;
root->rchild = NULL;

//插入新结点
BiTNode * p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = { 2 };
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;  //作为根节点的左孩子

3.求树的深度

int treeDepth(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    else {
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        //树的深度=Max(左子树深度，右子树深度)+1
        return l > r ? l + 1 : r + 1;
    }
}

4.层次遍历

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

5.二叉树的链式储存

//二叉树的结点(链式存储)
typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//链式队列结点
typedef struct LinkNode {
    BiTNode * data;
    struct LinkNode *next;
}LinkNode;

typedef struct {
    LinkNode *front, *rear;  //队头队尾
}LinkQueue;

6.孩子表示法（顺序+链式存储）

struct CTNode {
    int child;  //孩子结点在数组中的位置
    struct CTNode *next; //下一个孩子
};

typedef struct {
    ElemType data;
    struct CTNode *firstChild; //第一个孩子
} CTBox;

typedef struct {
    CTBox nodes[MAX_ TREE_ SIZE];
    int n, r;  //结点数和根的位置
} CTree;

7.中序线索化

//线索二叉树结点
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;   //左、右线索标志
}ThreadNode, *ThreadTree;

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T) {
    if (T != NULL) {
        InThread(T->lchild); //中序遍历左子树
        visit(T);            //访问根节点
        InThread(T->rchild); //中序遍历右子树
    }
}
void visit(ThreadNode *q) {
        if (q->lchild == NULL) {//左子树为空，建立前驱线索
            q->lchild = pre;
            q->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = q; //建立前驱结点的后继线索
            pre->rtag = 1;
        }
        pre = q;
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T) {
    pre = NULL;        //pre初始为NULL
    if (T != NULL) {   //非空二叉树才能线索化
        InThread(T);   //中序线索化二叉树
        if (pre->rchild == NULL)
            pre->rtag = 1;  //处理遍历的最后一个结点
    }
}

//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;

8.先序线索化

//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T) {
    if (T != NULL) {
        visit(T);          //先处理根节点
        if (T->ltag == 0)  //lchild不是前驱线索，避免爱的魔力转圈圈
            PreThread(T->lchild);
        PreThread(T->rchild);
    }
}
void visit(ThreadNode *q) {
    if (q->lchild == NULL) {//左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre - > rchild == NULL) {
        pre->rchild = q; //建立前驱结 点的后继线索
        pre->rtag = 1;
    }
    pre = q;
}

//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre = NULL;

9.后续线索化

//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre = NULL;

//后序线索化二叉树T
void CreatePostThread(ThreadTree T) {
    pre = NULL;       //pre初始为NULL
    if (T != NULL) {  //非空二叉树才能线索化
        InThread(T);  //中序线索化二叉树
        if (pre->rchild == NULL)
            pre->rtag = 1; //处理遍历的最后一个结点
    }
}

//后遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T) {
    if (T!= NULL) {
        PostThread(T->lchild);  //后序遍历左子树
        PostThread(T->rchild);  //后序遍历右子树
        visit(T);  //访问根节点
    }
}
void visit(ThreadNode *q) {
    if (q->lchild == NULL) { //左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = q;  //建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;
}

10.中序遍历的后继结点和前驱结点

// 找到以p为根的子树中，第一个被中序遍历的结点 
ThreadNode* FirstNode(ThreadNode *p) 
{
    while(0 == p->ltag){ // 循环找到最左下结点 
        p = p->lchild;
    }
    return p;
}
// 中序线索二叉树中找到结点p的后继结点 
ThreadNode *NextNode(ThreadNode *p) 
{
    if(0 == p->rtag){
        // 返回右子树中的最左下结点 
        return FirstNode(p->rchild);
    }
    else{
        return p->rchild; // rtag == 1 直接返回后继线索 
    }
}
// 对中序线索二叉树进行中序遍历（非递归算法） 
void InOrder(ThreadNode *T) 
{
    for(ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)){
        PrintNode(p);
    }
}



// 找到以p为根的子树中，最后一个被中序遍历的点 
ThreadNode* LastNode(ThreadNode *p)
{   
    // 循环找到最右下结点（不一定是叶节点） 
    while(0 == p->rtag){
        p = p->rchild;
    }
    return p; 
}
// 在中序线索二叉树中找到p的前驱 
ThreadNode* PreNode(ThreadNode *p)
{ 
    if(p->ltag == 0){  // 返回左子树中最右下结点 
        return LastNode(p->lchild);
    }
    else{
        return p->lchild;
    }
}
// 对线索二叉树逆向中序遍历 
void RevInOrder(ThreadNode *T)
{
    for(ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p)){
        PrintNode(p);
    }
}