二叉树性质

• 非空二叉树上叶节点数等于双分支结点数加一
• 二叉树的第i层上至多有2^(i-1)个结点（满二叉树时最多）
• 深度为k的二叉树，至多有2^k-1个结点
• 具有n个结点的完全二叉树的深度必为 [log2n] + 1

二叉树的存储结构

顺序存储结构

二叉树的顺序存储结构就是用一组地址连续的存储单元来存放二叉树的数据元素，因此必须确定好树中各数据元素的存放数据，使得各数据元素在这个采访次序中的相互位置能反映出数据元素之间的逻辑关系。

对于完全二叉树（满二叉树），树中结点的层序编号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上到下，从左到右的顺序存储树中的所有结点值，通过数组元素的下标关系反映完全二叉树中结点之间的逻辑关系。而对于一般二叉树，则需要在建树中增添一些虚结点使之成为完全二叉树(例如'#'字符)。

对于一个下标编号为i的结点：

• 结点 i 的父结点为 i/2
• 结点 i 的左孩子为 2*i
• 结点 i 的右孩子为 2*i+1

• 使用数组存储类型声明：ElemType SqBTree[MaxSize];
• 优点：
• 完全二叉树或满二叉树适合使用顺序存储结构，最大可能节省空间
• 利用数组元素的下标可以确定结点在二叉树中的位置和结点之间的关系
  • 查找一个结点的孩子和双亲结点都很方便，下标为i的结点的层次为【log2(i+1)】
• 缺点
• 一般二叉树可能需要很多空结点构造完全二叉树，会造成空间大量浪费
• 二叉树的插入，删除等操作运算不方便

链式存储结构

二叉树的链式存储结构是指用一个链表来存储一棵二叉树，二叉树的每一个结点用链表中的一个结点来存储，二叉树链式存储结构中一个结点具有两个指针域和一个数据域。

• 结构体定义

  typedef struct node
  {
  ElemType data;//数据域
  struct node* lchild;//左孩子
  struct node *rchild;//右孩子
  }BTnode, * BTree;

还可在结点中加入一个指向双亲的指针域parent，构成二叉树的3叉链表。

• 优点：
• 对于一般二叉树比较节省空间
• 访问一个结点的孩子很方便，访问双亲不方便
  • 增加指向双亲的指针域parent可以解决

二叉树的构造

顺序结构创建二叉树

将二叉树的顺序存储结构转成二叉链，要先把二叉树补成满二叉树，之后进行递归建树

BinTree CreatBinTree(string str, int i)//递归建树
{
    BinTree bt;
    if (i > str.size()-1||i <= 0) return NULL;
    if (str[i] == '#') return NULL;
    bt = new TNode;
    bt->Data = str[i];
    bt->Left = CreatBinTree(str, i * 2);
    bt->Right = CreatBinTree(str, i * 2 + 1);
    return bt;
}

先序遍历递归建树

先建立根节点，再先序建立左子树，最后先序建立右子树。

BinTree CreatBinTree(string str, int& i)//递归建树
{
    BinTree bt;
    if (i > str.size() - 1) return NULL;
    if (str[i] == '#') return NULL;
    bt = new TNode;
    bt->Data = str[i];
    bt->Left = CreatBinTree(str, ++i);
    bt->Right = CreatBinTree(str, ++i);
    return bt;
}

例如：ABD#G###CEH###F#I##

层次法建树

设计思路：

取字符串第一个数据，创建根结点，入队列
while (队列不空)
{
    出队一个节点T
    取一个字符str[i]
        if (str[i++] == '#') T->lchild = NULL;
        else   生成T的左孩子，值str[i]， 并把左孩子入队列;
    取一个字符
        if (str[i++] == '#') T->rchild = NULL
        else   生成T的右孩子，值str[i]， 并把右孩子入队列;
}

二叉树的遍历

先序遍历

• 访问根节点

• 先序遍历左子树

• 先序遍历右子树

  即：根->左子树->右子树

代码实现：

