树的基本概念

树的定义

树是个节点的有限集。当时，称为空树。在任意一颗空树中应满足：

• 有且只有一个特定称为根的节点
• 当时，其余节点可分为个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树。

显然，树的定义是递归的，即在书的定义中又用到了自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

• 树的根节点没有前驱，除根节点外的所有节点有且只有一个前驱。
• 树的所有节点可以有零个或多个后继。

树适合于表示具有层次的数据。树中的某个节点（除根节点外）最多只和上一层的一个节点（即其父节点）有直接关系，根节点没有直接上层节点，因此在个节点的树中有条边。而树中每个节点与其下一层的零个或多个节点（即其子女节点）有直接关系。

基本术语

• 树中一个节点的孩子个数称为该节点的度，树中节点的最大度数称为树的度。
• 度大于0的节点称为分支节点，度为0的节点称为叶子节点。在分支结点中，每个结点的分支数就是该结点的度。
• 结点的深度、高度和层次
  • 结点的深度是从根节点开始自顶向下逐层累加的
  • 结点的高度是从叶节点开始自底向上逐层累加的
  • 树的高度是树中节点的最大层数
• 有序树和无序树
  • 有序树：树中的结点的各子树从左到右是有次序的，不能互换（次序人为规定）
  • 无序树：否则成为无序树
• 路径和路径长度
  • 路径：由树中这两个结点之间所经过的结点序列构成的
  • 路径长度：路径所经过的边的数量
• 森林是棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根节点删去就成了森林。反之，只要给棵独立的树加上一个结点，并把这棵树作为该节点的子树，则森林就变成了树

树的性质

树具有如下基本性质：

• 树中的节点数等于所有结点度数之和加1
• 度为的树中第层上至多有
• 高度为的叉树最多有个节点
• 具有个结点的叉树的最小高度为

二叉树的概念

二叉树的定义及其主要特性

二叉树的定义

二叉树是另一种树形结构，其特点是每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能随意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是个结点的有限集合：

1. 或者为空二叉树，即
2. 或者由一个根节点和两个互不相等的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树

二叉树是有序树，若其左、右子树颠倒，则成为另一颗不同的二叉树，即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树与度为2的有序树的区别：

• 度为2的树至少有三个结点（否则度就没有2了），而二叉树可以为空
• 度为2的有序树的孩子的左右次序是相对于另一个孩子而言的，若某个结点只有一个子结点，则这个孩子就无需区分左右，因为两边啥也没有。而二叉树的左右次序是确定的，即不论子节点是否为空，其左右子节点的定位都是确定的。

特殊二叉树

• 满二叉树：
  • 高度为且结点数为的二叉树。即树中每层的结点都是满的。
  • 满二叉树的叶子结点均在最下一层，且除叶子结点外每个节点的度均为2 。
  • 满二叉树的编号：
    • 从根节点开始（根节点为1），自上到下，从左到右依次排号。
    • 若编号为的子节点有双亲，则双亲编号为，左孩子结点编号为，右孩子的结点编号为
• 完全二叉树：
  • 高度为、有个结点的二叉树，当且仅当其每个结点都与高度的满二叉树中编号为的结点一一对应时称为完全二叉树（人话版：所有节点的序号排列都和满二叉树里的排列一样）
  • 若，则有结点为分支节点，否则必为叶子结点。因为要一一对应的话，就会和满二叉树类似叶子结点几乎分布于最底层。
  • 叶子结点只可能在层次最大的两层上出现，最大层次中的叶子结点都依次排列在最左侧的位置上。意即从最底层的最左侧开始分布，一直排列到最右侧，排满了就是满二叉树了嗷。
  • 若有度为1的结点，则只可能有1个，且该结点只有左孩子。
  • 按层序编号后，一旦出现某节点为叶子结点或只有左孩子，则编号大于该节点的均为叶子结点（上一条性质为原理）
  • 若为奇数，则每个分支结点都有左孩子和右孩子，若为偶数，则编号最大的分支结点（编号为）只有左孩子，没有右孩子，其余分支结点左右孩子都有。
• 二叉排序树：
  • 左子树上所有结点的关键字均小于根节点的关键字；右子树上所有结点的关键字均大于根节点的关键字；左子树和右子树又各是一颗二叉排序树。
