[树和二叉树](8)题集_2

33、假设用两个一维数组L[n+1]和R[n+1]作为n个结点的二叉树存储结构,L[i]和R[i]分别指示结点i(i=1,2,...,n)的左孩子和右孩子,0表示空,试写一算法判别结点u是否为结点v的双亲。

BOOL T6_33(BinTree L, BinTree R, int n, int u, int v) {
    int flag = 0;//标记
    if (!v) return FALSE;//结点为空
    
    if (L[v] == u)  return TRUE;//找到u结点,位于v的左子树
    else flag += T6_33(L, R, n, u, L[v]);//递归传入左子树判断
    
    if (R[v] == u) return TRUE;//找到u结点,位于v的右子树
    else flag += T6_33(L, R, n, u, L[v]);//递归传入右子树判断
    
    if (flag) return TRUE;//若标记为true 则返回true
    return FALSE;//否则返回false
}

34、假定用两个一维数组L[1..n]和R[1..n]作为有n个结点的二叉树的存储结构, L[i]和R[i]分别指示结点i的左孩子和右孩子,0表示空。试写一个算法,先由L和R建立一维数组T[1..n],使T中第i(i=1,2,…,n)个分量指示结点i的双亲,然后判别结点u是否为结点v的子孙。

这道题初次看的时候有点懵,但是我们一步一步来,先看对应的存储结构如下所示:

image-20210102144625660

现在直观多了,从上图我们可以得知:

  • T[ L[ i ] ] = i
  • T[ R[ i ] ] = i

    • 举个例子,当 i == 1 时候
    • T[ L[ 1 ] ] == T[2] = 1
    • T[ R[ 1 ] ] == T[ 3 ] = 1

这样我们就可以写出创建 T 数组的 循环程序:

typedef int BinTree[255];
typedef int bool;
bool T6_34(BinTree L, BinTree R, BinTree T, int n, int u, int v)
//判断结点u是否为结点v的子孙
//通过L和R创建T数组(双亲数组)
{
    for (int i = 1; L[i] || R[i]; i++)//L[i]&&R[i] :从编号为1 的根结点开始,知道最后一个叶子结点,左右子树均为空时
    {
        T[L[i]] = i;
        T[R[i]] = i;
    }
    for (int i = 1; i <= 10; i++) printf("%d ", T[i]);
    
    for (int i = v; i >= u; i = T[i])//从给定的v结点开始往双亲查找,不断迭代双亲,若等于则直接返回true
        if (i == u) return true;


    return false;
}

这道题难点就在比较绕,需要结合图像进行分析。

35、假设二叉树中左分支的标号为“0”,右分支的标号为“1”,并对二叉树增设一个头结点,令根结点为其右孩子,则从头结点到树中任一结点所经分支的序列为一个二进制序列,可认作是某个十进制数的二进制表示,例如,右图所示二叉树中,和结点A对应的二进制序列为“110”,即十进制整数6的二进制表示,已知一棵非空二叉树以顺序存储结构表示,试写以尽可能简单的算法,求出与在树的顺序存储结构中下标值为i的结点对应的十进制整数。

思路:

  • 从题意可知,我们需要从给定的结点出发查找双亲,并且判断上一结点是左孩子为1,右孩子为0,进行一个string拼接操作
  • 最好的存储结构是【孩子双亲顺序存储结构】,如下所示:
#define BINTREE_MAX 255
typedef struct BinTree {
    ElemType data;
    int rchild;
    int lchild;
    int parent;
}BinTree[BINTREE_MAX];

如下二叉树所示:

image-20210103010119208

完整算法如下所示:

int T6_35(BinTree* T, int i,int size) {
    if (i > size) exit(0);
    int pre = 0; int start = BINTREE_MAX - 1; int n = BINTREE_MAX - 1;
    
    char str[BINTREE_MAX];
    for (int p = i; p >= 1; p=T[p].parent) {
        if (pre && T[p].lchild == pre) //添加0;
            str[start] = '0';
        else if (pre && T[p].rchild == pre) //添加1
            str[start] = '1';
        pre = p;
        start--;
    }
    str[start] = '1';//虚拟头结点编号增1.

    //转换为十进制
    int num = 0;
    for (int j = start; j <=n; j++) {
        if (str[j] == '1') num += 1;
        if (j + 1 < n)num = num *= 2 ;
    }
    printf("%d", num);
    return 0;
}

运行结果:

image-20210102162127457

36、若已知两棵二叉树B1和B2皆为空,或者皆不空且B1的左、右子树和B2的左、右子树分别相似,则称二叉树B1和B2相似,试编写算法,判别给定两棵二叉树是否相似。

思路:有了广义表那一章的折磨,这道题应该很容易,就是递归判断罢了,在题目中已经给出出口了,当两棵树均为空的时候,返回true,若不为空,则判断其左右子树是否为空,当有一个为空时,返回false。

算法如下所示:

/*
typedef struct BinTreeNode {
    int data;
    struct BinTreeNode* lchild;
    struct BinTreeNode* rchild;
}*BinTree;
*/
bool SimBinTree(BinTree T, BinTree T1) {
    if (!T && !T1) {
        return true;
    }
    else if(T&&T1){
        if (SimBinTree(T->lchild, T1->lchild)) {
            return SimBinTree(T->rchild, T1->rchild);
        }
    }
    return false;
}

37、试利用栈的基本操作写出先序遍历的非递归形式算法

这题不多讲,在之前笔记中有过:

Status PreOrderT0raversal(BinTree T) {
    BinTree p = T;
    BinStack S;
    InitBinStack(&S);

    while (p || S.top > S.base) {
        while (p) {
            Visit(p);//访问根
            Push(&S, p);
            p = p->lchild;//访问左子树
        }
        Pop(&S, &p);
        p = p->rchild;//访问右子树
    }
    return OK;
}

38、写出后续遍历的非递归算法

左右根 转换为 根右左 然后 reversal 即可。算法如下所示

Status PostOrderTraversal(BinTree T) {
    BinStack S, S1;
    InitBinStack(&S);
    InitBinStack(&S1);
    BinTree p = T;
    while (p || S.top > S.base) {
        while (p) {
            Push(&S, p);
            Push(&S1, p);
            p = p->rchild;
        }
        Pop(&S, &p);
        p = p->lchild;
    }

    S1.top--;
    while (S1.base <= S1.top) {
        printf("%c", (*(S1.top))->data);
        S1.top--;
    }
    return OK;
}

39、假设在二叉链表的结点中增设两个域:双亲域(parent)以指示其双亲结点:标志域(mark取值0..2)以去区分在遍历过程中到达该结点时应继续向左或向右或访问该结点,试以此存储结构编写不用栈进行后序遍历的地推算法。

/*
typedef struct BinTreeNode {
    int data;
    struct BinTreeNode* lchild;
    struct BinTreeNode* rchild;
    struct BinTreeNode* parent;
    int mark;
}*BinTree;
*/
Status PostOrderTraversal_NSr(BinTree T) {
    BinTree p = T;
    T->parent = NULL;
    while (p) {
        if (p->mark == 0) {//访问左子树
            p->mark = 1;
            if(p->lchild)
                p = p->lchild;
        }
        else if (p->mark == 1) {
            p->mark = 2;
            if (p->rchild)
                p = p->rchild;
        }
        else {
            Visit(p);
            p->mark = 0;
            p = p->parent;
        }
    }
    return OK;
}

这题我一直在访问左子树和右子树的标记哪儿琢磨,没想到看到答案后程序那么简单,我们需要记住以下几个点:

  • 在后序遍历中,因为顺序是 左右根 则我们需要在先将左右子树全部遍历完之后最后访问根结点
  • 从左子树返回到根,标记为1
  • 若标记为1,则访问其右子树
  • 从右子树返回到根,标记为2
  • 若结点标记为2,则访问该结点(恢复0)是为了进行下一次遍历,访问其双亲