void PreOrder(BTree bt)
{
    if (bt != NULL)
    {
        printf("%c", bt->data);//访问根节点
        PreOrder(bt->lchild);//先序遍历左子树
        PreOrder(bt->rchild);//先序遍历右子树
    }
}

• 注意：
• 递归调用从根节点开始，到根节点结束
• 每个结点访问两遍

中序遍历

• 中序遍历左子树

• 访问根节点

• 中序遍历右子树

  即：左子树->根->右子树

代码实现：

void InOrder(BTree bt)
{
    if (bt != NULL)
    {
        InOrder(bt->lchild);//中序遍历左子树
        printf("%c", bt->data);//访问根节点
        InOrder(bt->rchild);//中序遍历右子树
    }
}

后序遍历

• 后序遍历左子树

• 后序遍历右子树

• 访问根节点

  即：左子树->右子树->根

代码实现：

void PostOrder(BTree bt)
{
    if (bt != NULL)
    {
        PostOrder(bt->lchild);//遍历左子树
        PostOrder(bt->rchild);//遍历右子树
        printf("%c", bt->data);//访问根节点
    }
}

层次遍历

在进行层次遍历时，对某一层的结点访问完后，再按照他们的访问次序依次对各个结点的左，右孩子顺序访问。

层次遍历过程：

初始化一个队列，根节点入队
while (队列不为空)
{
    队列中出队一个结点，访问它;
    如果它有左孩子结点，入队;
    如果它有右孩子结点，入队;
}

代码实现：

void LevelOrder(BinTree bt)//层次遍历
{
    queue<BinTree>q;//初始化队列，元素为树节点
    BinTree p;
    int flag = 0;
    if (bt == NULL)//如果树空，输出NULL
    {
        cout << "NULL";
        return;
    }
    else q.push(bt);//如果树不空，根节点入队

    while (!q.empty())//当队列不空
    {
        p = q.front();//出队访问
        q.pop();
        if (flag == 0)
        {
            cout << p->Data;
            flag = 1;
        }
        else
            cout << " " << p->Data;

        if (p->Left != NULL)//如果该结点有左孩子，入队
            q.push(p->Left);
        if (p->Right != NULL)//如果该结点有右孩子，入队
            q.push(p->Right);
    }

}

还原二叉树

根据先序和中序序列还原二叉树

BTree CreateBT1(char* pre, char* in, int n)
{
    BTNode* s; char* p; int k;

    if (n <= 0) return NULL;
    s = new BTNode;
    s->data = *pre;// 创建根节点
    for (p = in; p < in + n; p++)//在中序中找为* ppos的位置k
        if (*p == *pre)
            break;
    k = p - in;
    s->lchild = CreateBT1(pre + 1, in, k);//构造左子树
    s->rchild = CreateBT1(pre + k + 1, p + 1, n - k - 1);//右子树
    return s;
}

根据中序和后序序列还原二叉树

BTRee CreateBT2(char* post, char* in, int n)
{
    BTNode* s; char* p; int k;
    if (n <= 0) return NULL;
    s = new BTNode; ///创建节点
    s->data = *(post + n - 1);//构造根节点。
    for (p = in; p < in + n; p++) //在中序中找为 * ppos的位置k
        if (*p == *(post + n - 1))
            break;
    k = p - in;
    s->lchild = CreateBT2(post, in, k); //构造左子树
    s->rchild = CreateBT2(post + k, p + 1, n - k - 1); // 构造右子树return s;
}

线索二叉树定义

对于n个结点的二叉树，当使用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域，又由于只有n-1个结点被有效指针所指向，则有2n-(n-1)=n+1个空链域。

遍历二叉树的结果是一个结点的线性序列，可以利用其中的空链域存放指向结点的前驱结点和后继结点的地址。

所以：

• 当某结点的左指针为空时，令该指针指向这个线性序列中该结点的前驱结点；

• 当某结点的右指针为空时，令该指针指向这个线性序列中该结点的后继结点；

  因此，这样的指向该线性序列中的“前驱结点”和“后继结点”的指针称为线索。

  创建线索的过程称为线索化，线索化的二叉树称为线索二叉树。