• 平衡二叉树：
  • 树上任意结点的左子树和右子树的深度之差不超过1 。

二叉树的性质

• 非空二叉树上的叶子结点数等于度为2的结点数加1，即
• 非空二叉树上第层上至多有个节点
• 高度为的二叉树至多有
• 对完全二叉树按从上到下、从左到右的顺序依次编号，则可以得到：
  • 当时，结点的双亲的编号为(向下取整)。并且当为偶数时，必为双亲左孩子，为奇数时，必为右孩子。
  • 当时，结点的左孩子编号为
  • 当时，结点的右孩子编号为
  • 结点所在的层（深度）为
• 具有个结点的完全二叉树的高度为或

二叉树的存储结构

顺序存储结构

二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下、自左向右地存储完全二叉树上地结点，即**将完全二叉树上编号为地结点存储在一维数组下标为中**

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储更加合适，树中结点的序号可以唯一反应结点的逻辑关系，这样既能节省存储空间，又能利用数组元素的下标值迅速地确定结点在二叉树中的位置。

但一般的二叉树中的空结点则需要在数组中相应位置进行补0，由此可能造成较大存储空间浪费

链式结构存储

使用结构体或类构建结点：

typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree

使用不同存储结构时，实现二叉树的操作算法也会不同，因此要根据实际应用场景选择合适的存储结构

在含有个结点的二叉链表中，含有个空链域。

二叉树的遍历和线索二叉树

二叉树的遍历

二叉树的遍历指按照某条搜索路径访问树中的每个节点，使得每个节点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个节点都可能有两颗子树，因此还需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，进而进行遍历。

常见的遍历次序有：先序(NLR)、中序(LNR)、后续(LRN)三种遍历算法，其中的序指的是根节点何时被访问，需要注意的是，左节点永远先于右节点被访问。

1、 先序遍历

• 若二叉树为空，则直接返回
• 先访问根节点
• 先序遍历左子树
• 先序遍历右子树

代码如下：

void PerOrder(BiTree T) {
  if(T != NULL) {
    visit(T);
    PerOrder(T->lchild);
    PerOrder(T->rchild);
  }
}

2、 中序遍历

• 若二叉树为空，直接返回
• 中序遍历左子树
• 访问根节点
• 中序遍历右子树

代码如下：

void InOrder(BiTree T) {
  if(T != NULL) {
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild)
  }
}

3、 后序遍历

• 后序遍历左子树
• 后序遍历右子树
• 访问根节点

代码如下：

void PostOrder(BiTree T) {
  if(T != BULL) {
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
  }
}

三种遍历算法中，不管采用哪种遍历算法，每个节点都访问一次且仅访问一次，故时间复杂度都是，在递归遍历中，递归工作栈的深度恰好为树的深度，故最坏情况下遍历算法的空间复杂度为。

递归算法和非递归算法的转换

中序遍历：

void InOrder2(BiTree T) {
  InitStack(S);
  BiTree p = T;

  while(p != NULL||!isEmpty(S)) {
    if(p != NULL) {
      //将根节点入栈并在下一个循环访问左节点
      Push(S,p);
      p=p->lchild;
    } else {
      //出栈根节点的同时访问根节点
      Pop(S,p);
      visit(p);
      //下一个循环访问右节点
      p=p->rchild;
    }
  }
}

先序遍历：

先序遍历的实现与中序遍历相似，只需要在入栈时先访问根节点即可

void PreOrder2(BiTree T) {
  InitStack(S);
  BiTree p = T;

  while(p != NULL||!isEmpty(S)) {
    if(p != NULL) {
      //访问根节点
      visit(p);
      //将根节点入栈并在下一个循环访问左节点
      Push(S,p);
      p=p->lchild;
    } else {
      //出栈根节点
      Pop(S,p);
      //下一个循环访问右节点
      p=p->rchild;
    }
  }
}

后序遍历

后序遍历算法思想与之前两种不同，需要保证在根节点出栈时右节点已被访问完。

