• 【王道数据结构编程题】- 二叉树算法题

    目录

    1.已知一颗二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个节点的最近的公共祖先节点的值。

    2.编写后序遍历的二叉树的非递归算法

    3.试给出二叉树的自下而上，从右到左的层次遍历算法。

    4.假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。

     5.设一颗二叉树中各个节点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A[1...n]和B[1...n]中，试编写算法建立该二叉树的二叉链表。

    6.二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法。

    7.假设二叉树采用二叉链表存储结构存储，试着设计一个算法，计算一颗给定二叉树的所有双分支节点的个数。

    8.设树B是一颗采用链式结构存储的二叉树，编写一个把树B中所有节点的左，右子树进行交换的函数。

    1.已知一颗二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个节点的最近的公共祖先节点的值。

    1. #include <stdio.h>
    2. #include <malloc.h>
    3. #define MaxSize 13
    4.  
    5. typedef struct TNode
    6. {
    7.     char data;
    8.     TNode* lchild;
    9.     TNode* rchild;
    10. }TNode;
    11.  
    12. int find_public(TNode T[],int i,int j)//注意这里不是TNode* &T
    13. {
    14.     if(T[i].data!='#'&&T[j].data!='#')//还要判断结点是否存在
    15.     {
    16.         while(i!=j)
    17.         {
    18.             if(i>j)
    19.                 i=i/2;
    20.             else
    21.                 j=j/2;
    22.         }
    23.         return i;
    24.     }
    25.     else
    26.         return 0;
    27.  
    28. }
    29.  
    30. int main()
    31. {
    32.     TNode T[MaxSize];
    33.     for(int i=1;i<MaxSize;i++)//从数组下标1开始存储
    34.     {
    35.         char c;
    36.         scanf("%c",&c);
    37.         T[i].data=c;
    38.     }
    39.     int k=find_public(T,4,10);
    40.     printf("%c\n",T[k].data);//测试数据：ABCDE####F#，输出data:B
    41.     return 0;
    42. }
    43. /*
    44.       A
    45. 	B   C
    46.   D   E  
    47.      F 
    48. */

    2.编写后序遍历的二叉树的非递归算法

    1. //非递归的一个后序遍历二叉树
    2. #include<iostream>
    3. using namespace std;
    4. typedef struct TreeNode{
    5.     char data;
    6.     struct TreeNode *lchild,*rchild;
    7.     int tag;
    8. }TreeNode,*Tree;
    9. void creattree(Tree &t)
    10. {
    11.     char ch;
    12.     ch=getchar();
    13.     if(ch=='#') t=NULL;
    14.     else
    15.     {
    16.         t=(TreeNode *)malloc(sizeof(TreeNode));
    17.         t->data=ch;
    18.         t->tag=0;
    19.         t->lchild=NULL;
    20.         t->rchild=NULL;
    21.         creattree(t->lchild);
    22.         creattree(t->rchild);
    23.     }
    24. }
    25. void back(Tree t)
    26. {
    27.     struct TreeNode *stack[100];
    28.     int top=-1;
    29.     TreeNode *p=t;
    30.     TreeNode *x;
    31.     while(p||top!=-1)
    32.     {
    33.         if(p)
    34.         {
    35.             top++;
    36.             stack[top]=p;
    37.             p=p->lchild;
    38.         }
    39.         else
    40.         {
    41.             p=stack[top];
    42.             if(p->rchild&&p->rchild->tag==0)
    43.                 p=p->rchild;
    44.             else
    45.             {
    46.                 p=stack[top];
    47.                 top--;
    48.                 cout<<p->data<<" ";
    49.                 p->tag=1;
    50.                 p=NULL;
    51.             }
    52.         }
    53.     }
    54. }
    55. int main()
    56. {
    57.     Tree t;
    58.     creattree(t);
    59.     back(t);
    60.     return 0;
    61. }
    62. //ABDEC
    63. //测试：ABD##E##C##

    3.试给出二叉树的自下而上，从右到左的层次遍历算法。

    1. #include<iostream>
    2. using namespace std;
    3. #define Max 10
    4. typedef struct treenode{
    5.     char data;
    6.     struct treenode *lchild,*rchild;
    7. }treenode,*tree;
    8. void buildtree(tree &t)
    9. {
    10.     char ch;
    11.     ch=getchar();
    12.     if(ch=='#') t=NULL;
    13.     else
    14.     {
    15.         t=(treenode *)malloc(sizeof(treenode));
    16.         t->data=ch;
    17.         t->lchild=NULL;
    18.         t->rchild=NULL;
    19.         buildtree(t->lchild);
    20.         buildtree(t->rchild);
    21.     }
    22. }
    23. typedef struct stack1{
    24.     struct treenode *data[Max];
    25.     int top;
    26. }stack1;
    27. bool isempty(stack1 s)
    28. {
    29.     if(s.top==-1) return true;
    30.     return false;
    31. }
    32. bool isfull(stack1 s)
    33. {
    34.     if(s.top==Max-1)    return true;
    35.     return false;
    36. }
    37. bool enters(stack1 &s,treenode *p)
    38. {
    39.     if(isfull(s))
    40.     {
    41.         cout<<"栈满"<<endl;
    42.         return false;
    43.     }
    44.     s.data[++s.top]=p;
    45.     return true;
    46. }
    47. bool outs(stack1 &s,treenode *&p)
    48. {
    49.     if(isempty(s))
    50.     {
    51.         cout<<"栈空"<<endl;
    52.         return false;
    53.     }
    54.     p=s.data[s.top--];
    55.     return true;
    56. }
    57. struct squeue1{
    58.     struct treenode *data[Max];
    59.     int f,r,tag;
    60. };
    61. bool entersqueue(squeue1 &s,treenode *x)
    62. {
    63.     if(s.f==s.r&&s.tag==1)
    64.     {
    65.         cout<<"队满"<<endl;
    66.         return false;
    67.     }
    68.     s.data[s.r]=x;
    69.     s.r=(s.r+1)%Max;
    70.     s.tag=1;
    71.     return true;
    72. }
    73. int outsqueue(squeue1 &s,treenode *&x)
    74. {
    75.     if(s.f==s.r&&s.tag==0)
    76.     {
    77.         cout<<"队空"<<endl;
    78.         return 0;
    79.     }
    80.     x=s.data[s.f];
    81.     s.f=(s.f+1)%Max;
    82.     s.tag=0;
    83.     return 1;
    84. }
    85. void solve(tree t)
    86. {
    87.     stack1 s;
    88.     squeue1 q;
    89.     treenode *p;
    90.     if(t)
    91.     {
    92.         s.top=-1;
    93.         q.f=q.r=q.tag=0;
    94.         entersqueue(q,t);
    95.         while(!(q.f==q.r&&q.tag==0))
    96.         {
    97.             outsqueue(q,p);
    98.             enters(s,p);
    99.             if(p->lchild) entersqueue(q,p->lchild);
    100.             if(p->rchild) entersqueue(q,p->rchild);
    101.         }
    102.         while(!isempty(s))
    103.         {
    104.             outs(s,p);
    105.             cout<<p->data<<" ";
    106.         }
    107.     }
    108. }
    109. int main()
    110. {
    111.     tree t;
    112.     buildtree(t);
    113.     solve(t);
    114.     return 0;
    115. }
    116. //测试数据：ABD##E##CF##G##

    4.假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。

    1. //非递归计算二叉树的高度
    2. #include<iostream>
    3. using namespace std;
    4. typedef struct treenode{
    5.     char data;
    6.     struct treenode *lchild,*rchild;
    7. }treenode,*tree;
    8. void buildtree(tree &t)
    9. {
    10.     char ch;
    11.     ch=getchar();
    12.     if(ch=='#') t=NULL;
    13.     else
    14.     {
    15.         t=(treenode *)malloc(sizeof(treenode));
    16.         t->data=ch;
    17.         t->lchild=NULL;
    18.         t->rchild=NULL;
    19.         buildtree(t->lchild);
    20.         buildtree(t->rchild);
    21.     }
    22. }
    23. int dept(tree t)
    24. {
    25.     if(!t) return 0;
    26.     tree q[10];
    27.     int f=-1,r=-1;
    28.     int L=0,ans=0;
    29.     q[++r]=t;
    30.     tree p;
    31.     while(f<r)
    32.     {
    33.         p=q[++f];
    34.         if(p->lchild) q[++r]=p->lchild;
    35.         if(p->rchild) q[++r]=p->rchild;
    36.         if(f==L)
    37.         {
    38.             ans++;
    39.             L=r;
    40.         }
    41.     }
    42.     return ans;
    43. }
    44. int main()
    45. {
    46.     tree t;
    47.     buildtree(t);
    48.     cout<<"树的高度为:"<<dept(t)<<endl;
    49.     return 0;
    50. }
    51. //测试数据：ABD##E##CF###

     5.设一颗二叉树中各个节点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A[1...n]和B[1...n]中，试编写算法建立该二叉树的二叉链表。

    1. //中序先序构造二叉树
    2. #include<iostream>
    3. using namespace std;
    4. typedef struct treenode{
    5.     char data;
    6.     struct treenode *lchild,*rchild;
    7. }treenode,*tree;
    8. int pos=0;
    9. tree build(char a[],char b[],int s,int e)
    10. {
    11.     if(s<=e)
    12.     {
    13.         treenode *root=(treenode *)malloc(sizeof(treenode));
    14.         root->data=a[pos];
    15.         int i;
    16.         for(i=s;i<=e;i++) if(b[i]==root->data) break;
    17.         pos++;
    18.         root->lchild=build(a,b,s,i-1);
    19.         root->rchild=build(a,b,i+1,e);
    20.         return root;
    21.     }
    22.     return NULL;
    23. }
    24. void disp(tree t)
    25. {
    26.     if(t)
    27.     {
    28.         disp(t->lchild);
    29.         disp(t->rchild);
    30.         cout<<t->data<<" ";
    31.     }
    32. }
    33. int main() {
    34.     char a[]={'A','B','D','E','C','F'};//先序序列
    35.     char b[]={'D','B','E','A','F','C'};//中序序列
    36.     tree root=build(a,b,0,5);
    37.     cout<<"后序序列为:"<<endl;
    38.     disp(root);
    39. 	return 0;
    40. }
    41. /*        A
    42.        /    \
    43.       B      C
    44.      / \    /
    45.     D   E  F
    46. */

    6.二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法。

    1. //判断是否是完全二叉树
    2. #include<iostream>
    3. using namespace std;
    4. #define Max 15
    5. typedef struct treenode{
    6.     char data;
    7.     struct treenode *lchild,*rchild;
    8. }treenode,*tree;
    9. void buildtree(tree &t)
    10. {
    11.     char ch;
    12.     ch=getchar();
    13.     if(ch=='#') t=NULL;
    14.     else
    15.     {
    16.         t=(treenode *)malloc(sizeof(treenode));
    17.         t->data=ch;
    18.         t->lchild=NULL;
    19.         t->rchild=NULL;
    20.         buildtree(t->lchild);
    21.         buildtree(t->rchild);
    22.     }
    23. }
    24. struct squeue{
    25.     struct treenode *data[Max];
    26.     int f,r,tag;
    27. };
    28. bool isempty(squeue s)
    29. {
    30.     if(s.f==s.r&&s.tag==0) return true;
    31.     return false;
    32. }
    33. bool isfull(squeue s)
    34. {
    35.     if(s.f==s.r&&s.tag==1) return true;
    36.     return false;
    37. }
    38. bool enters(squeue &s,treenode *p)
    39. {
    40.     if(isfull(s)) return false;
    41.     s.data[s.r]=p;
    42.     s.r=(s.r+1)%Max;
    43.     s.tag=1;
    44.     return true;
    45. }
    46. bool outs(squeue &s,treenode *&p)
    47. {
    48.     if(s.f==s.r&&s.tag==0) return false;
    49.     p=s.data[s.f];
    50.     s.f=(s.f+1)%Max;
    51.     s.tag=0;
    52.     return true;
    53. }
    54. bool isok(tree t)
    55. {
    56.     squeue s;
    57.     s.f=s.r=s.tag=0;
    58.     bool flag=true,ans=true;
    59.     if(t==NULL) ans=true;
    60.     if(!t->lchild&&!t->rchild) ans=true;
    61.     enters(s,t);
    62.     treenode *p;
    63.     while(!isempty(s))
    64.     {
    65.         outs(s,p);
    66.         if(!p->lchild)
    67.         {
    68.             flag=false;
    69.             if(p->rchild) ans=false;
    70.         }
    71.         else//有左孩子
    72.         {
    73.             if(flag)//之前不存在缺孩子的节点
    74.             {
    75.                 enters(s,p->lchild);
    76.                 if(p->rchild) enters(s,p->rchild);
    77.                 else flag=false;
    78.             }
    79.             else//之前存在缺孩子的节点
    80.                 ans=false;
    81.         }
    82.     }
    83.     if(ans) return true;
    84.     return false;
    85. }
    86. int main()
    87. {
    88.  
    89.    tree t;
    90.    buildtree(t);
    91.    if(isok(t)) cout<<"yes"<<endl;
    92.    else cout<<"no"<<endl;
    93.     return 0;
    94. }
    95. //ABD##E##CF##G##  完全
    96. //ABD###CE##F##  非完全

    7.假设二叉树采用二叉链表存储结构存储，试着设计一个算法，计算一颗给定二叉树的所有双分支节点的个数。

    1. //计算二叉树中双分支结点的个数
    2. #include<iostream>
    3. using namespace std;
    4. typedef struct treenode{
    5.     char data;
    6.     struct treenode *lchild,*rchild;
    7. }treenode,*tree;
    8. void buildtree(tree &t)
    9. {
    10.     char ch;
    11.     ch=getchar();
    12.     if(ch=='#') t=NULL;
    13.     else
    14.     {
    15.         t=(treenode *)malloc(sizeof(treenode));
    16.         t->data=ch;
    17.         t->lchild=NULL;
    18.         t->rchild=NULL;
    19.         buildtree(t->lchild);
    20.         buildtree(t->rchild);
    21.     }
    22. }
    23. int num(tree t)
    24. {
    25.     if(!t) return 0;
    26.     else if(t->lchild&&t->rchild) return num(t->lchild)+num(t->rchild)+1;
    27.     else return num(t->lchild)+num(t->rchild);
    28. }
    29. int main()
    30. {
    31.     tree t;
    32.     buildtree(t);
    33.     cout<<"该二叉树中双分结点有 "<<num(t)<<" 个"<<endl;
    34.     return 0;
    35. }
    36. /*
    37.        A
    38.      /  \
    39.     B    C
    40.   /\     /  \
    41.  D E    F   G
    42.  */
    43. //前序序列:ABD##E##CF##G##

    8.设树B是一颗采用链式结构存储的二叉树，编写一个把树B中所有节点的左，右子树进行交换的函数。

    1. //交换左右子树
    2. #include<iostream>
    3. using namespace std;
    4. typedef struct treenode{
    5.     char data;
    6.     struct treenode *lchild,*rchild;
    7. }treenode,*tree;
    8. void buildtree(tree &t)
    9. {
    10.     char ch;
    11.     ch=getchar();
    12.     if(ch=='#') t=NULL;
    13.     else
    14.     {
    15.         t=(treenode *)malloc(sizeof(treenode));
    16.         t->data=ch;
    17.         t->lchild=NULL;
    18.         t->rchild=NULL;
    19.         buildtree(t->lchild);
    20.         buildtree(t->rchild);
    21.     }
    22. }
    23. void swap(tree &t)
    24. {
    25.     treenode *p;
    26.     if(t)
    27.     {
    28.         swap(t->lchild);
    29.         swap(t->rchild);
    30.         p=t->lchild;
    31.         t->lchild=t->rchild;
    32.         t->rchild=p;
    33.     }
    34. }
    35. void disp(tree t)
    36. {
    37.     if(t)
    38.     {
    39.         cout<<t->data<<" ";
    40.         disp(t->lchild);
    41.         disp(t->rchild);
    42.     }
    43. }
    44. int main()
    45. {
    46.     tree t;
    47.     buildtree(t);
    48.     cout<<"交换过后的二叉树为(前序序列):"<<endl;
    49.     swap(t);
    50.     disp(t);
    51.     return 0;
    52. }
    53. /*
    55.              A                            A
    56.           B    C                       C     B
    57.         D  E  F  G                   G   F   E  D  
    59. ABD##E##CF##G##                   ACGFBED 
    61. */

  • 相关阅读:
    Python 自定义包和模块随机生成6位验证码（详解版）
    Ubuntu 18.04 LTS中cmake-gui编译opencv-3.4.16并供Qt Creator调用
    亿达中国武汉园区入选“武汉市科技金融工作站”及“武汉市线下首贷服务站”
    数据结构-复杂度（一）
    YOLOv3: An Incremental Improvement的译读笔记
    http 403
    umi中如何实现路由缓存
    [EIS 2019]EzPOP
    lxml解析库的使用
    艾美捷重组的脱氧核糖核酸酶 I，生物工艺级应用领域
  • 原文地址：https://blog.csdn.net/m0_56051805/article/details/125415110