40、若在二叉链表的结点中只增设一个双亲域以指示其双亲结点,则在遍历过程中能否不设栈?试以此存储结构编写不设栈进行中序遍历的递推形式的算法

思路:中序遍历的顺序是 左根右 根据这个顺序 先遍历其左子树,直到左子树为空的时候 访问其根结点 然后遍历其右子树即可。算法如下所示:

Status InOrderTraversal_NSr(BinTree T) {
    BinTree p = T;
    while (p->lchild) p = p->lchild;//向左走到尽头
    while (p) {
        Visit(p);
        
        if (p->rchild) {//寻找中序后继:当有右子树时
            p = p->rchild;
            while (p->lchild)p = p->lchild;//后继就是在右子树中向左走到尽头
        }
        
        else if (p->parent->lchild == p) p = p->parent;//当自己是双亲的左孩子时,后继就是双亲
        //难点
        else {
            p = p->parent;
            while (p->parent && p->parent->rchild == p)p = p->parent;
            p = p->parent;
        }//当自己是双亲的右孩子时,后继就是向上返回直到遇到自己是在其左子树中的祖先
    }
}

41、编写递归算法,在二叉树中求位于先序序列中第k个位置的结点的值

思路:这题我们需要维护一个指针变量,指针内存储的值是递归的次数,然后按先序遍历访问二叉树,当递归次数为k的时候,就输出其值即可,先沿着左子树去查找,若左子树未找到,则访问其右子树,若左子树找到了,则直接返回 代码如下所示:、

bool Find_PreOredrBinTree(BinTree T, int k,int *n) {

    if (T) {
        (*n)++;
        if (*n == k) {
            printf("%c", T->data);
            return true;
        }
        else {
            if (Find_PreOredrBinTree(T->lchild, k, n)) return true;
            else return Find_PreOredrBinTree(T->rchild, k, n);
        }
    }
    return false;
}

42、编写递归算法,计算二叉树中叶子结点的数目

思路:按任意次序递归访问二叉树,当当前结点的左右子树都为空的情况下,则计数即可。代码如下所示:

int LeafNodeNumber(BinTree T) {
    if (!T->lchild && !T->rchild) return 1;
    return LeafNodeNumber(T->lchild) + LeafNodeNumber(T->rchild);
}

43、编写算法,将二叉树中所有结点的左右子树互换

思路:交换左右子树即可,代码如下所示:

Status SwapBinTreeNode(BinTree T) {
    if (T) {
        BinTree temp = T->lchild;
        T->lchild = T->rchild;
        T->rchild = temp;
        SwapBinTreeNode(T->lchild);
        SwapBinTreeNode(T->rchild);
    }
    return OK;
}

44、编写递归算法,求二叉树中元素值为x的结点为根的子树的深度

用一个标记,当遍历到x结点时候,开始计算深度即可。

int xNode_BinTreeDepth(BinTree T, int flag, ElemType x) {
    if (!T) return 0;
    int m; int n;
    if (T->data == x) flag = 1;
    if (flag) {//当结点值等于x时,开始求其深度
        m = xNode_BinTreeDepth(T->lchild, flag, x) + 1;
        n = xNode_BinTreeDepth(T->rchild, flag, x) + 1;
        if (m > n) return m;
        else return n;
    }
    else {//否则 左右子树找寻x
        int L = xNode_BinTreeDepth(T->lchild, flag, x);
        int R = xNode_BinTreeDepth(T->rchild, flag, x);
        if (L > R) return L;
        else return R;
    }
}

45、编写递归算法:对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应空间。

思路:抓重点,删去结点 操作是在结点上,跟访问一个意思,我们可以根据后序遍历的思路对结点进行访问:先删去其左子树,再删去其右子树,最后删去根,代码很简单,如下所示。

Status Delete_xRootBinTree(BinTree *T, int flag,ElemType x) {
    
    if ((*T)) {
        if (x == (*T)->data) flag = 1;

        if (flag) {
            Delete_xRootBinTree(&(*T)->lchild, flag, x);
            Delete_xRootBinTree(&(*T)->rchild, flag, x);
            free((*T));
            (*T) = NULL;
        }
        else {
            Delete_xRootBinTree(&(*T)->lchild, flag, x);
            Delete_xRootBinTree(&(*T)->rchild, flag, x);
        }
    }
    return OK;
}

46、编写复制一棵树的非递归算法

这题之前也有介绍过,也是访问结点,若T==NULL,则T1=NULL,否则跟着复制即可,我们可以根据递归算法写出非递归算法,采用任一一遍历次序进行结点的逐一复制,为了操作方便,我们最优考虑PreOrder进行复制,T1作为被复制树,他的所有过程均需模拟T的遍历过程,并且为其动态分配空间,代码如下所示:

Status CopyBinTree(BinTree T, BinTree* T1) {
    if (!T) *T1 = NULL;
    else {
        BinStack S, S1;
        InitBinStack(&S);
        InitBinStack(&S1);
        
        (*T1) = (BinTree)malloc(sizeof(struct BinTreeNode));//复制根结点
        (*T1)->data = T->data;
        
        //根结点入栈
        BinTree p = T;
        BinTree p1 = (*T1);
        Push(&S, p);
        Push(&S1, p1);
        
        while (S.base < S.top) {
            while (p->lchild) {
                p = p->lchild;//复制左子树

                p1->lchild = (BinTree)malloc(sizeof(struct BinTreeNode));
                p1 = p1->lchild;
                p1->data = p->data;
                p1->lchild = NULL;
                p1->rchild = NULL;

                Push(&S, p);//结点入栈
                Push(&S1, p1);
            }
            
            //弹出栈顶元素
            Pop(&S, &p);
            Pop(&S1, &p1);
            
            if (p->rchild) {//若存在右子树,则全部向右走一步
                p = p->rchild;
                
                //复制右子树
                p1->rchild = (BinTree)malloc(sizeof(struct BinTreeNode));
                p1 = p1->rchild;

                p1->data = p->data;
                p1->lchild = NULL;
                p1->rchild = NULL;
                
                //入栈
                Push(&S, p);
                Push(&S1, p1);
            }
        }
    }
    return OK;
}

47、编写按层次顺序(同一层次自左至右)遍历二叉树的算法

思路:层次遍历需借助Queue来实现,先将根结点入队(初始状态),在队列不为空的情况下,每次将队头元素出队,然后将其左右孩子入队即可,代码如下所示:

Status LevelTraversalBinTree(BinTree T) {
    if (!T) return NULL;
    QueueData Q;
    Queue QL;
    IniTQueue(&Q, &QL);

    BinTree p = T;
    EnQueue(&QL, p);
    printf("\n");
    while (*(QL.front)) {
        DeQueue(&QL, &p);
        printf("%c", p->data);
        if (p->lchild) EnQueue(&QL, p->lchild);
        if (p->rchild) EnQueue(&QL, p->rchild);
    }

    return OK;
}

48、已知在二叉树中,root为根结点,p和q为二叉树中两个结点,试编写求距离他们最近的共同祖先的算法

思路:我们可以从根结点出发将p和q两结点的路径存入一个表中,进而去遍历两边求得最后一个相等的结点,则是他们两最近的通过祖先。代码如下所示:

void FindNodes(BinTree T, BinTree* FindN, int i, bool* flag, BinTree N) {//求从T到p(q)的递归算法
    if (T) {
        if (T->data == N->data) {//找到符合条件的结点
            *flag = true;
            return;
        }
        FindN[i] = T;//当前结点存入路径
        FindNodes(T->lchild, FindN, i + 1, flag, N);//探寻左子树
        if (!(*flag)) {//若左子树未能找到目标结点
            FindNodes(T->rchild, FindN, i + 1, flag, N);//探寻右子树
            //FindN[i] = NULL;
        }
    }
    return;
}
BinTree ComAnceBinTree(BinTree T, BinTree p, BinTree q) {
    BinTree FindQ[100] = { NULL };//设立两个辅助数组暂存从根到p,q的路径
    BinTree FindP[100] = { NULL };
    
    bool flag = false;//标记
    FindNodes(T, FindQ, 0, &flag, q);//从根结点出发寻找结点Q的路径

    if (!flag) return NULL;
    flag = false;
    FindNodes(T, FindP, 0, &flag, p);

    int i;
    for (i = 0; FindQ[i] && FindQ[i] == FindP[i]; i++);//寻找两路径中最后一个相同的根结点
    return FindQ[i - 1];
}

