SCAU华南农业大学数据结构oj 实验四

Agt_von

947人浏览 · 2025-05-24 15:12:37

Agt_von · 2025-05-24 15:12:37 发布

8606 二叉树的构建及遍历操作

Description

构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），'#'字符表示空树，构造二叉链表表示的二叉树T；再输出三种遍历序列。本题只给出部分代码,请补全内容。

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
    if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
    ________________________ // 生成根结点
     _______________________   // 构造左子树
    _________________________ // 构造右子树
}
return OK;
} // CreateBiTree

Status PreOrderTraverse( BiTree T) {
// 前序遍历二叉树T的递归算法
//补全代码,可用多个语句

} // PreOrderTraverse

Status InOrderTraverse( BiTree T) {
     // 中序遍历二叉树T的递归算法
    //补全代码,可用多个语句

} // InOrderTraverse

Status PostOrderTraverse( BiTree T) {
// 后序遍历二叉树T的递归算法
//补全代码,可用多个语句

} // PostOrderTraverse

int main() //主函数
{
//补充代码
}//main

输入格式

第一行：输入一棵二叉树的先序遍历序列

输出格式

第一行：二叉树的先序遍历序列
第二行：二叉树的中序遍历序列
第三行：二叉树的后序遍历序列

输入样例

AB##C##

输出样例

ABC
BAC
BCA

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
#include <iostream>
using namespace std;
typedef int  Status;

typedef char  ElemType;
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

Status CreateBiTree(BiTree &T) {  // 算法6.4
  // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
  // 构造二叉链表表示的二叉树T。
  char ch;
  scanf("%c",&ch);
  if (ch=='#') T = NULL;
  else {
    if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
    T->data=ch; // 生成根结点
    CreateBiTree(T->lchild);// 构造左子树
    CreateBiTree(T->rchild); // 构造右子树
  }
  return OK;
} // CreateBiTree

Status PreOrderTraverse( BiTree T) {
   if(T==NULL) return ERROR;
   else{
   cout<<T->data;
   PreOrderTraverse(T->lchild);
   PreOrderTraverse(T->rchild);}
} // PreOrderTraverse

Status InOrderTraverse( BiTree T) {
    if(T==NULL) return ERROR;
    else{
   InOrderTraverse(T->lchild);
   cout<<T->data;
   InOrderTraverse(T->rchild);}
} // InOrderTraverse

Status PostOrderTraverse( BiTree T) {
   if(T==NULL) return ERROR;
   else{
   PostOrderTraverse(T->lchild);
   PostOrderTraverse(T->rchild);
   cout<<T->data;}
} // PostOrderTraverse



int main()   //主函数
{
    BiTree T;
    CreateBiTree(T);
    PreOrderTraverse(T);
    cout<<endl;
    InOrderTraverse(T);
    cout<<endl;
    PostOrderTraverse(T);
 }//main

解析：这道题是很基础的二叉树的基本操作，本质就是利用递归进行遍历，创建二叉树时就先创建根节点，将数据存入，然后递归创建左子树和右子树；前中后序遍历则按照根节点，左子树，右子树不同的顺序进行递归遍历，这道题没什么说的

17121 求二叉树各种节点数

Description

构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），'#'字符表示空树，构造二叉链表表示的二叉树T,并求此二叉树中度为2的节点总数，度为1的节点总数，度为0的节点总数

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

int main() //主函数
{
//补充代码
}//main

输入格式

第一行输入先序次序二叉树中结点

输出格式

第一行输出度为2的节点数
第二行输出度为1的节点数
第三行输出度为0的节点数

输入样例

ABC###D##

输出样例

1
1
2

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
#include<iostream>
using namespace std;
typedef int  Status;

typedef char  ElemType;
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