创建线索二叉树的目的是提高该遍历过程的效率，那么在线索二叉树中如何区分左指针指向左孩子结点还是前驱结点，右指针指向的是右孩子结点还是后继结点呢?

为此，在结点的存储结构上增加两个标志位来区分这两种情况

• 左标志 ltag：

  • ltag=0，表示lchild指向左孩子结点
  • ltag=1，表示lchild指向前驱结点

• 右标志 rtag

  • rtag=0，表示rchild指向右孩子结点

  • rtag=1，表示rchild指向后继结点

    这样，每个结点的存储结构为：

线索二叉树建立

建立线索二叉树，或者说对二叉树线索化，实际上就是遍历一棵二叉树，在遍历过程中检查当前结点的左右指针域是否为空，如果为空，将他们改为指向前驱节点或后继结点的线索。

中序线索二叉树特点

在线索二叉树中再加入一个头节点：

• 头节点的左孩子指向根节点

• 右孩子为线索，指向最后一个孩子

• 遍历序列第一个结点前驱为头节点，最后一个结点后继为头节点

• 在中序线索二叉树中找前驱：

  • 结点有左孩子，则为左子树最右那个孩子
  • 结点无左孩子，则为前驱线索指针指向结点

• 在中序线索二叉树中找后继：

  • 结点有右孩子，则为右子树最左孩子结点
  • 结点无右孩子，则为后继线索指针指向结点

多叉树存储结构

双亲存储结构

定义：双亲存储结构是一种顺序存储结构，用一组连续空间存储树的所以结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。

（因为除了根节点以外，每个结点只有唯一的双亲结点，将根节点的双亲结点位置设置为特殊值-1）

结构体定义：

typedef struct
{
    ElemType data;//结点的值
    int parent;//指向双亲的位置
}PTree[MaxSize];

特点：该结构利用了每个结点（根节点除外）只有唯一双亲的性质。

• 找某个结点的双亲结点十分容易
• 求某个结点的孩子结点不易，需要遍历整个存储结构

孩子链存储结构

在孩子链存储结构中，每个节点不仅包含结点值，还包括指向所有孩子结点的指针。由于树中每个结点的子树个数（即结点的度）不同，如果按各个结点的度设计变长结构，则会因为结点的孩子结点的指针域个数不同而导致算法实现非常麻烦。所以，孩子链存储结构可按树的度，即树中所有结点度的最大值来设计结点的孩子结点指针域个数。

结构体定义：

typedef struct node
{
    ElemType data;//结点的值
    struct node* sons[MaxSons];//指向孩子结点
}TSonNode;

特点：

• 查找某结点的孩子结点十分方便

• 查找某结点的双亲结点比较费时

• 可能存在较多的空指针域

  孩子兄弟链存储结构

  孩子兄弟链存储结构是为每个结点设计3个域，即一个数据域，一个指向该节点的左边的第一个孩子结点（长子）的指针域，一个指向该节点的下一个兄弟结点的指针域。

  结构体定义：

  typedef struct tnode
  {
  ElemType data;//结点的值
  struct tnode* son;//指向孩子结点
  struct tnode* brother;//指向兄弟结点
  }TSBNode;

特点：

• 每个结点固定两个指针域，且两指针有序，不能混淆
• 方便实现树与二叉树的相互转换
• 寻找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找

多叉树遍历

树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。

先根遍历

• 访问根节点

• 按照从左到右的顺序先根遍历根节点的每一棵子树

  先根遍历序列的第一个元素即为根节点对应的结点值

后根遍历

• 按照从左到右的顺序后根遍历根节点的每一棵子树

• 访问根节点

  **后根遍历序列的最后一个元素即为根节点对应的结点值

层次遍历

从根结点开始从上到下，从左到右的次序访问树中的每一个结点。

层次遍历序列的第一个元素即为根节点对应的结点值

遍历序列对比