49、编写算法判别给定二叉树是否为完全二叉树

思路:我们来复习下完全二叉树的定义:

如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树

  1. 如果树为空,则直接返回错
  2. 如果树不为空:层序遍历二叉树
  3. 如果一个结点左右孩子都不为空,则pop该节点,将其左右孩子入队列;
  4. 如果遇到一个结点,左孩子为空,右孩子不为空,则该树一定不是完全二叉树;
  5. 如果遇到一个结点,左孩子不为空,右孩子为空;或者(左)右孩子都为空;则该节点之后的队列中的结点都为叶子节点;该树才是完全二叉树,否则就不是完全二叉树

算法如下所示

bool ComPleteBinTree(BinTree T) {
    if (!T) return false;
    BinTree p;
    BinTree LevelArray[100];
    
    LevelArray[0] = T;//根节点入队

    int i = 0;int l = 1;int r = 2;
    bool flag = false;
    
    while (LevelArray[i]) {//根据完全二叉树性质数组模拟队列
        p = LevelArray[i];
        if (flag && (p->lchild || p->rchild)) return false;
        
        if (!p->lchild||(!p->lchild && !p->rchild) || (p->lchild && !p->rchild)) flag = true;
        
        LevelArray[l] = p->lchild;
        LevelArray[r] = p->rchild;
        i++; l += 2; r += 2;
    }

    return true;
}

50、假设以三元组(F,C,L/R)的形式输入一棵二叉树的各边(其中F表示双亲结点的表示,C表示孩子结点标识,L/R表示C为F的左孩子或右孩子),且在输入的三元组序列中,C是按层次顺序出现的,设结点的标识是字符类型,F='-' 时,C为根结点标识,若C也为'-',则表示输入结束,例如下图所示:

image-20210106170612230

思路:题目给出了一个便利 按层次顺序输入 这就代表我们可以起一个队列,将题目转换成按层次创建二叉树,下列我采用在原树中寻找F所代表的双亲结点,然后根据三元组的child标识对其左右子树链接即可,算法如下所示:

#define TRIPLESIZE_MAX 255
typedef struct TripleNode {
    char F;
    char C;
    char child;
}Triple[TRIPLESIZE_MAX];


Status VisitTriple(Triple T) {//观察三元组,用于检查
    int i = -1;
    do {
        i++;
        printf("%c,%c,%c\n", T[i].F, T[i].C, T[i].child);
        system("pause");
    } while (T[i].C != '-');
    return OK;
}
Status InitTriple(Triple T) {//初始化三元组
    char t;//消除最后一个\n,可不要
    int i = -1;
    do {
        i++;
        scanf("%c%c%c%c", &T[i].F, &T[i].C, &T[i].child, &t);
    } while (T[i].C != '-');
    VisitTriple(T);
    return OK;
}

Status FindNode(BinTree T, BinTree* p,ElemType e) {//寻找双亲结点
    if (T) {
        if (T->data == e)
            *p = T;
        else {
            FindNode(T->lchild, p, e);
            if (!p) FindNode(T->rchild, p, e);
        }
    }
    return OK;
}
Status CreateTripleBinTree(BinTree* T) {
    //通过三元组创建二叉链存储结构的二叉树
    Triple Tr;
    InitTriple(Tr);
    
    (*T) = (BinTree)malloc(sizeof(struct BinTreeNode));//创建根结点
    (*T)->lchild = NULL;
    (*T)->rchild = NULL;
    (*T)->data = Tr[0].C;
    
    BinTree p;
    int i = 1;
    while (Tr[i].C != '-') {
        FindNode(*T, &p, Tr[i].F);//寻找根结点.
        if (!p) return ERROR;//三元组序列错误
        if (Tr[i].child == 'L') {
            p->lchild = (BinTree)malloc(sizeof(struct BinTreeNode));
            p = p->lchild;
        }
        else {
            p->rchild = (BinTree)malloc(sizeof(struct BinTreeNode));
            p = p->rchild;
        }
        p->data = Tr[i].C;
        p->lchild = NULL;
        p->rchild = NULL;
        i++;
    }

    //PreOrderTraversal(*T);检查
    return OK;
}

51、编写一个算法,输出以二叉树表示的算术表达式,若该表达式中含有括号,则在输出时应添上

思路:我们先来看两张图,思路就能很清晰了,先给出一张带括号表达式 (a+b)-(c+d) 的树型结构图

image-20210107025758753

下面给出运算符优先级表

image-20210107025958120

正确的中缀表达式的树结构,其分支结点必定为运算符,而其叶子结点必定为操作数,为此我们可以写出根据中序遍历树结构输出其中缀表达式,算法如下所示:

int opIndex(char a) {//优先级定位
    if (a == '+') return 0;
    if (a == '-') return 1;
    if (a == '*') return 2;
    if (a == '/') return 3;
    if (a == '(') return 4;
    if (a == ')') return 5;
}
char PriorOP(char a, char b) {//比较两运算符优先级
    char Prior[6][6] = { '>','>','<','<','<','>',
                        '>','>','<','<','<','>',
                        '>','>','>','>','<','>',
                        '>','>','>','>','<','>',
                        '<','<','<','<','<','=',
                        '>','>','>','>','0','>', };
    int c = opIndex(a);
    int d = opIndex(b);
    return Prior[c][d];
}
bool Jdop(char a) {//判断是否为运算符
    if (a == '+' || a == '-' || a == '*' || a == '/' || a == '(' || a == ')') return true;
    return false;
}

Status Print_InOrderExression_Bit(BinTree T) {
//根据中序遍历二叉树和运算符优先级输出其中序序列
    if (!Jdop(T->data)) Visit(T);//若是操作数,则直接输出
    else {
        if (!T->lchild) return ERROR;//非操作数的叶子结点,序列错误
        //添加括号的中序遍历.
        if (Jdop(T->lchild->data) && PriorOP(T->lchild->data, T->data) == '<') {//左子树比它小,需要添加括号
            //若其左子树为运算符且其左子树优先级小于它,则需要添加括号
            printf("(");
            if (!Print_InOrderExression_Bit(T->lchild)) return ERROR;//中序递归遍历:左根(访问)右
            Visit(T);
            printf(")");
        }
        else {
            //否则不添加,正常中序递归遍历
            if (!Print_InOrderExression_Bit(T->lchild)) return ERROR;
            Visit(T);
        }
        

        //右子树与左子树相同操作
        if (!T->rchild) return ERROR;

        if (Jdop(T->rchild->data) && PriorOP(T->rchild->data, T->data) == '<') {
            printf("(");
            if (!Print_InOrderExression_Bit(T->rchild)) return ERROR;
            printf(")");
        }
        else {
            if (!Print_InOrderExression_Bit(T->rchild)) return ERROR;
        }
    }
    return OK;
}

代码看着很复杂,但是其实思路很简单,就是中序访问罢了,而且一定记住必定是一棵完满二叉树,因为运算符为分支结点,一个运算符作用与两个操作数,测试可以根据先序创建一棵二叉树,根据其输出,如下图所示:

image-20210107035541962

若是大佬有兴趣,可以写一个根据中序表达式创建二叉树的算法,联系我~万分感谢!

52、一棵二叉树繁茂度定义为各层结点数的最大值与树的高度的乘积,试写一算法,求二叉树的繁茂度