Status CreateBiTree(BiTree &T) {  // 算法6.4
  // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
  // 构造二叉链表表示的二叉树T。
  char ch;
  scanf("%c",&ch);
  if (ch=='#') T = NULL;
  else {
    if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
    T->data=ch; // 生成根结点
    CreateBiTree(T->lchild);  // 构造左子树
    CreateBiTree(T->rchild);  // 构造右子树
  }
  return OK;
} // CreateBiTree
int er(BiTree T)
{
    if(T==NULL) return ERROR;
    int ct=0;
    if(T->lchild!=NULL&&T->rchild!=NULL)
    {
        ct=1;
    }
    return ct+er(T->lchild)+er(T->rchild);
}
int yi(BiTree T)
{
    if(T==NULL) return ERROR;
    int ct=0;
    if((T->lchild!=NULL&&T->rchild==NULL)||(T->lchild==NULL&&T->rchild!=NULL))
    {
        ct= 1;
    }
    return ct+yi(T->lchild)+yi(T->rchild);
}
int o(BiTree T)
{
    if(T==NULL) return ERROR;
    if(T->lchild==NULL&&T->rchild==NULL)
    {
        return 1;
    }
    return o(T->lchild)+o(T->rchild);
}
int main()   //主函数
{
    BiTree T;
    CreateBiTree(T);
    cout<<er(T)<<endl;
    cout<<yi(T)<<endl;
    cout<<o(T)<<endl;
 }//main

解析：这题思路很简单，就是通过遍历将符合度数条件的一个个数出来，比如数节点度为1的函数int yi(BiTree T)中，如果树为空就return error，而度为1的条件是左孩子为空或者右孩子但是不能同时为空，遇到符合条件的就更新数量

18924 二叉树的宽度

Description

二叉树的宽度指的是具有节点数目最多的那一层的节点个数。
          1
         / \
        2   3
       /
      4
答案为2, 第二层节点数最多，为2个节点。

输入格式

共n行。
第一行一个整数n，表示有n个结点，编号为1至n,结点1为树根。（1<=n<=50）
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子

输出格式

输出二叉树的宽度。

输入样例

5
1 2
1 3
2 4
2 5

输出样例

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int hai[105][3]={ };
    int width=1;
    int x,y;
    for(int i=1;i<n;i++)
    {
        cin>>x>>y;
        if(!hai[x][1])
        {
            hai[x][1]=y;
        }
        else
        {
            hai[x][2]=y;
        }
    }
    queue<int> man;
    man.push(1);
    while(man.size())
    {
        int len=man.size();
        width=max(width,len);
        for(int i=0;i<len;i++)
        {
            int temp=man.front();
            man.pop();
            if(hai[temp][1])
            {
                man.push(hai[temp][1]);
            }
            if(hai[temp][2])
            {
                man.push(hai[temp][2]);
            }
        }
    }
    cout<<width;
    return 0;
}

解析：这道题标程的思路就很好，将每一个节点的孩子节点通过另外一个数组存起来，方便处理。重点说说bfs的部分：

while(man.size())
    {
        int len=man.size();
        width=max(width,len);
        for(int i=0;i<len;i++)
        {
            int temp=man.front();
            man.pop();
            if(hai[temp][1])
            {
                man.push(hai[temp][1]);
            }
            if(hai[temp][2])
            {
                man.push(hai[temp][2]);
            }
        }
    }

先看内层循环，这一部分代码就是将各节点替换为各结点的孩子节点，而每一次更新队列，就会重新更新宽度，保证其为最大宽度，而len则为记录上一次内层循环更新后的队列的长度（即为上一层的宽度），len变量的存在既方便我们更新宽度，又方便我们更新队列，而外层循环的条件man.size()则巧妙地保证了能够在遍历完每一层树之后结束循环。

18724 二叉树的遍历运算

Description

二叉树的三种遍历都可以通过递归实现。
如果我们知道一棵二叉树的先序和中序序列，可以用递归的方法求后序遍历序列。

输入格式

两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。
树的结点一律用小写字母表示,且字符串长度不超过30。

输出格式

一个字符串，树的后序序列。

输入样例

abcde
bcade

输出样例

cbeda

#include <iostream>
#include <string>
using namespace std;
string pre,mid;
void post(int root,int start,int end)
{
    if(start>end) return;
    int i=start;
    while(i<end&&mid[i]!=pre[root])
    {
        i++;
    }
    post(root+1,start,i-1);
    post(root+i-start+1,i+1,end);
    cout<<mid[i];
}
int main()
{
    cin>>pre>>mid;
    int len=pre.length();
    post(0,0,len-1);
    return 0;
}

解析：这道题需要了解三种遍历的顺序的特点：

 先序：第一个元素是当前子树的根节点。

 中序：根节点将序列分为左子树和右子树。

所以思路就明确了：在先序中找到当前根节点（pre[root]），然后在中序中定位该根节点的位置i。中序中i左边的元素属于左子树，右边的属于右子树。对左子树和右子树分别递归调用，最后输出根节点，形成后序遍历（左→右→根）。

所以不断地找到根节点是这道题的关键。

仔细看一下post函数：

