text: 数据结构 第5章总结 
  树与二叉树
  二叉树
  基本概念：
  树是n(n>=0)个结点的有限集合，n=0时，称为空树；任意非空树满足：
  1）有且仅有一个特定的称为根的结点
  2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根结点的子树 （n个结点的树只有n-1条边）
  树的性质：
  1）树中的结点数等于所有结点的度数加1；
  2）度为m的树中第i层上至多有m^(i-1)个结点(i>=1)；
  3）高度为h的m叉树至多有(m^h-1)/(m-1)个结点；
  4）具有n个结点的m叉树的最小高度为[logm (n(m-1)+1)]（向上取整）
  定义及特点：
  二叉树是n(n>=0)个结点的有限集合；
  1）n=0时，二叉树为空；
  2）n>0时，由根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树也分别是一棵二叉树。
  满二叉树：一棵高度为h，且含有2^h-1个结点的二叉树为满二叉树。对于编号为i的结点，若存在，其双亲的编号为[i/2]（向下取整），左孩子为2i，右孩子为2i+1
  完全二叉树：设一个高度为h、有n个结点的二叉树，当且仅当其每个节点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树；
  性质：
  1）若i<=[n/2]（向下取整），则结点i为分支节点，否则为叶子结点；
  2）叶子节点只可能在层次最大的两层上出现，对于最大层次的叶子结点，都依次排在最左边的位置上；
  3）度为1的结点若存在，则可能有一个，且为编号最大的分支结点，并且孩子结点一定是左结点
  二叉排序树：一棵二叉树，若树非空则具有如下性质：对于任意结点若存在左子树或右子树，则其左子树上所有结点的关键字均小于该结点，右子树上所有结点的关键字均大于该结点。
  平衡二叉树：树上任意结点的左子树和右子树的深度之差不超过1。
  二叉树的性质：
  1）非空二叉树上的叶子结点数等于度为2的结点数加1，即n0=n2+1；
  2）非空二叉树上第k层上至多有2^(k-1)个结点(k>=1)；
  3）高度为h的二叉树至多有2^h-1个结点(h>=1)；
  4）对完全二叉树按从上到下、从左到右的顺序依次编号1,2,...,n，则有以下关系：
  当i>1时，结点i的双亲结点标号为[i/2]（向下取整），即当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。
  当2i<=n时，结点i的左孩子编号为2i，否则无左孩子。
  当2i+1<=n时，结点i的右孩子编号为2i+1，否则无右孩子；
  结点i所在层次为[log2 i]+1（向下取整）
  5）具有n个(n>=0)结点的完全二叉树的高度为[log2 n]+1（向下取整）或[log2 (n+1)]（向上取整）
  二叉树的存储结构
  顺序存储：用一组连续的存储单元一次自上而下、自左至右存储完全二叉树上的节点元素
  链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链接点来存储（含有n个结点的二叉链表中，有n+1个空链域）
  二叉树的遍历
  先序遍历：根结点--左子树--右子树
  void PreOrder(BiTree T)
  {//先序遍历二叉树 
   if(T!=NULL)//若树非空 
   {
   cout<<T->data;//访问根节点 
   PreOrder(T->lchild);//先序遍历左子树 
   PreOrder(T->rchild);//先序遍历右子树 
   }
  }
  中序遍历：左子树--根结点--右子树
  void InOrder(BiTree T)
  {//中序遍历二叉树（递归）
   if(T!=NULL)//若树非空 
   {
   InOrder(T->lchild);//中序遍历左子树 
   cout<<T->data;//访问根节点 
   InOrder(T->rchild);//中序遍历右子树 
   }
  }
  void InOrder2(BiTree T)
  {//中序遍历非递归算法
   InitStack(S); BiTree p=T;
   while(p||IsEmpty(S))
   {
   if(p)
   {
   Push(S,p);
   p=p->lchild;
   }
   else
   {
   Pop(S,p); visit(p);
   p=p->rchild;
   }
   }
  }
  后序遍历：左子树--右子树--根结点
  void PostOrder(BiTree T)
  {//后序遍历二叉树 
   if(T!=NULL)//若树非空 
   {
   PostOrder(T->lchild);//后序遍历左子树 
   PostOrder(T->rchild);//后序遍历右子树 cout<<T->data;//访问根节点
   }
  }
  层次遍历：
  void LevelOrder(Tree T)
  {
   queue<int> Q;//队列
   Q.push(T.root);//根结点入队
   
   int k;
   bool flag=false; 
   while(!Q.empty())
   {
   k = Q.front();//获取队头元素 
   Q.pop();//队头元素出队 
   if(T.data[k].lch==-1 && T.data[k].rch==-1)
   {//叶子结点 
   if(flag==false)
   {
   cout<<k;//输出叶子结点的编号
   flag=true; 
   }
   else
   {
   cout<<" "<<k;
   }
   } 
   else
   {//不是叶子结点 
   if(T.data[k].lch!=-1)
   Q.push(T.data[k].lch);
   if(T.data[k].rch!=-1)
   Q.push(T.data[k].rch);
   }
   } 
  }
  线索二叉树
  二叉树的应用
  二叉排序树
  平衡二叉树
  哈夫曼树及哈夫曼编码
  树的带权路径长度：WPL，树中所有叶子结点的带权路径长度之和
  哈夫曼树的性质：
  1）每个初始结点都会成为叶结点，双支结点都为新生成的结点
  2）权值越大离根结点越近，反之权值越小离根结点越远
  3）哈夫曼树中没有度为1的结点
  4）n个叶子结点的哈夫曼树的节点总数为2n-1，其中度为2的结点数为n-1
  哈夫曼树构造算法：
  1）将n个结点作为n棵仅含有一个根结点的二叉树，构成森林F
  2）生成一个新结点，并从F中找出根结点权值最小的两棵树作为它的左右子树，且新结点的权值为两棵子树根结点的权值之和
  3）从F中删除这个树，并将新生成的树加入到F中
  4）重复2）3）步骤，直到F中只有一棵树为止
  树与森林
  树的基本概念
  树的存储结构
  双亲表示法：采用一组连续的存储空间来存储每个节点，同时在每个结点中增设一个伪指针，指示双亲结点在数组中的位置。根结点的下标为0，其伪指针域为-1。
  孩子表示法：将每个结点的孩子结点都用单链表连接起来形成一个线性结构，n个结点具有n个孩子链表
  左孩子右兄弟表示法：以二叉链表作为树的存储结构，又称二叉树表示法。左指针存放结点第一个孩子节点指针，右指针存放下一个兄弟节点指针
  树和森林的遍历
  树的遍历：
  先根遍历：若树非空，则先访问根节点，再按从左到右的顺序遍历根结点的每棵子树。（树的先根遍历序列与这棵树对应的二叉树的先序遍历序列相同）
  后根遍历：若树非空，则先按从左到右顺序遍历根结点的每棵子树，再访问根节点。（树的后根遍历序列与这棵树对应的二叉树的后序遍历序列相同）
  层次遍历
  森林的遍历：
  先序遍历：若森林非空，则
  访问森林中第一棵树的根结点
  先序遍历第一棵树的子树森林
  先序遍历除去第一棵树之后剩余的树构成的子树森林
  中序遍历：若森林非空，则
  中序遍历第一棵树的根结点的子树森林
  访问第一棵树的根节点
  中序遍历除去第一棵树之后剩余的树构成的子树森林
  树和森林及二叉树的转换
  树与二叉树的转换：左孩子右兄弟算法：每个结点左指针指向它的第一个孩子结点，右指针指向它在树中相邻兄弟结点。
  森林与二叉树的转换：将每一棵树转换为二叉树，将每棵二叉树的根依次作为上一棵二叉树的右子树。（二叉树转换为树或森林是唯一的）
  树的应用--并查集
  ————————————————————
  5.11课堂笔记
  第4章PTA实践：两个整数集合（集合内无重复元素），集合元素个数<=100000，求两集合交集，并按非降序输出1）直接遍历 O(m*n)+Q(排序)2）先排序再合并 O(nlogn)+O(m+n) stl：sort函数！！！
  5.9PTA个人赛：测试点3：5000 连续相同编号输入积分，遇到不同编号时break测试点4：100001）将数组和长度隔开成为两个变量2）将数组和长度打包为一个结构体SqList L;cin>>L.length;L.data[3].id/.money
  分析顺序表、结构体、数组之间的关系：顺序表（结构体（数组））typedef struct{ string id; int money;}node;typedef struct{ node data[MAXSIZE]; int length;}SqList;
  SPOC substr讨论string可以视作C风格的字符型数组string t;空串 t[0] t[1] 非法访问内存string t="1234";//合法：t[0]~t[3]
  char *p="123456";//在常量区写入123456，将该字符串的首地址返回给pchar s[]="123456";//在栈空间中给s分配一个空间，大小为7个字符（加上\0）p[0] ='0';//在常量区存储，不能修改（编译正确，运行时非法）s[0] = '0';//可以修改char *t = new char[10];//在堆空间开辟是个字符大小的空间，将首地址赋值给t，合法t[0]~t[9]t = "123456";//在常量区开辟空间写入该字符串，再将首地址返回给t；原来通过t申请的空间没有释放，产生内存泄漏
  5.11课堂提问1.一棵有201个结点的完全二叉树，其中叶子结点的个数是？对任何一棵二叉树T, 如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1如果该完全二叉树存在一个度为1的结点，那总数一定为偶数，故不存在度为1的结点 n2=(201-1)/2 n0=n2+1=1012。一个具有258个结点的二叉树的高h为？本题未说明是否为完全二叉树，最矮情况下高度=(log2 258)+1=9，最高情况下为单支树，高度为2583.深度为h的满m叉树的第k层有多少个结点?(1<=k<=h)二叉树第i层上至多有2^(i-1)个结点，故结点数为 m^(k-1)
  5.11SPOC讨论二叉树的顺序存储结构：1）若采用课本P120的方式进行顺序存储，对于非完全二叉树来说，有可能造成存储空间的极大浪费，为什么？因为用该方式存储非完全二叉树时，需要在其对应完全二叉树的位置空缺时进行补齐，会对空间造成浪费
  ————————————————————
  5.12课堂提问1、若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？不存在，n=98，n1=48，所以n0+n2=50，又因为n0=n2+1 为奇数，故不存在2、在一棵度为3的树T中，若有10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数为？22个，n3=10，n2=1，n1=10，分支总数=10*3+1*2+10*1=42而在一棵树中只有根结点没有分支指向，所以结点总数=分支总数+1，n=43n0=43-10-1-10=22
  ————————————————————
  5.18课堂笔记
  讨论疑问：
  1）
  将二叉树根结点下标与nodes打包，可以通过根节点下表找双亲
  利用Node *nodes;在初始化时申请空间，避免数组大小不足或浪费
  2）
  typedef struct
  {
  char data;
  int parent;
  }BiTNode;
  int n;//需要包在函数内出现
  cin>>n;
  BiTNode *BiTree new BiTNode[n];//在堆空间存储
  int n; cin>>n; int a[n];//常量区存储 C可以 C++不行
  3）
  Parent跟数组打包在一起，指向不明
  名字查找 下标查找
  O（n） O（n）
  O（1） O（1）
  O(n)……
  找双亲的下标公式
  i/2（向下取整）
  课堂问题
  如果T为空，直接退出函数
  Fun函数：
  利用STL中的queue模板
  层次遍历：
  一层一层向下遍历，遍历当前结点时，同时保存孩子结点
  先进先出，利用队列
  q.push(T);//T结点入队相当于地址入队
  BiTNode *p;//定义与q相同类型的p
  当q不为空时
  P=q.front();//q队头元素赋值给p
  q.pop();//弹出队头元素
  ————————————————————
  1.typedef struct{int dataCNode *nodes;}CNode;错误，如果要递归定义结构体，必须在struct后面声明
  2.怎样才是哈夫曼树？有最优的非哈夫曼树吗？利用哈夫曼算法创建的二叉树，这棵二叉树一定是最优的有，eg：{1，2，3，4，5}>>WPL=33怎样构造最优的非哈夫曼树？交换同层次的叶子结点
  3.listleaveselse{if(...);//可能同时执行if(...);}
  else if(...);//不可能同时执行else if(...);
  ————————————————————
  总结：从树这一章开始，感觉数据结构真正开始综合起来了。在实际开发中，树不单单只是一个简单的逻辑结构，更多的需要与之前的栈、队、线性表进行结合，从而达到清晰的结构定义。不过也真的是挺难的，特别是属于森林的部分，存储的逻辑很清晰，但是在写结构体和对应操作算法的时候会一直卡住，可能还是对之前的章节不够熟练吧，所以现阶段要更加注重之前的知识掌握情况，同时要充分理解新学习的逻辑结构。