• 先根遍历序列：A B E F C D G H I J K
• 后跟遍历序列：E F B C I J K H G D A
• 层次遍历序列：A B C D E F G H I J K

哈夫曼树定义

在许多应用中经常将树中的结点赋予一个有某种意义的数值，称此数值为该结点的权。

从根节点到该节点之间的路径长度与该节点上权的乘积称为结点的带权路径长度。

树中所有叶子节点的带权路径长度之和称为该树的带权路径长度，通常记为：

• n0：叶子节点的个数

• wi：第i个叶子结点的权值

• li：根到第i个叶子节点的路径长度

  在n0个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。

• 结构体定义：

  typedef struct
  {
  char data;//结点值
  int weight;//权重
  int parent;//双亲结点
  int lchild;//左孩子结点
  int rchild;//右孩子结点
  }HTNode, * HTree;

哈夫曼树构造

• 构造哈夫曼树的原则：

  • 权值越大的叶节点越靠近根节点
  • 权值越小的叶节点越远离根节点

• 构造哈夫曼树的过程：

  • 根据给定的n个权值，构造n棵只有根节点的二叉树
  • 选取根节点权值最小和次小的两棵二叉树作为左右子树构造一棵新的二叉树，新二叉树根节点权值为左右子树根节点之和
  • 在集合中删除左右子树的两棵二叉树，并将新建立的二叉树加入集合中
  • 重复2，3两步，直到只剩下一棵二叉树，这棵二叉树就是哈夫曼树

• 示例

1. 8个结点的权值大小如下：

2. 从19，21，2，3，6，7，10，32这8个数中选择两个权小结点。选中2，3。同时算出这两个结点的和5。

3. 继续从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。

4. 从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。又构造二叉树。

5. 依此类推，最终得到一棵哈夫曼树

哈夫曼树编码

在远程通讯中，要将待传字符转换成二进制的字符串。想使编码的总长度最短，可让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的字符串编码便可减少，可构造哈夫曼树来实现编码，即哈夫曼树编码。

• 哈夫曼树编码————根结点到叶子结点经过路径组成的 0，1 序列

  规定：

• 左分支用0表示

• 右分支用1表示

并查集的定义

并查集支持查找一个元素所属的集合以及两个元素各自专属的集合的合并等运算。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫分离集合，称之为并查集。

并查集是一种树形结构，又叫“不相交集合”，保持了一组不相交的动态集合，每个集合通过一个代表来识别，代表即集合中的某个成员，通常选择根结点做这个代表。

并查集树的运算操作

结构体定义:

typedef struct node
{
  int data;//结点对应人的编号
  int rank;//结点对应秩，即子树高度，在合并时会使用到
  int parent;//结点对应双亲下标
}UFSTree;//并查集树的结点类型

并查集树的初始化

void MAKE_SET(UFSTree t[],int n)//初始化并查集树
{
    int i;
    for (i = 1;i <= n;i++)
    {
        t[i].data = i;      //1数据为该人的编号
        t[i].rank = 0;      //秩初始化为0
        t[i].parent = i;    //双亲初始化指向自已
    }
}

并查集树的查找

int FIND_SET(UFSTree t[], int x)    //在x所在子树中查找集合编号
{
    if (x != t[x].parent)   //双亲不是自已
        return(FIND_SET(t, t[x].parent));   //递归在双亲中找x
    else
        return(x);  //双亲是自己，返回x
}

并查集树的合并

void UNION(UFSTree t[], int x, int y)     //将x和y所在 的子树合并
{
    x = FIND_SET(t, x);     //查找x所在分离集合树的编号
    y = FIND_SET(t, y);     //查找y所在分离集合树的编号
    if (t[x].rank > t[y].rank)      //y结点的秩小于x结点的秩
        t[y].parent = x;    //将y连到x结点上，x作为y的双亲结点
    else        //y结点的秩大于等于x结点的秩
    {
        t[x].parent = y;        //将x连到y结点上，y作为x的双亲结点
        if (t[x].rank == t[y].rank)     //x和y结点的秩相同
            t[y].rank++;        //y结点的秩增1
    }
}

