四、数据结构第四节——二叉树

今天开启美妙的二叉树的学习~~~

“树”是我们第一次见到的”非线性”的数据结构。

二叉树：是树上每个节点都只有两个子节点的简单的树。

知识点小汇：

1. 完全二叉树：除了最后一层外全满的二叉树，最后一层从左到右依次排满。（中间不空）

2. 满二叉树：全满的二叉树。（不存在某个节点没有子节点）

3. 满二叉树的节点个数：2^h-1

4. 完全二叉树节点个数范围：[ 2^h , 2^h - 1 )

5. 完全二叉树的储存：

   • 在以数组 [ 1 ] 为 “根” 建立的二叉树中
   • 对于数组 [ t ] 位置的 “左、右儿子” 对应的位置应为 [ 2t ] 和 [ 2t + 1 ] ，“父亲” 的节点位置为 [ t / 2 ] .

6. 完全二叉树的建立：

   void Build ( int t ){
       //添加数据,可以用不同方式添加数据；（ 取决于UpdateDate（）函数的自我定义 ） 
       UpdateDate( t );
       //如果子节点存在
       Build( t + t );
       Build( t + t + 1 );
   }
   

7. 用struct 方式储存信息：

   用指针储存二叉树：

   struct TreeNode {
   	int value;
   	TreeNode *l,*r,*fa;
   };
   
   TreeNode *root; //根
   

   此方式中的基本操作有如下：

   1. 新建节点

      此处定义了”新建节点函数“ TreeNode（），

      调用该函数，新建节点p，且将该节点处的value的值赋成x

      struct TreeNode {
          int value;
          TreeNode *i,*r,*fa; //自动初始化为NULL
          TreeNode( int x ) { value = x; }  //定义了一个函数TreeNode( int x )
          								  //该函数将该节点的value的值设置为x
      };
      TreeNode *p = new TreeNode(x);        //新建的节点处valu的值是x
      

   2. 根节点初始化

      TreeNode *root;
      root = new TreeNode(v); // v是根节点
      

   3. 插入节点

      此处定义了一个inser（）函数，使用该函数将新节点 p 插到 fa 的左（或右）边，成为左（或右）儿子，fa 就理所当然的成为了新节点p 的爹（fa）

      void insert (TreeNode *fa, TreeNode *p, int flag ){
          //flag = 0 插入到左边
          //flag = 1 插入到右边
          if ( !flag ) {
              fa -> l = p;
          }else{
              fa -> r = p;
          }
          p -> fa = fa; //插入的节点的爹（fa）是 fa 
      }
      TreeNode *p = new TreeNode(v); //新建一个节点p，并将该节点的value赋值为v
      insert( fa, p, flag );     //将新节点p插入fa后成为其子节点
      

8. 二叉树的遍历顺序

   • 先序遍历（ 根左右 ）
   • 中序遍历（ 左根右 ）
   • 后续遍历（ 左右根 ）
   • 层级遍历（ BFS序列 ）

   1.先序遍历（DLR）

   void PreOrder ( TreeNode *p ){
       cout << p -> value << endl;		//先输出根值，在递归左、右儿子
       if ( p -> l ) PreOrder( p -> l ); //如果左儿子存在，则对左儿子进行先序遍历
       if ( p -> r ) PreOrder( p -> r ); //同上
   }
   PreOrder(root); //从根开始遍历
   

   2.中序遍历（LDR）

   void InOrder ( TreeNode *p ){
       if ( p -> l ) InOrder( p -> l );
       cout << p -> value << endl;
       if ( p -> r ) InOrder( p -> r );
   }
   InOrder(root);
   

   3.后序遍历（LRD）

   void PostOrder ( TreeNode *p ){
       if ( p -> l ) PostOrder( p -> l );
       if ( p -> r ) PostOrder( p -> r );
       cout << p -> value << endl;
   }
   PostOrder(root);
   

   4.层级遍历（ BFS ）

   用队列的方式进行层级遍历，先对于同深度的节点进行遍历，在逐层向下。

   对于root进行层级遍历，即：

   1. 将根值放入队首
   2. 输出，并弹出队首元素
   3. 若根（队首元素）的左、右儿子存在，则依次将其放入队列
   4. 一次循环完成。
   5. 对于新的队列（由左、右儿子组成的队列）的队首元素继续层级遍历

   通过上述步骤实现对该二叉树实现层级遍历（逐层遍历）

void BFS( TreeNode *root ){
    q[1] = root; //将根放入队首
    int front = 1, rear = 1; //由于定义根是从 1 开始的，所以rear = 1;
    while ( front <= rear ){ //当队列中还存在元素时
        TreeNode *p = q[front]; //每次取出队首元素对其进行处理（每次的根）
        front++；//取出队首元素后在队列中将其弹出，等待下次操作
        cout << p -> value << endl; //输出取出的根值（队首元素）
        if ( p -> l ) q[++rear] = p -> l; //将队首元素的左儿子放入队列
        if ( p -> r ) q[++rear] = p -> r; //将队首元素的右儿子防入队列

    }
}
BFS(root);//利用定义的BFS（）函数对此二叉树进行层级遍历

9. 求每个节点的深度

此处以层级遍历为例（且先序遍历、中序遍历和后序遍历都可以通过类似的方法求得）

在结构体TreeNode中定义deepth ——int deepth

且定义根的深度deepth为 1 ——root -> depth = 1

TreeNode *q[N];
void BFS( TreeNode *root ){
    q[1] = root;
    int front = 1, rear = 1;
    root -> depth = 1; //定义根（左、右儿子的fa）的深度为 1
    while ( front <= rear ){
            TreeNode *p = q[front]; 
        //将队首元素取出使用（因为通过指针定义，所以要取出通过指针方式使用）
             front++;
        //将无用的队首元素弹出
            if ( p -> l ) { 	  //如果左儿子存在
                p -> l -> deepth = p -> deepth + 1; 
                //对于每个左儿子，其深度为其爹（fa）的深度 + 1
                q[++rear] = p->l; //将左儿子放到队尾
            }
            if (p->r) {          //右儿子同理左儿子
                p -> r -> deepth = p -> deepth + 1;
                q[++rear] = p->r;
            }
        }
    }
BFS(root);//遍历结束后，二叉树中每一个节点的deepth就得到了

上述操作可以在遍历后将二叉树中每一个节点的深度（deepth）求得。

由于某些原因，课程进度赶不上了，最近得赶课了。

所以先把例题放放叭，之后再回头来敲，先看课T_T