Code666 (代码贴、代码片段)

[C++] 是否同一棵二叉搜索树 →→→→→进入此内容的聊天室

来自 , 2021-04-11, 写在 C++, 查看 147 次.
URL http://www.code666.cn/view/84ddfb34
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef struct TreeNode * Tree;
  4. struct TreeNode
  5. {
  6.     int data;
  7.     Tree left, right;
  8.     int flag;
  9. };
  10. Tree NewNode(int V)
  11. {
  12.     Tree T = (Tree)malloc(sizeof(struct TreeNode));
  13.     T->data = V;
  14.     T->left = T->right = NULL;
  15.     T->flag = 0;
  16.     return T;
  17. }
  18.  
  19. Tree Insert(Tree T,int V)//二叉排序树的插入方式
  20. {
  21.     if(T)
  22.     {
  23.         if(V > T->data)
  24.             T->right = Insert(T->right,V);
  25.         else
  26.             T->left = Insert(T->left,V);
  27.     }
  28.     else
  29.         T = NewNode(V);
  30.     return T;
  31. }
  32.  
  33. Tree MakeTree(int N)
  34. {
  35.     Tree R;
  36.     int i, V;
  37.     cin>>V;
  38.     R = NewNode(V);
  39.     for( i = 1; i < N; i ++)
  40.     {
  41.         cin>>V;
  42.         R = Insert(R,V);
  43.     }
  44.     return R;
  45. }
  46.  
  47. int check(Tree T,int V)
  48. {
  49.     if(T->flag)//如果当前节点查找过了
  50.     {
  51.         if(V < T->data)
  52.             return check(T->left,V);//此时要查找的数小于该节点的数，去左边查找
  53.         else if(V > T->data)
  54.             return check(T->right,V);//大于该节点的数，去右边查找
  55.         else
  56.             return 0;//如果相等则不一致
  57.     }
  58.     else//如果当前节点没查找过
  59.     {
  60.         if(V == T->data)//如果是要查找的节点则标记为查找过
  61.         {
  62.             T->flag=1;
  63.             return 1;
  64.         }
  65.         else return 0;//如果当前节点没被查找过还不是要查找的节点，则不一致
  66.     }
  67. }
  68.  
  69. int judge(Tree T,int N)
  70. {
  71.     int i, V, flag = 1;
  72.     cin>>V;
  73.     if(V == T->data)
  74.         T->flag = 1;   //1代表目前还一致
  75.     else
  76.         flag = 0;
  77.     for( i =1 ; i < N ; i ++)
  78.     {
  79.         cin>>V;
  80.         if(flag&&(!check(T,V)))
  81.             flag=0;//如果check不一致，则整棵树不一致
  82.     }
  83.     if(flag)
  84.         return 1;
  85.     else
  86.         return 0;
  87. }
  88.  
  89. void ResetFlag(Tree T)
  90.  
  91. {
  92.     if( T -> left)
  93.         ResetFlag(T->left);
  94.     if( T -> right)
  95.         ResetFlag(T->right);
  96.     T->flag = 0;
  97. }
  98. void TreeFree(Tree T)
  99. {
  100.     if( T -> left)
  101.         TreeFree(T->left);
  102.     if( T -> right)
  103.         TreeFree(T->right);
  104.     free(T);
  105.     T=NULL;
  106. }
  107.  
  108. int main ()
  109. {
  110.     Tree T;//初始化数
  111.     int N, L, i;
  112.     cin>>N;
  113.     while(N)
  114.     {
  115.         cin>>L;
  116.         T = MakeTree(N);//建本次事例的初始化对比树
  117.         for ( i = 0; i < L; i ++ )
  118.         {
  119.             if (judge(T,N))
  120.                 cout<<"Yes"<<endl;
  121.             else
  122.                 cout<<"No"<<endl;
  123.             ResetFlag(T);//清楚判断过程中flag标记
  124.         }
  125.         TreeFree(T);//清楚本次事例的对比数
  126.         cin>>N;
  127.     }
  128. }
  129.  

回复 "是否同一棵二叉搜索树"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666