并查集的应用

• 并查集主要用于求解亲戚关系，朋友圈应用等等价问题。
• 利用并查集解决问题的优势主要是：降低解决问题的时间复杂度，提高效率。

2. PTA实验作业

2.1 输出二叉树每层结点

层次遍历树中所有节点。输出每层树节点。

树结构按照树的先序遍历递归建树，比如先序遍历字符串“ABD#G###CEH###F#I##”#代表空节点。

输入格式:

输入一行字符串。空节点用#表示。

输出格式:

层次遍历二叉树，按照层次输出所在层及其包含节点，节点间要求,隔开，最后一个节点尾部带,。若二叉树为空，则输出NULL

解题思路：

对于输入的一行字符串，首先要将它进行先序递归建树，之后再进行层次遍历输出每层结点。

//这里着重介绍层次遍历输出每层结点
递归建树BT；
建立队列q，并对其初始化；
定义空结点p，lastnode，node；//p：遍历结点  lastnode，node：记录最后结点
定义flag = 0，高度h = 1；//flag：高度h是否已经输出，未输出为0，已经输出为1
if （树空）
输出NULL，return；
else 树的根节点BT入队；

while（树不为空）
{
    p = q队列出队访问的结点；
    该结点出队；
    if flag等于0
        输出高度h，更改flag状态flag = 1；
    输出该结点数据元素data；
    if 该节点有左孩子，左孩子入队；
        记录最后结点node = p->Left；
    if 该节点有右孩子，右孩子入队
        记录最后结点node = p->Right；
    if p等于lastnode&& q不为空    //说明一层结点已经完全遍历完，进入下一层遍历
        高度h++；
        更改flag状态：flag = 0；
        更改新一层最后结点：lastnode = node；
    end if；
}
end while；

代码实现：

知识点：

• 先序遍历递归建树
• 利用队列进行层次遍历
• 利用lastnode记录最后结点，知道每层结点在哪停止

在ZIP归档文件中，保留着所有压缩文件和目录的相对路径和名称。当使用WinZIP等GUI软件打开ZIP归档文件时，可以从这些信息中重建目录的树状结构。请编写程序实现目录的树状结构的重建工作。

输入格式:

输入首先给出正整数N（≤10^4),表示ZIP归档文件中的文件和目录的数量。随后N行，每行有如下格式的文件或目录的相对路径和名称（每行不超过260个字符）：路径和名称中的字符仅包括英文字母（区分大小写）；符号“\”仅作为路径分隔符出现；目录以符号“\”结束；不存在重复的输入项目；整个输入大小不超过2MB。

输出格式:

假设所有的路径都相对于root目录。从root目录开始，在输出时每个目录首先输出自己的名字，然后以字典序输出所有子目录，然后以字典序输出所有文件。注意，在输出时，应根据目录的相对关系使用空格进行缩进，每级目录或文件比上一级多缩进2个空格。

解题思路：

• 设计目录树结构体

• 进行初始化树，建根结点

• 对输入的字符串进行切割，分离文件名和目录名