void post(int root,int start,int end)
{
    if(start>end) return;
    int i=start;
    while(i<end&&mid[i]!=pre[root])
    {
        i++;
    }
    post(root+1,start,i-1);
    post(root+i-start+1,i+1,end);
    cout<<mid[i];
}

参数root:前序遍历的根节点位置，start/end：子树在中序的位置

递归出口：start>end

变量i是标记根节点在中序遍历的位置。

post(root+1,start,i-1);则为遍历左子树，root+1:在先序中，左子树的根节点紧跟在当前根节点之后;中序范围为start到i - 1。

post(root+i-start+1,i+1,end);则为遍历右子树，根节点位置为root + i - start + 1（跳过左子树长度），中序范围为i + 1到end。

问：为什么这样就能保证后序输出呢？

答：后序的本质：

后序遍历的顺序是：左子树 → 右子树 → 根节点。
递归代码的关键在于：先处理左子树和右子树，最后处理根节点。

递归的调用栈决定了节点的处理顺序。代码中总是先深入左子树，再深入右子树，最后处理根节点。

左子树优先处理：递归会一直向左深入，直到左子树为空。
右子树次之处理：左子树处理完毕后，递归处理右子树。
根节点最后处理：左右子树都处理完毕后，才会将根节点加入结果。

做完这题建议去看洛谷P1827

https://www.luogu.com.cn/problem/P1827

18923 二叉树的直径

Description

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
          1
         / \
        2   3
       / \
      4   5
答案为3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

输入格式

共n行。
第一行一个整数n，表示有n个结点，编号为1至n。
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子

输出格式

输出二叉树的直径。

输入样例

5
1 2
1 3
2 4
2 5

输出样例

#include <iostream>
#include <algorithm>
using namespace std;
int man[100][3],d=0;
int dfs(int root)
{
    if(!root) return 0;
    int lchild=dfs(man[root][1]);
    int rchild=dfs(man[root][2]);
    int depth=max(lchild,rchild)+1;
    d=max(d,lchild+rchild);
    return depth;
}
int main()
{
    int n;
    cin>>n;
    int x,y;
    for(int i=1;i<n;i++)
    {
        cin>>x>>y;
        if(!man[x][1]) man[x][1]=y;
        else man[x][2]=y;
    }
    dfs(1);
    cout<<d<<endl;
    return 0;
}

解析：这道题还是讲解标程思路，还是同样的思路，利用另一个数组存各节点的孩子节点方便处理。仔细看看dfs函数：

int dfs(int root)
{
    if(!root) return 0;
    int lchild=dfs(man[root][1]);
    int rchild=dfs(man[root][2]);
    int depth=max(lchild,rchild)+1;
    d=max(d,lchild+rchild);
    return depth;
}

首先我们必须清楚，直径是左右子树高度之和，为什么？高度即为最深叶子结点到当前节点距离是多少，假设当前节点的左子树高度为2（路径A → B → 当前节点），右子树高度为3（路径当前节点 → C → D → E），则经过当前节点的最长路径为 A → B → 当前节点 → C → D → E，长度为5。

所以，我们只需要递归遍历左子树和右子树的高度，不断更新深度就行。

8609 哈夫曼树

Description

利用静态链表建立赫夫曼树，建树过程中要求左子树权值小于右子树权值，求各结点的编码。要求：叶子结点的个数n及结点值由键盘录入。本题给出程序代码,要求填空以满足测试要求.
#include "stdio.h"
#include "string.h"
#include
using namespace std;
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void   select(HuffmanTree &HT, int n, int &s1, int &s2)
{//在HT[1..n]中选择parent为0且weight最小的两个结点，其序号分别为s1（最小）和s2（次小）。
   __________________________
}
void createHuffmanTree(HuffmanTree &HT, int n)
{ //构造哈夫曼树HT
    int i, m, s1, s2;
    if (n<=1) return;
    m = 2 * n - 1;
    HT = new HTNode[m+1]; // 0号单元未用
    for (i=1; i<=m; i++) { //初始化HT数组
        HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
    }
    for (i=1; i<=n; i++)
        cin>>HT[i].weight;
    for (i=n+1; i<=m; i++)    // 建哈夫曼树
    { //在HT[1..i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1(最小)和s2(次小)
         _______________________________
    }
}
void createHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
    char *cd = new char[n];    // 分配求编码的工作空间
    cd[n-1] = '\0'; // 编码结束符。
    int i,c,f,start;
    for (i=1; i<=n; ++i)
    {
        start = n-1;
        c=i, f=HT[i].parent;
        while(f)// 从叶子到根逆向求编码
        {
            --start;
            if (HT[f].lchild==c) cd[start] = '0';
            else cd[start] = '1';
            c=f,f=HT[f].parent;
        }
        HC[i] = new char[n-start];// 为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]);    // 从cd复制编码(串)到HC
    }
}
int main()
{
    int i,n;
    int *w;
    HuffmanTree HT;
    HuffmanCode HC;
    scanf("%d",&n); //权值个数
    HC=new char*[n+1]; //0空间未用
    createHuffmanTree(HT,n);
    createHuffmanCode(HT,HC,n);
    for (i = 1; i<=n; i++)
        printf("%s\n",HC[i]); //输出哈夫曼编码
}

