• 北京化工大学数据结构2022/11/3作业 题解


    (12条消息) 食用前须知(阅读并同意后在食用其他部分)_lxrrrrrrrr的博客-CSDN博客

    请大家看完这个再往下看

    目录

    问题 A: 二叉树非递归前序遍历-附加代码模式

    问题 B: 二叉树非递归中序遍历-附加代码模式

    问题 C: 二叉树非递归后序遍历-附加代码模式

    问题 D: 求二叉树中序遍历序根节点的下标

    问题 E: 根据前序+中序还原二叉树

    问题 F: 算法6-12:自底向上的赫夫曼编码

    问题 G: 视频合并问题

    问题 H: 二叉树实现的简单物种识别系统-附加代码模式

    问题 I: 静态链表存储的二叉树查找根节点

    问题 J: 基础实验4-2.1:树的同构

    问题 K: 哈夫曼树--查找值最小的两个叶节点

    问题 L: 静态链表存储的二叉树的非递归遍历算法-附加代码模式


    (快一个月之前因为忘记做核酸然后被迫出校做核酸,

    晴导当时说找谈话)

    之后一直鸽以为过久了就忘了

    没想到他今天居然想起来了!

     

     全当看个乐呵,大家别忘做核酸

    问题 A: 二叉树非递归前序遍历-附加代码模式

    1. #include
    2. using namespace std;
    3. struct BiNode
    4. {
    5. string data;
    6. BiNode *lchild, *rchild;
    7. };
    8. typedef BiNode *BiTree;
    9. int InitBiTree(BiTree &T)
    10. {
    11. T = NULL;
    12. return 0;
    13. }
    14. string PreTraverse_nonRec(BiTree T)
    15. {
    16. stack q;
    17. string result = "";
    18. BiTree temp;
    19. if (T!=NULL) q.push(T);
    20. while(!q.empty())
    21. {
    22. temp=q.top();
    23. q.pop();
    24. result=result+temp->data;
    25. if(temp->rchild!=NULL) q.push(temp->rchild);
    26. if(temp->lchild!=NULL) q.push(temp->lchild);
    27. }
    28. return result;
    29. }
    30. char *CreateBiTree(BiTree &T, char *str)
    31. {
    32. if (*str == '#')
    33. {
    34. T = NULL;
    35. return str + 1;
    36. }
    37. T = new BiNode;
    38. T->data = *str;
    39. // 继续输入并构造左子树和右子树
    40. char * strAfterLeft = CreateBiTree(T->lchild, str + 1);
    41. char * strAfterRight = CreateBiTree(T->rchild, strAfterLeft);
    42. return strAfterRight;
    43. }
    44. int PreTraverse(BiTree T){
    45. if (T == NULL) return 0;
    46. cout << T->data;
    47. PreTraverse(T->lchild);
    48. PreTraverse(T->rchild);
    49. return 0;
    50. }
    51. int DestroyBiTree(BiTree &T){
    52. if (T == NULL) return 0;
    53. DestroyBiTree(T->lchild);
    54. DestroyBiTree(T->rchild);
    55. delete T;
    56. T = NULL;
    57. return 0;
    58. }

    问题 B: 二叉树非递归中序遍历-附加代码模式

    1. #include
    2. using namespace std;
    3. struct BiNode
    4. {
    5. string data;
    6. BiNode* lchild, * rchild;
    7. };
    8. typedef BiNode* BiTree;
    9. int InitBiTree(BiTree& T)
    10. {
    11. T = NULL;
    12. return 0;
    13. }
    14. string InTraverse_nonRec(BiTree T)
    15. {
    16. string result = "";
    17. stack s;
    18. BiTree p = T;
    19. while (p != NULL || !s.empty())
    20. {
    21. while (p != NULL)
    22. {
    23. s.push(p);
    24. p = p->lchild;
    25. }
    26. if (!s.empty())
    27. {
    28. p = s.top();
    29. result += p->data;
    30. s.pop();
    31. p = p->rchild;
    32. }
    33. }
    34. return result;
    35. }
    36. char* CreateBiTree(BiTree& T, char* str)
    37. {
    38. if (*str == '#')
    39. {
    40. T = NULL;
    41. return str + 1;
    42. }
    43. T = new BiNode;
    44. T->data = *str;
    45. char* strAfterLeft = CreateBiTree(T->lchild, str + 1);
    46. char* strAfterRight = CreateBiTree(T->rchild, strAfterLeft);
    47. return strAfterRight;
    48. }
    49. int InTraverse(BiTree T) {
    50. if (T == NULL) return 0;
    51. InTraverse(T->lchild);
    52. cout << T->data;
    53. InTraverse(T->rchild);
    54. return 0;
    55. }
    56. int DestroyBiTree(BiTree& T) {
    57. if (T == NULL) return 0;
    58. DestroyBiTree(T->lchild);
    59. DestroyBiTree(T->rchild);
    60. delete T;
    61. T = NULL;
    62. return 0;
    63. }

    问题 C: 二叉树非递归后序遍历-附加代码模式

    1. #include
    2. using namespace std;
    3. struct BiNode
    4. {
    5. string data;
    6. BiNode* lchild, * rchild;
    7. };
    8. typedef BiNode* BiTree;
    9. int InitBiTree(BiTree& T)
    10. {
    11. T = NULL;
    12. return 0;
    13. }
    14. string SucTraverse_nonRec(BiTree T)
    15. {
    16. string result="";
    17. stack s;
    18. BiTree cur=T;
    19. BiTree prev=NULL;
    20. while(cur!=NULL || !s.empty()){
    21. while(cur!=NULL){
    22. s.push(cur);
    23. cur=cur->lchild;
    24. }
    25. BiTree top=s.top();
    26. if(top->rchild==NULL || top->rchild==prev){
    27. result+=top->data;
    28. s.pop();
    29. prev=top;
    30. }
    31. else{
    32. cur=top->rchild;
    33. }
    34. }
    35. return result;
    36. }
    37. char* CreateBiTree(BiTree& T, char* str)
    38. {
    39. if (*str == '#')
    40. {
    41. T = NULL;
    42. return str + 1;
    43. }
    44. T = new BiNode;
    45. T->data = *str;
    46. char* strAfterLeft = CreateBiTree(T->lchild, str + 1);
    47. char* strAfterRight = CreateBiTree(T->rchild, strAfterLeft);
    48. return strAfterRight;
    49. }
    50. int SucTraverse(BiTree T) {
    51. if (T == NULL) return 0;
    52. SucTraverse(T->lchild);
    53. SucTraverse(T->rchild);
    54. cout << T->data;
    55. return 0;
    56. }
    57. int DestroyBiTree(BiTree& T) {
    58. if (T == NULL) return 0;
    59. DestroyBiTree(T->lchild);
    60. DestroyBiTree(T->rchild);
    61. delete T;
    62. T = NULL;
    63. return 0;
    64. }
    65. // int main(){
    66. // // char *str = "abd###ceg##h##f#i##";
    67. // char str[2000];
    68. // while(cin >> str)
    69. // {
    70. // BiTree tree;
    71. // InitBiTree(tree);
    72. // // 根据带空节点的前序遍历字符串构造二叉树
    73. // CreateBiTree(tree, str);
    74. // // 后序遍历递归算法
    75. // SucTraverse(tree);
    76. // cout << endl;
    77. // // 后序遍历非递归算法
    78. // string result = SucTraverse_nonRec(tree);
    79. // cout << result << endl;
    80. // DestroyBiTree(tree);
    81. // }
    82. // return 0;
    83. // }

    问题 D: 求二叉树中序遍历序根节点的下标

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e6+10;
    19. signed main()
    20. {
    21. string a,b;
    22. while(cin>>a>>b){
    23. cout<find(a[0])<
    24. }
    25. }

    问题 E: 根据前序+中序还原二叉树

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. signed main()
    19. {
    20. function<void(string,string)> post1=[&](string a,string b){
    21. int l=a.length();
    22. if(l==0) return;
    23. if(l==1)
    24. {
    25. cout<0];
    26. return;
    27. }
    28. int p=b.find(a[0]);
    29. post1(a.substr(1,p),b.substr(0,p));
    30. post1(a.substr(p+1,l-p-1),b.substr(p+1,l-p-1));
    31. cout<0];
    32. };
    33. string a,b;
    34. while(cin>>a>>b)
    35. {
    36. post1(a,b);
    37. cout<<'\n';
    38. }
    39. }

    问题 F: 算法6-12:自底向上的赫夫曼编码

    1. #include
    2. using namespace std;
    3. typedef struct {
    4. int parent;
    5. int weight;
    6. int lch;
    7. int rch;
    8. }Huffnode;
    9. Huffnode h[205];
    10. typedef struct {
    11. char code[15];
    12. }Hufftree;
    13. Hufftree hcd[102];
    14. int CreateHufftree(Huffnode hn[],int n)
    15. {
    16. for(int i=n;i<2*n-1;i++)
    17. h[i].weight=0;
    18. for(int i=0;i<2*n-1;i++)
    19. h[i].parent=h[i].lch=h[i].rch=-1;
    20. for(int i=n;i<2*n-1;i++)
    21. {
    22. int min1=INT_MAX,min2=INT_MAX;
    23. int index1,index2;
    24. for(int j=0;j
    25. {
    26. if(h[j].weight-1)
    27. {
    28. min1=h[j].weight;
    29. index1=j;
    30. }
    31. }
    32. h[index1].parent=i;
    33. for(int j=0;j
    34. {
    35. if(h[j].weight-1)
    36. {
    37. min2=h[j].weight;
    38. index2=j;
    39. }
    40. }
    41. h[index2].parent=i;
    42. if(index1>index2)
    43. {
    44. swap(min1,min2);
    45. swap(index1,index2);
    46. }
    47. h[i].weight=min1+min2;
    48. h[i].lch=index1;
    49. h[i].rch=index2;
    50. }
    51. return 0;
    52. }
    53. int Createhuffcode(Huffnode h[],Hufftree hcd[],int n)
    54. {
    55. int head=0;
    56. char s[15];
    57. for(int i=0;i
    58. {
    59. int par=h[i].parent;
    60. int j=i;
    61. while(par!=-1)
    62. {
    63. if(h[par].lch==j) s[head]='0';
    64. else s[head]='1';
    65. head++;
    66. j=par;
    67. par=h[par].parent;
    68. }
    69. int k=0;
    70. while(head>0)
    71. {
    72. head--;
    73. hcd[i].code[k]=s[head];
    74. k++;
    75. }
    76. cout<
    77. head=0;
    78. }
    79. return 0;
    80. }
    81. int main()
    82. {
    83. int n;
    84. while(cin>>n)
    85. {
    86. for(int i=0;i
    87. cin>>h[i].weight;
    88. CreateHufftree(h,n);
    89. Createhuffcode(h,hcd,n);
    90. }
    91. }

    问题 G: 视频合并问题

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=100010;
    19. int a[N];
    20. signed main(){
    21. int n,x,res=0;
    22. priority_queue<int,vector<int>,greater<int> >heap;
    23. cin>>n;
    24. while(n--){
    25. cin>>x;
    26. heap.push(x);
    27. }
    28. while(heap.size()>1){
    29. int a=heap.top();
    30. heap.pop();
    31. int b=heap.top();
    32. heap.pop();
    33. res+=(a+b);
    34. heap.push(a+b);
    35. }
    36. cout<
    37. return 0;
    38. }

    问题 H: 二叉树实现的简单物种识别系统-附加代码模式

    1. #include
    2. using namespace std;
    3. struct BiNode
    4. {
    5. string data;
    6. BiNode *lchild, *rchild;
    7. };
    8. typedef BiNode *BiTree;
    9. int InitBiTree(BiTree &T)
    10. {
    11. T = NULL;
    12. return 0;
    13. }
    14. BiNode *StartRecognize(BiTree T)
    15. {
    16. BiTree p=T;
    17. char c;
    18. for(int i=0;i<2;i++){
    19. cin>>c;
    20. if(c=='y'||c=='Y'){
    21. p=p->rchild;
    22. }else{
    23. p=p->lchild;
    24. }
    25. }
    26. return p;
    27. }
    28. BiNode* getNode(string data){
    29. BiNode* node = new BiNode();
    30. node->data = data;
    31. node->lchild = node->rchild = nullptr;
    32. }

    数据的同学强烈建议python+if

    1. a = input()
    2. b = input()
    3. if a == 'y' or a =='Y':
    4. if b == 'y' or b =='Y':
    5. print("the answer is:eagle")
    6. else:
    7. print("the answer is:swallow")
    8. else:
    9. if b == 'y' or b =='Y':
    10. print("the answer is:tiger")
    11. else:
    12. print("the answer is:rabbit")

    问题 I: 静态链表存储的二叉树查找根节点

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e6+10;
    19. int s1[N];
    20. char s2[N];
    21. signed main(){
    22. int T=2;
    23. while(T--)
    24. {
    25. memset(s1,0,sizeof s1);
    26. int n;
    27. cin>>n;
    28. fer(j,0,n-1)
    29. {
    30. cin>>s2[j];
    31. char a,b;
    32. cin>>a>>b;
    33. if (a != '-')
    34. s1[a - '0']++;
    35. if (b != '-')
    36. s1[b - '0']++;
    37. }
    38. fer(j,0,n-1)
    39. {
    40. if(s1[j]==0)
    41. {
    42. cout<
    43. break;
    44. }
    45. }
    46. }
    47. }

    问题 J: 基础实验4-2.1:树的同构

    1. #include
    2. using namespace std;
    3. struct TreeNode{
    4. char data;
    5. int left;
    6. int right;
    7. }T1[10],T2[10];
    8. int a[100];
    9. int BuildTree(TreeNode T[])
    10. {
    11. memset(a,0,sizeof a);
    12. int n;
    13. int root=-1;
    14. cin>>n;
    15. for(int i=0;i
    16. { char cl,cr;
    17. cin>>T[i].data>>cl>>cr;
    18. if(cl!='-')
    19. {
    20. T[i].left=cl-'0';
    21. a[cl-'0']=1;
    22. }
    23. else{
    24. T[i].left=-1;
    25. }
    26. if(cr!='-')
    27. {
    28. T[i].right=cr-'0';
    29. a[cr-'0']=1;
    30. }
    31. else{
    32. T[i].right=-1;
    33. }
    34. }
    35. for(int i=0;i
    36. {
    37. if(a[i]==0)
    38. {
    39. root=i;
    40. break;
    41. }
    42. }
    43. return root;
    44. }
    45. int judge(int R1,int R2)
    46. {
    47. if(R1==-1&&R2==-1){
    48. return 1;
    49. }
    50. if((R1==-1&&R2!=-1)||(R1!=-1&&R2==-1)){
    51. return 0;
    52. }
    53. if((R1!=-1&&R2!=-1)&&T1[R1].data!=T2[R2].data){
    54. return 0;
    55. }
    56. if(T1[R1].left==-1&&T2[R2].left==-1){
    57. return judge(T1[R1].right,T2[R2].right);
    58. }
    59. if((T1[R1].left!=-1&&T2[R2].left!=-1)&&T1[T1[R1].left].data==T2[T2[R2].left].data){
    60. return judge(T1[R1].left,T2[R2].left)&&judge(T1[R1].right,T2[R2].right);
    61. }
    62. else{
    63. return judge(T1[R1].left,T2[R2].right)&&judge(T1[R1].right,T2[R2].left);
    64. }
    65. }
    66. int main()
    67. {
    68. int root1=BuildTree(T1);
    69. int root2=BuildTree(T2);
    70. if(judge(root1,root2))
    71. {
    72. cout<<"Yes";
    73. }
    74. else{
    75. cout<<"No";
    76. }
    77. }

    问题 K: 哈夫曼树--查找值最小的两个叶节点

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e6+10;
    19. pll a[N];
    20. signed main(){
    21. int n;
    22. cin>>n;
    23. fer(i,1,n){
    24. cin>>a[i].first;
    25. a[i].second=i-1;
    26. }
    27. sort(a+1,a+1+n);
    28. cout<1].second<<" "<2].second;
    29. }

    问题 L: 静态链表存储的二叉树的非递归遍历算法-附加代码模式

    1. #include
    2. using namespace std;
    3. struct BiNode
    4. {
    5. char data;
    6. char lchild;
    7. char rchild;
    8. int flag = 0;
    9. };
    10. struct BiTree
    11. {
    12. int nodeNumber;
    13. BiNode data[10];
    14. int rootIndex;
    15. };
    16. void FindRootIndex(BiTree & T){
    17. vector<char> v;
    18. for (int i = 0; i < T.nodeNumber; ++i) {
    19. if (T.data[i].lchild != '-') v.push_back(T.data[i].lchild-'0');
    20. if (T.data[i].rchild != '-') v.push_back(T.data[i].rchild-'0');
    21. }
    22. for (int i = 0; i < T.nodeNumber; ++i) {
    23. if (find(v.begin(), v.end(), i) == v.end())
    24. {
    25. T.rootIndex = i;
    26. return;
    27. }
    28. }
    29. }
    30. string getPreTraverseStr(const BiTree & T){
    31. if (T.nodeNumber <= 0) return "";
    32. string s;
    33. stack sta;
    34. sta.push(T.data[T.rootIndex]);
    35. while (!sta.empty())
    36. {
    37. BiNode t;
    38. t = sta.top();
    39. sta.pop();
    40. s += t.data;
    41. if (t.rchild != '-') sta.push(T.data[t.rchild-'0']);
    42. if (t.lchild != '-') sta.push(T.data[t.lchild-'0']);
    43. }
    44. return s;
    45. }
    46. string getInTraverseStr(const BiTree & T){
    47. if (T.nodeNumber <= 0) return "";
    48. string s;
    49. stack sta;
    50. sta.push(T.data[T.rootIndex]);
    51. while (!sta.empty())
    52. {
    53. if (sta.top().flag == 0) {
    54. sta.top().flag++;
    55. if (sta.top().lchild != '-') {
    56. sta.push(T.data[sta.top().lchild - '0']);
    57. }
    58. }
    59. else
    60. {
    61. BiNode t;
    62. t = sta.top();
    63. sta.pop();
    64. s += t.data;
    65. if (t.rchild != '-')
    66. {
    67. sta.push(T.data[t.rchild-'0']);
    68. }
    69. }
    70. }
    71. return s;
    72. }
    73. string getSucTraverseStr(const BiTree & T){
    74. if (T.nodeNumber <= 0) return "";
    75. string s;
    76. stack sta;
    77. sta.push(T.data[T.rootIndex]);
    78. while (!sta.empty())
    79. {
    80. if (sta.top().flag == 0)
    81. {
    82. sta.top().flag++;
    83. if (sta.top().lchild != '-')
    84. {
    85. sta.push(T.data[sta.top().lchild-'0']);
    86. }
    87. }
    88. else if (sta.top().flag == 1)
    89. {
    90. sta.top().flag++;
    91. if (sta.top().rchild != '-')
    92. {
    93. sta.push(T.data[sta.top().rchild-'0']);
    94. }
    95. }
    96. else
    97. {
    98. s += sta.top().data;
    99. sta.pop();
    100. }
    101. }
    102. return s;
    103. }

  • 相关阅读:
    2020年MathorCup数学建模B题养老服务床位需求预测与运营模式研究全过程解题程序及多篇论文
    【Mask-RCNN】基于Mask-RCNN的目标检测和识别
    记录一次递归查询导致的 java.lang.StackOverflowError: null
    古代汉语(王力版)笔记 通论8-9
    关于.model.meta,.model.index,.model.data-00000-of-00001--学习笔记
    请问idea git分支树为什么会这样
    haas506 2.0开发教程-hota(仅支持2.2以上版本)
    oak深度相机入门教程-累积行人计数
    【GB28181】wvp-GB28181-pro修改分屏监控为16画面(前端)
    西门子CT重建算法
  • 原文地址:https://blog.csdn.net/m0_61735576/article/details/127663058