1前言

本篇主要讲的是我最近学的关于堆和树的知识。  （我好菜呀）

①树

1. 有n个节点的树有(n-1)条边

2. 树：无环无向图，任意两点之间只有一条边

3. 经过所有边回到原点--哈密尔顿回路

   经过所有点回到原点--欧拉回路

4. 中序：父亲在中间，左儿子在左边，左儿子在右边(人脑习惯)

5. vectora :定义不定长数组

   a.push_back :加入元素

   a.size() :获取元素个数

6. 二叉树：每个节点最多有两个子树的树。

   完全二叉树：一棵深度为h的二叉树，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就 是完全二叉树。

   满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子 结点的二叉树。

   1. 将权值从大到小排序

   2. 取2个数做子节点，建一个空白父节点

   3. 将新建的树放回序列

   4. 重复步骤2

7. 生成哈夫曼树

   • B:只有0的

   • I:只有1的

   • F:其他的j

   ---

   ②图

   1. 堆就是完全二叉树。

   2. • 最大堆：根结点的键值是所有堆结点键值中最大者的堆。

      • 最小堆：根结点的键值是所有堆结点键值中最小者的堆。

   3. 最小堆排序

      #include
      using namespace std;
      int n;
      int heap[11]={0,1,8,2,11,12,4,6};
      int ans[8];
      void d(int i)
      {
      int t;
      while(i*2<=n)
      {
         t=i;
         if(heap[2*i]
         {
             t=2*i;
         }
         else
         {
             t=i;
         }
         if(2*i+1<=n)
         {
             if(heap[2*i+1]
             {
                 t=2*i+1;
             }
         }
         if(t!=i)
         {
             swap(heap[t],heap[i]);
             i=t;
         }
         else
             break;
      }
      return;
      }
      int main()
      {
      heap[1]=10;
      n=7;
      d(1);
      int k = 0;
      while(n>0)
      {
         k++;
         ans[k] = heap[1];
         heap[1] = heap[n];
         n--;
         d(1);
      }
      for(int i=1;i<=7;i++)
      {
         cout<<ans[i]<<" ";
      }
      return 0;
      }

      正确结果：2 4 6 8 10 11 12

   ---

   ③其他

   • queue->队列

   • 位运算

     x>>1 除以2

     x<<1 乘以2

     可以用来计算x的n次方

   • pow函数

     power ：求冥

     pow(x,y) :求x的y次方

   • floor(x)向下取整，返回一个<=x的int整型。

     ceil(x)向上取整，返回一个>=x的int整型。

   • 用一个数据和数据的关系，通过图和线段之间的关系来表示。

     前提条件：BFS

8. FBI树

• VIM是什么？好像是个编译器？

• 我同学写了一个神奇的代码，哪位大佬明白是什么意思？

  #include
  #include
  #define
  int1 long long using namespace std;
  priority_queueq1;
  queueq2;
  queueq3;
  int1 n,m,t,q,u,v;
  int main()
  {
  cin>>n>>m>>q>>u>>v>>t;
  for(int i=1; i<=n; i++)
  {
     int1 a;
     cin>>a;
     q1.push(a);
  }
  int1 tag=0;
  for(int i=1; i<=m; i++)
  {
     int1 x=-1000000000,y=-1000000000,z=-1000000000;
     if(!q1.empty()) x=q1.top();
     if(!q2.empty()) y=q2.front();
     if(!q3.empty()) z=q3.front();
     int1 a;
     a=max(x,max(y,z));
     if(a==x) q1.pop();
     else if(a==y) q2.pop();
     else if(a==z) q3.pop();
     a+=(i-1)q;
     if(i%t==0) cout<<a<<" ";
     int1 px=a(long long)u/v;
     q2.push(px-iq);
     q3.push(a-px-iq);
  }
  cout<<endl;
  for(int i=1; i<=n+m; i++)
  {
     int1 x=-100000000000,y=-100000000000,z=-100000000000;
     if(!q1.empty()) x=q1.top();
     if(!q2.empty()) y=q2.front();
     if(!q3.empty()) z=q3.front();
     int1 a;
     a=max(x,max(y,z));
     if(a==x) q1.pop();
     else if(a==y) q2.pop();
     else if(a==z) q3.pop();
     if(i%t==0) cout<<a+m*q<<" ";
  }
  }

  好了，本月的笔记到此结束。

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com