• 对应产生树结点，插入建立目录树。

  伪代码：

  对结构体进行定义；
  初始化树，建立根节点root；
  输入字符串，进行建树；

  void CreatTree(Tree& bt, string str, int i)//建树，
  {
  新建结点temp，ptr；初始化结点；
  切割字符串；新节点name为该段字符；
  if 该段字符串为目录，isfile改为false；
  if (temp为文件)
  InitFile(temp, bt);//插入文件
  else //temp为目录
  InitList(temp, bt);//插入目录
  CreatTree(temp, str, i);
  }

  void InitList(Tree& temp, Tree& bt)//插入目录
  {
  定义结构体指针btr来遍历二叉树bt；
  btr = bt->child;//btr先指向bt的孩子；

      /*先对第一个兄弟结点进行判断*/
  if (没有第一个孩子|| btr为文件 || 第一个孩子字典序大于该结点)//可插入
      进行插入temp->brother = btr;bt->child = temp;//修改孩子指针
  else if (二者相等)
      直接使temp指向btr；
  else //查找兄弟节点
      while (btr->brother != NULL)
          if (兄弟节点为文件 || 兄弟节点字典序大于该节点)
              找到可插入位置，break；
          else if (二者相等)
              直接使temp指向btr->brother;break;
          else
              btr = btr->brother;//遍历下一兄弟结点；
  end if
      end while
      if (btr->brother为空 || btr->brother->name != temp->name)
          进行插入操作:temp->brother = btr->brother;btr->brother = temp;
  end if
      end if

  }

  void InitFile(Tree& temp, Tree& bt)//对文件temp找一个可插入位置
  {
  定义结构体指针btr来遍历二叉树bt；
  btr = bt->child;//btr先指向bt的孩子；

  if (第一个孩子为空 || btr为文件 && 结点字典序大于等于该节点)
      进行插入，修改bt的孩子指针；
  else //判断兄弟结点
      while (btr->brother != NULL)
          if (btr->brother为文件 && 兄弟节点字典序大于该节点)
              找到可插入位置，break;
          else
              btr = btr->brother;//遍历下一个兄弟结点
  end if
      end while
      对temp进行插入操作:temp->brother = btr->brother;btr->brother = temp;
  end if

  }

代码实现：

知识点：

• 使用孩子兄弟链结构
• 结构体中增加isfile判断一个结点是目录还是文件
• 目录与文件使用两个函数插入，分类讨论
  • 需要考虑是否有第一个孩子，孩子是目录还是文件，二者字典序大小等情况
  • 插入的顺序要求：目录在文件前面，字典序小的在前面

3. 阅读代码

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/count-complete-tree-nodes

bool exists(struct TreeNode* root, int level, int k) {
    int bits = 1 << (level - 1);
    struct TreeNode* node = root;
    while (node != NULL && bits > 0) {
        if (!(bits & k)) {
            node = node->left;
        } else {
            node = node->right;
        }
        bits >>= 1;
    }
    return node != NULL;
}

int countNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int level = 0;
    struct TreeNode* node = root;
    while (node->left != NULL) {
        level++;
        node = node->left;
    }
    int low = 1 << level, high = (1 << (level + 1)) - 1;
    while (low < high) {
        int mid = (high - low + 1) / 2 + low;
        if (exists(root, level, mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/wan-quan-er-cha-shu-de-jie-dian-ge-shu-by-leetco-2/
来源：力扣（LeetCode）

除了遍历树来统计结点个数以外，该题可利用完全二叉树的特性，利用二分查找和位运算来得到结点个数的答案。

规定根节点为第0层，完全二叉树最大高度为h，即完全二叉树结点个数为[2h,2(h+1)-1]范围。则在该范围内通过二分查找来确定结点个数。即根据节点个数范围的上下界得到当前需要判断的节点个数 k，如果第 k 个节点存在，则节点个数一定大于或等于 k，如果第 k 个节点不存在，则节点个数一定小于 k，由此可以将查找的范围缩小一半，直到得到节点个数。

那么如何判断第k个结点是否存在呢？

使用位运算的方法，找到二进制数与结点之间的关系，即可使用位运算得到答案。

如果第 k 个节点位于第 h 层，则 k 的二进制表示包含 h+1 位，其中最高位是 1，其余各位从高到低表示从根节点到第 k 个节点的路径，0 表示移动到左子节点，1 表示移动到右子节点。通过位运算得到第 k 个节点对应的路径，判断该路径对应的节点是否存在，即可判断第 k 个节点是否存在。

如：

• 两个函数，一个使用位运算判断该数字结点是否存在，一个使用二分运算确认结点个数
• 找到二进制树与二叉树结点位置之间的关系，利用其来判断结点是否存在
• 使用二分运算来提高统计结点的效率
• 时间复杂度：时间复杂度：O(\log^2 n)，其中 n 是完全二叉树的节点数
• 空间复杂度：O(1)