思路:答案就在题目里,高度就是深度,只不过高度是从下往上,而深度是从上往下,我们层次遍历二叉树,记录结点个数的最大值,然后返回其与深度的乘积即可。

int BinTreeDepth(BinTree T) {//求二叉树深度的递归算法
    if (!T) return 0;
    int m = BinTreeDepth(T->lchild) + 1;
    int n = BinTreeDepth(T->rchild) + 1;
    if (m > n) return m;
    else return n;
}
void Level_FindMax(BinTree T,int n,int* LeveNum) {
    //构造每层次结点个数表
    if (T) {
        LeveNum[n]++;//该层次结点个数
        Level_FindMax(T->lchild, n + 1, LeveNum);
        Level_FindMax(T->rchild, n + 1, LeveNum);
    }
    return;
}

int LushBinTree(BinTree T) {
    int dep = BinTreeDepth(T);
    int* LeveNum = (int*)malloc(sizeof(int) * (dep + 1));
    for (int i = 0; i <= dep; i++) LeveNum[i] = 0;//初始化

    Level_FindMax(T, 1, LeveNum);//构造层次结点数表

    int MaxNodes = 0;
    for (int i = 1; i <= dep; i++) 
        if (MaxNodes < LeveNum[i]) 
            MaxNodes = LeveNum[i];//求出最大结点数

    return MaxNodes * dep;
}

53、试编写算法,求给定二叉树上从根结点到叶子结点的一条其路径长度等于树的深度减一的路径(即列出从根结点到该叶子结点的结点序列,若这样的路径存在多条,则输出路径终点(叶子结点)在最左边的一条)

思路:先序遍历+递归回溯,维护一个层次数,当这个层次数 i 等于深度 n - 1 的时候, 就找到了,先序遍历就是从左到右,所以第一条即是最左边的一条,算法如下所示:

bool LeftPath(BinTree T,BinTree* Path, int i, int dep) {
    if (i == dep)
        return true;
    if (T) {
        Path[i] = T;
        if (LeftPath(T->lchild, Path, i + 1, dep) || LeftPath(T->rchild, Path, i + 1, dep))//
            //左右子树DFS,左边先执行,相当于先序遍历
            return true;
    }
    return false;
}
Status FindPath(BinTree T) {
    int dep = BinTreeDepth(T);
    printf("\n%d\n", dep);
    BinTree* Path = (BinTree*)malloc(sizeof(BinTree) * (dep + 1));
    LeftPath(T, Path, 0, dep);

    for (int i = 0; i < dep; i++) printf("%c", Path[i]->data);
    system("pause");
    return OK;
}

测试用例:ABC#DEF##G##H#IJ##K###LMN#OP##Q###R#ST#U#VW##X##Y##

测试逻辑结构图:image-20210108023455276

通过测试。

54、假设以顺序表sa表示一棵完全二叉树,sa.elem[sa.last]中存放树种各结点的数据元素,试编写算法由此顺序存储结构建立该二叉树的二叉链表。

思路:在完全二叉树中,孩子与其双亲结点 i 的关系如下:

  • 左孩子:2i
  • 右孩子:2i+1

根据上述,算法如下所示,完全二叉树按层次顺序从左到右编号,序列是连续的(中途不会出现空结点)

typedef struct saNodes {
    int* elem;
    int last;
}sanode;
Status InitSa(sanode *sa) {
    scanf("%d", &(*sa).last);
    if (!((*sa).elem = (int*)malloc(sizeof(int) * ((*sa).last + 1))))return ERROR;
    for (int i = 1; i <= (*sa).last; i++) scanf("%d", &(*sa).elem[i]);
    return OK;
}
Status CreateBinTree_saArray(BinTree *T) {
    
    sanode sa;
    if (!(InitSa(&sa))) return ERROR;
    BinTree* TA = (BinTree)malloc(sizeof(BinTree) * (sa.last + 1));
    
    for (int i = 1; i <= sa.last; i++) {//构造子树森林
        TA[i] = (BinTree)malloc(sizeof(struct BinTreeNode));
        TA[i]->data = sa.elem[i];
        TA[i]->lchild = NULL;
        TA[i]->rchild = NULL;
        int j = i / 2;
        if (j >= 1) {
            if (i == 2 * j) TA[j]->lchild = TA[i];
            else
                TA[j]->rchild = TA[i];
        }
    }
    *T = TA[1];
    return OK;
}

55、为二叉链表的结点增加DescNum域,试写一算法,求二叉树的每个结点的子孙数目存入其DescNum域,请给出算法的时间复杂度。

思路:这题我们可以使用递归实现,我初步想到的办法时间复杂度很高,想优化思路却卡壳了,后边看了下答案,才发现代码非常简单,我们先总结一下几个情况:

  • 当T为叶子结点时,其左右孩子均为空,则DescNum域为0
  • 当T不为叶子节点时,但其只有一棵子树,则其DescNum域>=1
  • 当T不为叶子节点时,且有两棵子树,则其DescNum域>=2

我们将问题规模逐渐缩小

当T为叶子结点时,左右子树均为空,子孙数为0,当T不为叶子结点时,子孙数等于其左子树加其右子树

这样我们可以得出当T为空时,返回-1(叶子结点两孩子均为空)

其子孙数目=其左孩子数目+其右孩子数目+2 算法如下所示:

int DescNum(BinTree T) {
    if (!T) return -1;
    int Des = (DescNum(T->lchild) + DescNum(T->rchild)) + 2;//精髓所在
    T->DescNum = Des;
    return Des;
}

56、试写一算法,在先序后继线索二叉树中,查找给定结点 *p 在先序序列中的后继(假设二叉树的根节点未知),并讨论实现此算法对存储结构有何要求?

思路:为了对得起这道题的难度,下列把先序线索化二叉树算法也一并给出。

BinTree TBitFindSucced(BinTree p) {//在线索二叉树中返回后继结点
    if (p) {
        if (p->ltag == List) return p->lchild;
        else return p->rchild;
    }
}

Status PreThreadtraversal(BinTree T) {//先序线索遍历二叉树
    BinTree p;
    p = T->lchild;
    while (p != T) {
        while (p->ltag == List) {
            Visit(p);
            p = p->lchild;
        }
        Visit(p);
        p = p->rchild;
    }
}
BinTree pre;
Status Threading(BinTree* T) {//先序线索化二叉树
    if ((*T)) {
        (*T)->ltag = List;
        (*T)->rtag = List;

        if (!(*T)->lchild) {
            (*T)->lchild = pre;
            (*T)->ltag = Thread;
        }
        if (!pre->rchild) {
            pre->rchild = (*T);
            pre->rtag = Thread;
        }
        pre = (*T);
        if ((*T)->ltag == List)
            Threading(&(*T)->lchild);
        if ((*T)->rtag == List)
            Threading(&(*T)->rchild);
    }
    return OK;
}
Status PreThreadBinTree(BinTree *T) {//先序线索化二叉树
    BinTree Thrs = (BinTree)malloc(sizeof(struct BinTreeNode));//增加虚结点,统一情况
    Thrs->ltag = List;
    Thrs->lchild = (*T);
    Thrs->rtag = Thread;
    Thrs->rchild = Thrs;
    pre = Thrs;
    Threading(T);
    pre->rchild = Thrs;
    pre->rtag = Thread;
    PreThreadtraversal(Thrs);
    return OK;
}
  • 在存储结构中需要添加两个标志域,用于标志左右孩子指向的是孩子还是线索,如下图所示:

image-20210109021240576

在之前学习过程中介绍过线索二叉树,传送门

57、试写一算法,在后序后继线索二叉树中,查找给定结点,*p在后续后继线索二叉树中的后继(二叉树的根节点指针并未给出)并讨论实现算法对存储结构有何要求

思路:这道题做过线索二叉树后序遍历的话就很简单,只需要知道后序中如何查找后继就行,如下所示:

  • 若结点p是二叉树的根,则其后继为空
  • 若结点p是其双亲的右孩子

    • 或是其双亲的左孩子,且其双亲没有右子树,则其后继为其双亲结点
  • 若结点p是其双亲的左孩子,且其双亲右子树,则其后继为双亲的右子树上按后序遍历列出的第一个结点(如下图所示)