void PostOrder(BiTree T) {
  InitStack(S);
  p=T;
  r=NULL;  //用于记录最近访问过的结点
  while(p != NULL||!IsEmpty(S)) {
    if (p) {
      Push(S,p);
      //走到最左边
      p=p->lchild;
    } else {
      //获取根节点
      Peek(S,p);
      if(p->rchild != NULL&&p->rchild != r) {
        //走到右边
        p=p->rchild;
      } else {
        Pop(S,p);
        visit(p);
        r=p;
        p=NULL;
      }
    }
  }
}

层次遍历

需要借助队列实现，每访问一个节点就将该节点的孩子节点输入队列，并将该节点出队

void LevelOrder(BiTree T) {
  InitQueue(Q);
  BiTree p;
  EnQueue(Q,T);
  while(!IsEmpty(Q)) {
    DeQueue(Q,p);
    visit(p);
    if(p->lchild != NULL) {
      EnQueue(Q,p->lchild);
    }
    if(p->rchild != NULL) {
      EnQueue(Q,p->rchild);
    }
  }
}

由遍历序列构建二叉树

• 二叉树的先序序列和中序序列可以唯一确定一颗二叉树
  • 先序遍历中第一个结点一定是二叉树的根节点；中序遍历中，根节点必然将中序序列分割为两个子序列，前一个子序列是根节点的左子树的中序序列，后一个子序列是根节点的右子树的中序序列。
• 二叉树的后序序列和中序序列也可以唯一确定一颗二叉树
• 二叉树的层序序列和中序序列也可以唯一确定一颗二叉树

除了先序序列和后序序列其余两种任意序列的组合都可以构建出二叉树。构建二叉树需要明确知道根节点和左右子树，而先序序列和后序序列无法确定左右子树。

线索二叉树

1. 概念
   遍历二叉树是以一定规则将二叉树中的节点排列成一个线性序列，从而得到几种遍历序列，使得该序列的每个节点（第一个和最后一个除外）都有一个直接前驱和直接后继。

   存储结构：

   typedef struct ThreadNode {
   ElemType data;  //数据
   struct ThreadNode *lchild,*rchild;  //左右指针
   int ltag,rta;  //左右线索标志，若为1则代表指向的是上级
   }

2. 构造
   二叉树的线索化是将二叉链表中的空指针改为指向前驱或者后继的线索。而前驱或后继的信息只有在遍历时才能得到。

   不同序列的线索二叉树其更新前结点(pre)的时机不同。比如中序线索二叉树：

   void InThread(ThreadTreee &p,ThreadTree &pre) {
   if(p!=NULL) {
    InThread(p->lchild,pre);
    if(p->lchild==NULL) {
      p->lchild=pre;
      p->ltag=1;
    }
   
    if(pre!=NULL&&pre->rchild==NULL) {
      pre->rchild=p;
      pre->stag=1;
    }
    pre=p;//中序
    InThread(p->rchild,pre);
   }
   }

   若通过中序建立中序线索二叉树，则在遍历的最后一个结点，还需要对最终右节点做处理：

   void CreateInThread(ThreadTree T) {
   ThreadTree pre = NULL;
   if(T!=NULL) {
    InThread(T,pre);
    pre->rchild=NULL;
    pre->rtag=1;
   }
   }

若将pre=p放置提前，则转为不同的序列线索二叉树
如先序线索二叉树：

void PreThread(ThreadTreee &p,ThreadTree &pre) {
  if(p!=NULL) {
    pre=p;  //先序
    InThread(p->lchild,pre);
    if(p->lchild==NULL) {
      p->lchild=pre;
      p->ltag=1;
    }

    if(pre!=NULL&&pre->rchild==NULL) {
      pre->rchild=p;
      pre->stag=1;
    }
    InThread(p->rchild,pre);
  }
}

如后序线索二叉树：

void PreThread(ThreadTreee &p,ThreadTree &pre) {
  if(p!=NULL) {
    InThread(p->lchild,pre);
    if(p->lchild==NULL) {
      p->lchild=pre;
      p->ltag=1;
    }

    InThread(p->rchild,pre);
    if(pre!=NULL&&pre->rchild==NULL) {
      pre->rchild=p;
      pre->stag=1;
    }
    pre=p;  //后序
  }
}