18数(二叉数)

大家好，欢迎来到IT知识分享网。

非线性结构 —– 数（硬件的线性来解决实际中的非线性问题）

数

• 数定义

​ 专业定义：1. 有且只有一个称为根的节点

​ 2.有若干个互不相交的子数，这些子数本身也是一颗数

​ 通俗的定义：

​ 1.树由节点和边组成

​ 2.每个节点只有一个父节点但有多个字节点

​ 3.但有一个节点例外，该节点没有父节点，该节点称为根节点

​ 专业术语：

​ 节点 父节点 子节点

​ 子孙 堂兄弟

​ 深度：

​ 从根节点到最底层的层数称之为深度（根节点为第一层）

​ 叶子节点：

​ 没有子节点的节点

​ 非终端节点：

​ 非叶子节点

​ 度：

​ 子节点的个数称为度

• 数分类

  1. 一般数: 任意一个节点的子节点的个数都不受限制

  2. 二叉数：任意一个节点的子节点个数最多两个，且子节点的位置不可变更

  3. • 二叉数分类：
     • 一般二叉数
     • 满二叉数：每一层节点都是最大的
     • 完全二叉数：如果只是删除了满二叉数最底层最右边的连续若干个节点，这样形成的 二叉数就是完全

  4. 森林：n个互不相交的数的集合

• 数操作

• 数的存储

  • 二叉数的存储

    1.连续存储「完全二叉数」（二叉数顺序存储的重点）

    优点：查找某个节点的父节点和子节点（也包括判断有没节点）

    缺点：占用内存比较大

    2.链式存储

  • 一般数的存储

    • 双亲表示法：求父节点方便

    • 孩子表示法：求子节点方便

    • 双亲孩子表示法：求父节点和子节点都很方便

    • 二叉数表示法：把一个普通数转化为二叉数来存储

      具体转换方法：

      1. 把一个普通数转化为二叉数来存储

      2. 左指针域指向它的第一个孩子

      3. 右指针域指向它的下一个兄弟

         能满足此条件，就可以把一个普通数转化为二叉数

         一个普通的树转化为二叉数一定没有右子数

  • 森林的存储

    1. 先把森林转换成二叉数，再存储二叉数

• 操作

  面试必考点：数的遍历、已知两种遍历求原始的数据

  • 遍历

    • 先序遍历【先访问根节点】

      1. 先访问根节点
      2. 再先序访问左子树
      3. 再先序访问右子树

    • 中序遍历【中间访问根节点】

      1. 中序遍历左子树
      2. 再访问根节点
      3. 再中序遍历右子树

    • 后续遍历【后访问根节点】

      1. 中序遍历左子树

      2. 再中序遍历右子树

      3. 再访问根节点

    • 已知两种遍历序列求原始二叉数：中序确定左右子树，前后序确定根节点，先定首个根节点

      通过先序和中序 或者 中序和后序我们可以

      还原出原始的二叉树

      但是通过先序和后序是无法还原出原始的二叉树的

      换种说法：

      只有通过先序和中序，或者 中序和后续才可以确定唯一的二叉树

• 应用

         1. 数是数据库中数据组织的一种重要形式
  
      2. 操作系统子父进程本身就是一颗树
      2. 面向对象语言中类的继承关系本质是一个树（上是一般到特殊的关系）
      2. 赫夫曼树
  

  例题

  思路：

  • 能写出各种二叉数排列
  • 会由中序定左右子树，先后序定根节点
  • 先定根节点后由中序定左右子树还原出二叉数

  1.由二叉数写出先序排列，中序排列和后续排列

  2.由先序排列，中序排列得到后续排列

  3.由先序排列，后续排列得到中序排列

  链式二叉数程序(必考):静态创造

  # include <stdio.h>
  # include <malloc.h>
  
  //节点结构体
  struct BTNode
  {
      int data;
      struct BTNode * pLhild;//p是指针 L是左   child是孩子
      struct BTNode * pRhild;
  };
  
  int main(void)
  {
      struct BTNode * pT = CreateBTree();//根节点本身存储数据可能大，返回根节点地址
      PreTraverseBTree(pT); //先序遍历
      InTraverseBTree(pT);  //中序遍历
      PostTraverseBTree(pT);//后序遍历
      
      return 0;
  }
  //静态创造二叉树，返回根节点地址
  struct BTNode * CreateBTree(void)
  {
      struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode));
      struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode));
      struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode));
      struct BTNode * pD = (struct BTNode *)malloc(sizeof(struct BTNode));
      struct BTNode * pE = (struct BTNode *)malloc(sizeof(struct BTNode));
      
      pA->data = 'A';
      pB->data = 'B';
      pC->data = 'C';
      pD->data = 'D';
      pE->data = 'E';
     
      pA->pLchild = pB;
      pA->pRchild = PC;
      pA->pLchild = pA->pRhild =NULL;
      pC->pLchild = pD;
      pC->pRchild = NULL;
      pD->pLchild = NULL;
      pD->pRchild = pE;   
      pD->pLchild = pD->pRchild = NULL;
      
      return pA;
  }
  //先序遍历
  void PreTraverseBTree(BTNode * pT)
  {
      /*
      伪算法：
      先访问根节点
      再先序访问左子树
      再先序访问右子树
      */
      if(NULL !== pT)
      {
          printf("%c\n",pT->data);
          PreTraverseBTree(pT->pLhild);//左子树地址(pT->pLhild)传入调用先序遍历函数 
          PreTraverseBTree(pT->pRhild);
      }
     return;
  }
  //中序遍历
  void InTraverseBTree(BTNode * pT)
  {
      if(NULL !== pT)
      {
          PreTraverseBTree(pT->pLhild);//左子树地址(pT->pLhild)传入调用先序遍历函数 
          printf("%c\n",pT->data);
          PreTraverseBTree(pT->pRhild);
      }
     return;
  }
  //后序遍历
  void InTraverseBTree(BTNode * pT)
  {
      if(NULL !== pT)
      {
          PreTraverseBTree(pT->pLhild);//左子树地址(pT->pLhild)传入调用先序遍历函数 
          PreTraverseBTree(pT->pRhild);
          printf("%c\n",pT->data);
      }
     return;
  }
  
  

  链式二叉数（动态创造）