image-20210109032847991

算法如下所示:

BinTree PostBitFindSucced(BinTree p) {
    if (p->rtag == Thread) return p->rchild;//p有后继线索
    if (!p->parent) return NULL;//p为根结点
    if (p == p->parent->rchild) return p->parent;//p为其双亲的右孩子
    if (p == p->parent->lchild && p->parent->rtag == Thread)
        return p->parent;//p为其双亲的左孩子且其双亲无右子树
    BinTree q = p->parent->rchild;
    while (q->ltag == List || q->rtag == List) {
        if (q->ltag == List)p = q = q->lchild;
        else q = q->rchild;
    }
    return q;
}

58、试写一算法,再中序全线索二叉树的结点 p 之下,插入一棵以结点x为根,只有左子树的中序全线索二叉树,使x为根的二叉树称为p的左子树,如果p已存在左子树,则令其称为x的右子树,完成插入后的二叉树应保持全线索化

思路:这道题我们可以画图来看看线索的变化过程,找到变化过程后就很简单了,图示如下:

我们先来看当p为根的子树有左子树时的场景:

image-20210110063417832

依照题目要求,我们可以看到P是有左子树的,则我们需要将P的左子树称为 J 的右子树,同时让J称为P的左子树,我们先不改变线索走向,来看看连接后的逻辑图,如下所示:

image-20210110064026853

从上分析可知,我们需要改变的只有一处,中序遍历顺序为:左 根 右:

  • 在P结点有左子树时候,我们只需要将X的右孩子与其连接,然后改变其中序遍历的第一个结点的前驱即可。

而当 P 结点没有左子树时,我们只需要改变 X结点左子树 中序序列 最后一个序列所在结点的后继指针,让其指向P即可。

算法如下所示:

Status xISp_Left(BinTree *p, BinTree *x) {
    if ((*p)->rtag == Thread||!(*p)->lchild) {//p的左子树为线索,代表x可以成为其左子树,
        (*p)->ltag = List;
        (*p)->lchild = *x;

        //改变x最后一结点的后继
        BinTree q = (*x);
        while (q->rchild != (*x)) {//x只有左子树,其最后一个序列一定是根
            while (q->ltag = List) q = q->lchild;
            while (q->rchild != (*x) && q->rtag == Thread) q = q->rchild;
            if (q->rchild != (*x)) q = q->rchild;
        }
        q->rchild = (*p);//改变后继
    }
    else {
        (*x)->rtag = List;
        (*x)->rchild = (*p)->lchild;
        (*p)->lchild = (*x);

        //改变其右子树中序遍历第一结点的前驱,需要指向 (*x)

        BinTree q = (*x)->rchild;
        while (q->ltag == List) q = q->lchild;
        q->lchild = (*x);
    }
    return OK;
}

测试通过

59、编写算法完成下列操作,无重复的输出以孩子兄弟链表存储的树T中所有的边,输出形式为(k1,k2),...(ki,kj),...,其中,k1和kj为树种的结点标识

思路:这是第一道关于一般树的算法题,思路其实很简单,其一个队列,将根结点加入队列中,然后以他的孩子为基准不断添加,迭代根结点与其孩子和孩子的兄弟结点输出即可,当队列为空时,即停止,如下图所示:

image-20210110085219193

算法如下所示:

/*
typedef struct TreeNode {
    int data;
    struct TreeNode* child;
    struct TreeNode* brother;
}*Tree;

Status CreateTree(Tree *T) {
//约定,采用二叉树的先序序列创建一般树,左子树为其根的孩子,右子树为其根的兄弟
    char ch;
    scanf("%c", &ch);
    if (ch == '#') *T = NULL;
    else {
        (*T) = (Tree)malloc(sizeof(struct TreeNode));
        (*T)->data = ch;
        CreateTree(&(*T)->child);
        CreateTree(&(*T)->brother);
    }
    return OK;
}
*/
//打印所有边
Status Print_RootChild(Tree T) {
    if (!T) return ERROR;
    Queue Q;
    InitQueue(&Q);
    Tree p = T;
    EnQueue(&Q, p);
    while (Q.front != Q.rear) {
        DeQueue(&Q, &p);
        Tree cd = p->child;
        while (cd) {
            if (cd->child) EnQueue(&Q, cd);
            printf("(%c,%c) ", p->data, cd->data);
            cd = cd->brother;
        }
    }
    return OK;
}

测试通过

image-20210110094541646

60、试编写算法,对一颗孩子兄弟链表表示的树统计叶子的个数

思路:遍历一遍树,当前结点没孩子的时候即计数变量加1,我们可以采用递归来实现,如下所示:

image-20210110095929776

算法如下所示:

int leafNumber(Tree T) {
    if (!T->child)return 1;
    int num = 0;
    for (Tree cd = T->child; cd; cd = cd->brother) {//横向兄搜索
        num += leafNumber(cd);//递归纵向孩子搜索
    }
    return num;
}

经典的递归

61、试编写算法,求一棵以孩子兄弟链表表示的树的度

思路:和上道题一样可以使用递归求解,孩子的兄弟个数代表着这颗子树的度,算法如下所示:

int TreeMaxDegree(Tree T) {
    if (!T->child) return 0;
    int max = 0;
    int deg = 0;
    int tem = 0;
    for (Tree p = T->child; p; p = p->brother, max++) {
        tem=TreeMaxDegree(p);
        if (deg < tem) deg = tem;
    }
    if (max < deg) max = deg;
    return max;
}

测试图例:

image-20210111021509034

62、对以孩子兄弟链表表示的树编写计算树的深度的算法

思路:还是可以用递归求解,去比较子树的深度,然后求出最大值即可

int TreeDepth(Tree T) {
    if (!T) return 0;
    int m = 0;
    int n = 0;
    for (Tree p = T; p; p = p->brother) {
        m = TreeDepth(p->child) + 1;
        if (n < m) n = m;
    }
    return n;
}

63、对以孩子链表表示的树编写计算树的深度的算法

思路:这题我感觉考的是创建,至于深度和上题思路类同,我们采用指针数组为其分配孩子链的空间即可,完整代码如下所示:

/*
typedef struct CTreeNode {
    char data;
    int ChildNumber;
    struct CTreeNode** child;//靠ChildNumBer分配孩子个数,指针数组存储孩子域
}*CTree;


//先序孩子链创建树
Status CreateCTree(CTree *T) {
    if (!((*T) = (CTree)malloc(sizeof(struct CTreeNode)))) return ERROR;
    scanf("%c,%d", &(*T)->data, &(*T)->ChildNumber);
    if((*T)->ChildNumber < 0) return ERROR;
    if (!(*T)->ChildNumber) {
        (*T)->child = NULL;
        return OK;
    }
    //按照孩子个数分配空间
    if (!((*T)->child = (CTree*)malloc(sizeof(CTree) * (*T)->ChildNumber))) return ERROR;
    for (int i = 0; i < (*T)->ChildNumber; i++)
        CreateCTree(&(*T)->child[i]);
    return OK;
}


//先序序列打印树
Status Print_CTree(CTree T) {
    if (!T) return ERROR;
    printf("%c", T->data);
    for (int i = 0; i < T->ChildNumber; i++) {
        Print_CTree(T->child[i]);
    }
    return OK;
}
*/
//深度
int CTreeDepth(CTree T) {
    if (!T) return 0;
    if (!T->ChildNumber) return 1;
    int m = 0;
    int n = 0;
    for (int i = 0; i < T->ChildNumber; i++) {
        m = CTreeDepth(T->child[i]) + 1;
        if (n < m) n = m;
    }
    return n;
}

测试图例:

image-20210111032527707

64、对以双亲表表示的树编写计算树的深度的算法