输入格式

第一行：权值个数
第二行：输入n个权值，用空格分隔

输出格式

输出n行
每行表示各权值对应的哈夫曼编码

输入样例

8
5 29 7 8 14 23 3 11

输出样例

0001
10
1110
1111
110
01
0000
001

#include "stdio.h"
#include "string.h"
#include <iostream>
using namespace std;
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void   select(HuffmanTree &HT, int n, int &s1, int &s2)
{//在HT[1..n]中选择parent为0且weight最小的两个结点， 其序号分别为s1（最小）和s2（次小）。
   int minn=1;
   for(int i=1;i<=n;++i)
   {
       if(HT[i].parent==0)
       {
           minn=i;
           break;
       }
   }
   for(int i=minn;i<=n;++i)
   {
       if(HT[i].parent==0&&HT[i].weight<HT[minn].weight)
       {
           minn=i;
       }
   }
   s1=minn;
   minn=1;
   for(int i=1;i<=n;++i)
   {
       if(HT[i].parent==0&&s1!=i)
       {
           minn=i;
           break;
       }
   }
   for(int i=minn;i<=n;++i)
   {
       if(HT[i].parent==0&&HT[i].weight<HT[minn].weight&&i!=s1)
       {
           minn=i;
       }
   }
   s2=minn;
}
void createHuffmanTree(HuffmanTree &HT, int n)
{ //构造哈夫曼树HT
    int i, m, s1, s2;
    if (n<=1) return;
    m = 2 * n - 1;
    HT = new HTNode[m+1];  // 0号单元未用
    for (i=1; i<=m; i++) { //初始化HT数组
        HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
    }
    for (i=1; i<=n; i++)
        cin>>HT[i].weight;
    for (i=n+1; i<=m; i++)    // 建哈夫曼树
    { //在HT[1..i-1]中选择parent为0且weight最小的两个结点， 其序号分别为s1(最小)和s2(次小)
         select(HT,i-1,s1,s2);
         HT[s1].parent=i;HT[s2].parent=i;
         HT[i].lchild=s1;HT[i].rchild=s2;
         HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
}
void createHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
    char *cd = new char[n];    // 分配求编码的工作空间
    cd[n-1] = '\0';  // 编码结束符。
    int i,c,f,start;
    for (i=1; i<=n; ++i)
    {
        start = n-1;
        c=i, f=HT[i].parent;
        while(f)// 从叶子到根逆向求编码
        {
            --start;
            if (HT[f].lchild==c) cd[start] = '0';
            else cd[start] = '1';
            c=f,f=HT[f].parent;
        }
        HC[i] = new char[n-start];// 为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]);    // 从cd复制编码(串)到HC
    }
}
int main()
{
    int i,n;
    int *w;
    HuffmanTree HT;
    HuffmanCode HC;
    scanf("%d",&n);  //权值个数
    HC=new char*[n+1]; //0空间未用
    createHuffmanTree(HT,n);
    createHuffmanCode(HT,HC,n);
    for (i = 1; i<=n; i++)
        printf("%s\n",HC[i]);  //输出哈夫曼编码
}

DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

企业微信 × AI 对接第四步：应用消息 message/send——和群机器人怎么分工，配额与字节红线都算给你（附代码）

企业微信里给员工发消息有两条路——群机器人 webhook（W2 讲过，只进群）和应用消息 message/send（本篇，能直达个人工作台、支持模板卡片交互）。选错通道是新手最常见的设计失误。这篇把 message/send 的 8 种消息类型、touser/toparty/totag 定向规则、2048 字节红线、"账号上限×200 人次/天"的配额算法、81013/invaliduser 可