思路:如下图所示的双亲表,我们可以从末尾开始不断寻找其双亲更新最大深度,同时优化时间避免重复双亲的查找即可

image-20210111040800678

算法如下所示:

/*
#define MAXPTREE_DATASIZE 255
typedef struct PTreeDataNode {
    int parent;
    char data;
}PTreeData;//双亲表数据域结构

typedef struct PTreeNode {//双亲表
    PTreeData PTB[MAXPTREE_DATASIZE];
    int len;
}*PTree;

Status CreatePTree(PTree *PT) {//创建一个双亲表
    if (!((*PT) = (PTree)malloc(sizeof(struct PTreeNode)))) return ERROR;

    scanf("%d", &(*PT)->len);
    for (int i = 1; i <= (*PT)->len; i++) {
        scanf("%d,%c", &(*PT)->PTB[i].parent, &(*PT)->PTB[i].data);
        
        if ((*PT)->PTB[i].parent < 0) return ERROR;
        
        if (i == 1) (*PT)->PTB[i].parent = 0;//根结点双亲为1
    }
    return OK;
}
//打印此双亲表
Status Print_PTreeB(PTree PT) {
    for (int i = 1; i <= PT->len; i--)
        printf("%d,%c\n", PT->PTB[i].parent, PT->PTB[i].data);
    return OK;
}

*/
int PTreeDepth(PTree PT) {
    int dep = 0;
    int tem;
    for (int i = PT->len; i > 0; i--) {
        tem = 0;
        if ((i - 1 > 0) && PT->PTB[i].parent == PT->PTB[i - 1].parent) continue;
        for (int j = i; j >= 1; j = PT->PTB[j].parent, tem++);//寻找根结点,tem计算此结点到根的高度
        
        //更新最大高度
        if (dep < tem) dep = tem;
    }
    return dep;
}

测试通过:

image-20210111044141943

65、已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中,试编写算法建立该二叉树的二叉链表。

思路:我们需要通过[先序序列]和[中序序列]唯一确定一棵二叉树,若只给出先序序列,或只给出中序序列,将会有多种可能的二叉树结构,如下所示:

image-20210112032522761

两棵不同的二叉树,其先序序列是一样的,而基于此先序序列能创建的二叉树还有很多

通过中序序列和先序序列,我们可以唯一确定一棵二叉树的原因在于:

  • 先序序列的顺序为:根、左、右,可以确定根的位置,当前元素即为该子树的根
  • 中序序列的顺序为:左、根、右,可以看到,在根的左边为其左子树,在根的右边为其右子树

则我们可以由在先序序列中的根去中序序列中确定其位置所在,并划分其左右子树所处的序列,来进行左右子树的连接

此过程为一个递归的过程,详细如大佬在百度问答所述:

前序先访问根节点,遍历左序然后右序。中序先遍历左序然后访问根节点,遍历右序。

假设某二叉树的bai先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,其逻辑结构如图:

image-20210112033211206

分析:先序遍历序列的第一个字符为根结点。对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序遍历序列。

  • 先序:abdgcefh --> a bdg cefh
  • 中序:dgbaechf --> dgb a echf

左子树部分

得出结论:a是树根,a有左子树和右子树,左子树有bdg结点,右子树有cefh结点。

  • 先序:bdg --> b dg
  • 中序:dgb --> dg b

得出结论:b是左子树的根结点,b无右子树,有左子树。

  • 先序:dg --> d g
  • 中序:dg --> d g

右子树部分

得出结论:d是b的左子树的根结点,d无左子树,有右子树。

  • 先序:cefh --> c e fh
  • 中序:echf --> e c hf

得出结论:c是右子树的根结点,c有左子树(只有e结点),有右子树(有fh结点)。

  • 先序:fh --> f h
  • 中序:hf --> h f

得出结论:f是c的右子树的根结点,f有左子树(只有h结点),无右子树。

根据上述,我们已经可以画出此二叉树的逻辑图,但是如何通过程序创建呢?我们采用分治的思想,如同二分搜素,划定左右边界

当当前子树所在的先序序列或其中序序列左边界大于其右边界时,返回NULL,代表此位置已无子树

image-20210112035709735

中序序列确定在先序序列中所在根的左右子树,分治进行其左右子树的创建,算法如下所示:

typedef struct BinTreeNode {
    char data;
    struct BinTreeNode* lchild;
    struct BinTreeNode* rchild;
}*BinTree;


//char Pre_ch[] = "abdgcefh";//先序序列
//char In_ch[] = "dgbaechf";//中序序列
BinTree Pre_In_OrderCreateBinTree(char* Pre_ch, char* In_ch, int Pre_Start, int Pre_End, int In_Start, int In_End) {
    if (In_Start > In_End || Pre_Start > Pre_End)
        return NULL;//返回空
    BinTree p = (BinTree)malloc(sizeof(struct BinTreeNode));
    p->data = Pre_ch[Pre_Start];
    int i = In_Start;

    //在中序序列中需寻找 当前 根 结点 所在位置,并且划定左右边界
    while (i < In_End) {
        if (In_ch[i] == Pre_ch[Pre_Start]) break;
        i++;
    }

    //分治
    BinTree Lroot = Pre_In_OrderCreateBinTree(Pre_ch, In_ch, Pre_Start + 1, Pre_Start + (i - In_Start), In_Start, i - 1);
    p->lchild = Lroot;
    BinTree Rroot = Pre_In_OrderCreateBinTree(Pre_ch, In_ch, Pre_Start + (i - In_Start) + 1, Pre_End, i + 1, In_End);
    p->rchild = Rroot;
    //返回其根
    return p;
}
//先序序列创建法检查

/*char* Bit = (char*)malloc(sizeof(char) * ((2 * Tlen) + 2));
    int i = -1;*/
/*
Status PreOrder_Traversal(BinTree T,char *Bit,int* i) {
    (*i)++;
    if (!T) {
        Bit[*i] = '#';
    }
    else{
        Bit[*i] = T->data;
        PreOrder_Traversal(T->lchild, Bit, i);
        PreOrder_Traversal(T->rchild, Bit, i);
    }
    return OK;
} 
Status InOrder_Traversal(BinTree T) {
    if (T) {
        InOrder_Traversal(T->lchild);
        printf("%c", T->data);
        InOrder_Traversal(T->rchild);
    }
    return OK;
}
//凹入法打印
Status Print_BinTree(BinTree T, int n) {
    if (!T) return OK;
    Print_BinTree(T->rchild, n + 1);
    for (int i = 0; i < n; i++) printf("\t");
    if (n >= 0)
        printf("---%c\n", T->data);
    Print_BinTree(T->lchild, n + 1);
    return OK;
}
*/

测试图例:

image-20210112040119159

66、假设有n个结点的树T采用了双亲表示法,写出由此建立树的孩子兄弟链表的算法

思路:这题我们依旧可以采用分治的思想,去创建其孩子和兄弟,有双亲表我们只需要知道:

  • 孩子是其双亲域与当前结点下标相同
  • 双亲是其双亲域域当前结点的双亲域相同

同时因为递归最后会返回,需要避免重复判断出现,我们需要在当前结点的孩子或兄弟为空(未被创建)的时候递归其孩子和兄弟,算法如下所示:

/*
#define MAXPTREE_DATASIZE 255

typedef struct PTreeDataNode {
    int parent;
    char data;
}PTreeData;//双亲表数据域结构

typedef struct PTreeNode {//双亲表
    PTreeData PTB[MAXPTREE_DATASIZE];
    int len;
}*PTree;

typedef struct TreeNode {
    int data;
    struct TreeNode* child;
    struct TreeNode* brother;
}*Tree;
*/
Status PTreeCreateTree(PTree PT, Tree* T, int i, int n) {
    (*T) = (Tree)malloc(sizeof(struct TreeNode));
    (*T)->child = NULL;
    (*T)->brother = NULL;
    (*T)->data = PT->PTB[i].data;   
    for (int k = i + 1; k <= n; k++)
        if (PT->PTB[k].parent == i && !(*T)->child)//该结点的双亲域为当前结点,当前结点的孩子域未被访问
            PTreeCreateTree(PT, &(*T)->child, k, n);
    for (int j = i + 1; j <= n; j++)
        if (PT->PTB[j].parent == PT->PTB[i].parent && !(*T)->brother)
            PTreeCreateTree(PT, &(*T)->brother, j, n);//该结点的双亲域为当前结点的双亲域,当前结点的兄弟域未被访问

    return OK;
}

67、假设以二元组(F,C)的形式输入一棵树的诸边(其中 F 表示 双亲结点的标识,C表示孩子结点表示),且在输入的二元组序列中,C是按层次顺序出现的,F="-"时,C为结点表示,若C也为‘-’,则表示输入结束。例如,如下所示树的输入序列为:

image-20210113023421177

思路:这题与之前那道二叉树的题类同,看到C按层次顺序出现时,我们可以想到,当前F若不为-,则肯定与已扫描过的C相同,则我们可以采用队列的方式先迭代孩子,再迭代与其F相同的兄弟,算法如下所示:

/*#define TWOTUPMAXSIZE 255
typedef struct TwotupNode {
    char F;
    char C;
}Twotup[TWOTUPMAXSIZE];

Status CreateTwotup(Twotup *Tt) {//创建二元组
    char tem;
    int i = 0;
    while (TRUE) {
        scanf("%c%c%c", &(*Tt)[i].F, &(*Tt)[i].C, &tem);
        if ((*Tt)[i].C == '-') break;
        i++;
    }
    return OK;
}
Status Print_Ttup(Twotup Tt) {//check二元组
    int i = -1;
    do {
        i++;
        printf("%c,%c\n", Tt[i].F, Tt[i].C);
    } while (Tt[i].C != '-');
    return OK;
}

*/
Status TtCreateTree(Twotup Tt, Tree* T) {
    if (Tt[0].F != '-') return ERROR;//序列错误
    Queue Q;
    InitQueue(&Q);
    (*T) = (Tree)malloc(sizeof(struct TreeNode));
    (*T)->child = (*T)->brother = NULL;
    (*T)->data = Tt[0].C;
    Tree p = (*T);
    EnQueue(&Q, p);//根结点入队

    int i = 1;
    while (Tt[i].C != '-') {
        DeQueue(&Q, &p);//取出其双亲所在的二元组元素
        char tem = p->data;
        if (Tt[i].F == tem) {
            p->child = (Tree)malloc(sizeof(struct TreeNode));//迭代其孩子
            p = p->child;
            p->data = Tt[i].C;
            p->child = p->brother = NULL;
            EnQueue(&Q, p);//入队
            i++;
            while (Tt[i].C != '-' && Tt[i].F == tem) {//迭代其兄弟
                p->brother = (Tree)malloc(sizeof(struct TreeNode));
                p = p->brother;
                p->data = Tt[i].C;
                p->child = p->brother = NULL;
                EnQueue(&Q, p);
                i++;
            }
        }
        else return ERROR;//未按层次输入
    }
    return OK;
}

68、已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度(每层中自左至右输入),试写出构造此树的孩子兄弟链表的算法

思路:首先约定输入序列为(结点元素,度),若度为-1时,输入结束,若度为0,则该结点孩子域为空,若度不为0,则创建其孩子并循环创建其孩子的兄弟即可,同时需要将结点依次入队,需要注意的是添加的孩子与其在二元组中的对应,由于二元组是按层次序列输入的,则孩子的位置可以累加获得,而边界即为此时已创建结点子树的总个数算法如下所示:

/*
#define EDMAXSIZE 255//二元组最大容量
typedef struct EDNode {//二元组结构
    char Elem;
    int deg;
}ED[EDMAXSIZE];

Status CreateED(ED* e) {//创建二元组
    int i = 0;
    while (TRUE) {
        scanf("%c%d", &(*e)[i].Elem, &(*e)[i].deg);
        if ((*e)[i].deg == -1) break;
        i++;
    }
    return OK;
}

*/
Status Elem_degCreateTree(Tree* T, ED ch) {//通过二元组创建其孩子兄弟链结构树
//约定输入为:元素——度
    if (ch[0].deg == -1) return ERROR;//无元素

    Queue Q;
    InitQueue(&Q);

    (*T) = (Tree)malloc(sizeof(struct TreeNode));
    (*T)->child = (*T)->brother = NULL;
    (*T)->data = ch[0].Elem;//创建root

    int i = 0;//当前结点
    int j = 0;//当前结点子树位置
    int k = 0;//当前结点子树总个数
    Tree p = (*T);
    EnQueue(&Q, p);
    while (ch[i].deg != -1) {
        DeQueue(&Q, &p);
        k += ch[i].deg;//累加子树个数
        if (ch[i].deg == 0) p->child = NULL;
        else {
            p->child = (Tree)malloc(sizeof(struct TreeNode));
            p->child->data = ch[++j].Elem;//第一个孩子
            p->child->child = p->child->brother = NULL;
            EnQueue(&Q, p->child);
            if (ch[i].deg > 1) {//若度大于1,则添加其兄弟
                p = p->child;
                while (j < k) {
                    p->brother = (Tree)malloc(sizeof(struct TreeNode));
                    p->brother->child = p->brother->brother = NULL;
                    p->brother->data = ch[++j].Elem;
                    EnQueue(&Q, p->brother);
                    p = p->brother;
                }
            }
        }
        i++;
    }
    return OK;
}

测试通过:

image-20210113042724457

image-20210113042743315

69、假设以二叉链表存储的二叉树中,每个结点所行数据元素均为单字母,试编写算法,按树状打印二叉树的算法,入下图所示:

image-20210113043811346

思路:对照上图,不难发现这是一个逆中序输出,而空格的个数即是其所在的层次,打印完元素后换行即可无需利用二维数组附加存储,说实话这道题我看了答案,我第一想到的就是二维数组然后确定其位置进行添加....算法如下所示:

Status Print_BinTree(BinTree T, int n) {
    if (!T) return OK;
    Print_BinTree(T->rchild, n + 1);//递归其右子树
    for (int i = 0; i < n; i++) printf("   ");//按层次打印空格
    if (n >= 0)
        printf("---%c\n", T->data);//打印元素并换行
    Print_BinTree(T->lchild, n + 1);//递归其左子树
    return OK;
}

70、如果用大写字母表示二叉树结点,则一棵二叉树可以用符合下面语法图的字符序列表示,试写一个递归算法,由这种形式的字符序列,建立相应的二叉树的二叉链表存储结构。

image-20210114023247167

思路:这题我又看了答案,之前的思路一直卡在如同建立广义表的思路上,想着如何分割字符串,但是却一直找不到其规律,后边看了答案后发现我思路完全错了,采用字符串长度去控制循环,然后递归实现其左右子树的创建,分为四种情况(在序列正确的情况下)

  • 若当前字符为‘#’,则代表当前树为空
  • 若当前字符为'(',则代表进入其子树的创建,由于序列是根 左 右 【如A(B,C)其中A为根结点,B为左子树,C为右子树】 则子树的创建也是先序顺序
  • 若当前字符为')'或',' 则代表子树创建完毕,退出这层递归
  • 其他字符则是代表根元素,创建根结点即可
  • 需要注意的是,当前状态取决于当前字符,所以每一种情况都需要将字符序列指针自增去判断下一状态

算法如下所示:

//lsorder为字符序列
//i为当前字符,初始情况下为0
//n为字符串总长度
Status ListsCreateBinTree(BinTree* T, char* lsorder, int *i, int n) {
    while (*i < n) {
        if (lsorder[*i] == '#') {//若为#,则为空树
            (*T) = NULL;
            (*i)++;
        }
        else if (lsorder[*i] == '(') {//若当前为(,则代表传入其子树
            (*i)++;
            ListsCreateBinTree(&(*T)->lchild, lsorder, i, n);
            ListsCreateBinTree(&(*T)->rchild, lsorder, i, n);
        }
        else if (lsorder[*i] == ')' || lsorder[*i] == ',') {
            //若为)或者,则代表子树递归结束,退出这成递归
            (*i)++;
            break;
        }
        else {
            //其他情况,建立根结点
            (*T) = (BinTree)malloc(sizeof(struct BinTreeNode));
            (*T)->data = lsorder[(*i)];
            (*T)->lchild = NULL;
            (*T)->rchild = NULL;
            (*i)++;
        }
    }
    return OK;
}

71、假设树上每个结点所含的数据元素为一个字母,并且以孩子-兄弟链表为树的存储结构,试写一个按凹入表方式打印一棵树的算法,如下如所示:

image-20210114023606655

思路,从上图可以得知,按行优先是先序序列(先孩子后兄弟),有了69题的前车之鉴,这道题就是一道简单题,一样层次控制空格输出即可,需要注意的是,只有递归孩子的时候层次才会变化,而兄弟层次是不变的算法如下所示:

Status Print_Tree(Tree T, int n) {
    if (T) {
        for (int i = 0; i < n; i++) printf("  ");
        printf("%c\n", T->data);
        Print_Tree(T->child, n + 1);
        Print_Tree(T->brother, n);
    }
    return OK;
}

72、以孩子链表为树的存储结构,重做71题

思路:这题和上题思路类同,只不过孩子是通过节点中的"度变量"控制的,我们在递归其孩子的时候利用循环去递归其所有孩子即可,算法如下所示:

Status Print_CTree(CTree T, int n) {
    if (T) {
        for (int i = 0; i < n; i++) printf("  ");
        printf("%c\n", T->data);
            for (int i = 0; i < T->ChildNumber; i++)
                Print_CTree(T->child[i], n + 1);
    }
    return OK;
}

73、若用大写字母标识树的结点,则可用带标号的广义表形式表示一棵树,其语法图如下所示:

image-20210114033511255

例如71题中的树可用:A(B(E,F),C(G),D)表示

试写一递归算法,由这种广义表表示的字符序列构造树的孩子兄弟链表(提示:按照树和森林相互递归的定义写两个互相递归调用的算法,语法图中一对圆括号内的部分可看成为森林的语法图)

思路:把其转换成二叉树即可,采用70题的思路即可,略有不同的是,情况变为:

  • 若当前字符为'(',则代表创建其孩子
  • 若当前字符为‘,’则代表创建其兄弟

    • 需要注意的时,在兄弟创建结束后,需要退回上一层,因为序列是按【根 孩子 兄弟】则代表这棵子树已经创建完毕
  • 若当前字符为‘)’,则代表子树创建完毕
  • 为其他字符时,则创建根结点。

算法如下所示:

Status ListsCreateTree(Tree* T, char* lsorder, int* i, int n) {

    while (*i < n) {
        if (lsorder[*i] == '(') {//当前字符为左括号时,递归创建孩子
            (*i)++;
            ListsCreateTree(&(*T)->child, lsorder, i, n);
        }
        else if (lsorder[*i] == ')') {//当前字符为右括号时,表示子树创建完毕,回到上一层
            (*i)++;
            break;
        }
        else if (lsorder[*i] == ',') {//当前括号为逗号时,表示递归创建其兄弟
            //创建完后也许代表该子树创建完,需要回到上一层
            (*i)++;
            ListsCreateTree(&(*T)->brother, lsorder, i, n);
            break;
        }
        else {
            (*T) = (Tree)malloc(sizeof(struct TreeNode));
            (*T)->data = lsorder[*i];
            (*T)->child = NULL;
            (*T)->brother = NULL;
            (*i)++;
        }
    }
    return OK;
}

测试通过

74、试写义递归算法,以73题给定的树的广义表表示法的字符序列形式输出以孩子兄弟链表表示的树

思路:之前我们知道,序列是按先序给出的,则在进入子树时,添加左括号,进入兄弟时,添加逗号,结束一棵子树时(结束代表其没有孩子也没有兄弟,为叶结点的时候),添加右括号即可,算法如下所示:

Status PrintLists_Tree(Tree T) {
    if (T) {
        printf("%c", T->data);
        if (T->child)printf("(");
        PrintLists_Tree(T->child);
        if (T->brother) {
            printf(",");
            PrintLists_Tree(T->brother);
        }
        if (!T->child && !T->brother)
        printf(")");
    }
    return OK;
}

75、试写一递归算法,由73题定义的广义表表示法的字符序列,构造树的孩子链表

思路:这题依旧不难,采用73题的思路即可,还是用循环控制其孩子的输出,不同的是:为逗号或右括号时候需要返回两层,因为第一层作用于的是当前子树,而孩子链表需要返回其父结点才能进行其兄弟的构造

算法如下所示:

/*typedef struct CTreeNode {
    char data;
    int ChildNumber;
    struct CTreeNode** child;//靠ChildNumBer分配孩子个数,指针数组存储孩子域
}*CTree;
*/
Status ListsCreateCTree(CTree* T, char* lsorder, int* i, int n) {
    while (*i < n) {
        if (lsorder[(*i)] == '(') {
            (*i)++;//遇到左括号,则代表进入子树构建,字符递进
            (*T)->ChildNumber++;//子树空间递增
            (*T)->child = (CTree*)realloc((*T)->child, sizeof(CTree) * (*T)->ChildNumber);//为子树空间重新分配内存
            //因为逐步扩建子树空间只能是递增,所以不会出现数据丢失
            for (int j = 0; j < (*T)->ChildNumber; j++) {//循环构造子树
                (*T)->child = (CTree*)realloc((*T)->child, sizeof(CTree) * (*T)->ChildNumber);//在递归内子树空间也许会递增,所以需要重新分配
                ListsCreateCTree(&(*T)->child[j], lsorder, i, n);//构造子树
                if (lsorder[(*i)] == ',') {//返回后判断若是逗号,则代表还有兄弟,子树空间递增,字符递进
                    (*T)->ChildNumber++;
                    (*i)++;
                }
                else if (lsorder[(*i)] == ')') {//返回后若是右括号,则代表子树构造完毕,返回上一层,同时字符递增
                    (*i)++;
                    break;
                }
            }
        }
        else if (lsorder[(*i)] == ',' || lsorder[(*i)] == ')') {
           //若当前字符是逗号或右括号,则代表当前子树没有子树,则返回上一层对其父节点进行操作
            break;
        }
        else {
            (*T) = (CTree)malloc(sizeof(struct CTreeNode));
            (*T)->ChildNumber = 0;
            (*T)->data = lsorder[(*i)];
            (*T)->child = NULL;
            (*i)++;
        }
    }
    return OK;
}

测试通过:

image-20210115114909341

76、试写一递归算法,以73题给定的树的广义表表示法的字符序列形式输出以孩子链表表示的树

思路:这题结合了74和75题的思路也很容易写出来,当我们碰到子树的时候则添加左括号,若子树数目大于0的时候,每一次的递归都添加逗号,当子树输出完后添加右括号,先序序列递归即可,算法如下所示:

/*typedef struct CTreeNode {
    char data;
    int ChildNumber;
    struct CTreeNode** child;//靠ChildNumBer分配孩子个数,指针数组存储孩子域
}*CTree;
*/
Status PrintLists_CTree(CTree T) {
    if (T) {
        printf("%c", T->data);
        if (T->ChildNumber > 0) printf("(");
        for (int i = 0; i < T->ChildNumber; i++) {
            if (i > 0) printf(",");
            PrintLists_CTree(T->child[i]);
        }
        if (T->ChildNumber > 0) printf(")");
    }
    return OK;
}

测试通过

本文链接:

https://nullcode.fun/45.html
1 + 6 =
快来做第一个评论的人吧~