目录

🌳树

🌳树的概念

🌳树的基本术语

🌳树中节点之间的关系

🌳二叉树

🌳二叉树的定义

🌳二叉树的分类

🌳二叉树的性质

🌳二叉树的存储

 🌳二叉树的遍历

🌳二叉树遍历及递归实现

🌳二叉树遍历的非递归实现

🌳由遍历序列确定二叉树

🌳树

🌳树的概念

• 定义：树是n个(n>=0)节点的有限集合，当n=0时该树称为空树。
• 表示方法：树形表示法、嵌套集合表示法、广义表表示法、凹入表示法

🌳树的基本术语

• 结点(node)：包含一个数据元素以及若干指向其子树的分枝。
• 节点的度(degree)：节点拥有的子树的个数。
• 树的度：书中所有节点的度的最大值。
• 叶子节点(leaf)：度为0的节点，也称为“终端节点”。
• 内部节点(internal node)：度不为0的节点。

🌳树中节点之间的关系

• 孩子节点(child)：该节点的子树的根节点称为该节点的“孩子节点”。
• 双亲节点(parent)：该节点的上一层的直接节点。
• 兄弟节点(sibling)：同一双亲的孩子节点
• 祖先节点(ancestor)：从总根节点到该节点的路径上的所有节点
  子孙节点：该节点子树中的所有节点
• 节点的层次(level)：从树根开始，依次为第一层、第二层...
• 树的深度：树种所有节点的层次的最大值。

🌳二叉树

🌳二叉树的定义

• 二叉树(binary tree)是n(n>=0)个节点的有限集合。当n==0时，称为“空二叉树”，当n>0时，该集合由一个根节点以及互不相交的，被分别成为“左子树”和“右子树”的二叉树组成。
• 二叉树可以理解是满足以下两个条件的树形结构
  ①每个节点的度<=2
  ②节点的子树的位置是区分左右的，不能改变

🌳二叉树的分类

• 满二叉树：深度为k且含有2^k-1个结点的二叉树
• 完全二叉树：深度为k，节点数为n的二叉树，当且仅当n个结点与满二叉树1-n结点的位置一一对应时，称为完全二叉树

🌳二叉树的性质

• 在二叉树的第i层上至多有2^i-1个结点(i>=1)
• 深度为k的二叉树至多有2^k-1个结点
• 对任意一个二叉树，若终端节点数为n0，度为2的节点数为n2，则n0 = n2+1
• 具有n个结点的完全二叉树的深度为Floor(log2(n)+1)
• 对于一个连续编号的完全二叉树的任意序号i：
  ①i=1，结点i为根节点，无双亲结点；i>1，则结点i的双亲结点编号为Floor(i/2)。
  ②如果2i<=n，i的左孩子结点为2i，否则无左孩子。
  ③如果2i+1<=n，那么i的右孩子结点编号为2i+1，否则无右孩子。

🌳二叉树的存储

顺序存储结构

  1.对于满二叉树或者完全二叉树来说，可以按照将满二叉树编号的次序将各节点的数据存放到一组连续的存储单元中。但是对于普通的二叉树，如果使用这种方式存储，将浪费大量的存储空间。

 2.顺序存储结构的描述

#define MAX <存储单元的最大个数>
typedefstruct 
{
    datetype SqBiTree[MAX+1];//不使用0号存储单元
    int nodemax;             //数组中最后一个结点的下标
}Bitree;

链式存储结构

  ①二叉链表：对于任意的二叉树来说，可以设置包含：数据域、左孩子域、右孩子域的结点结构，不难看出，一个拥有n个结点的二叉树，必定含有2n个指针域，其中有n-1个指针域指向其孩子，n+1个指针域为空。二叉链表的结点的描述如下：

typedef struct Node 
{
    DateType data;
    struct Node* Lchild;
    struct Node* Rchild;
}BiTNode,*BiTree;

  ②三叉链表：如果需要方便的找到双亲结点，可以在二叉链表中增加Parent域指向其双亲结点

 🌳二叉树的遍历

🌳二叉树遍历及递归实现

  在此主要讨论先左后右的深度遍历。若用D、L、R分别表示访问根节点，遍历左子树，遍历右子树，则先左后右深度遍历的三种遍历方式如下：

• 先序遍历(DLR)：若二叉树为空，则返回空，否则执行：
  ①访问根节点
  ②先序遍历左子树
  ③先序遍历右子树
• 中序遍历(LDR)：若二叉树为空，返回空，否则执行：
  ①中序遍历左子树
  ②访问根节点
  ③中序遍历右子树
• 后序遍历(LRD)：若二叉树为空，返回空，否则执行：
  ①后序遍历左子树
  ②后续遍历右子树
  ③访问根节点

例如下述二叉树的先序中序后序遍历的到的序列为：

•  先序遍历序列：-+a×b-cd/ef
• 中序遍历序列：a+b×c-d-e/f
• 后序遍历序列：abcd-x+ef/-

先序，中序，后序三种二叉树遍历方法实现的算法描述：

//先序遍历二叉树的递归算法描述
void PreOrder(BiTree root) {
    if(root) {
        visit(root);
        PreOrder(root->Lchild);
        PreOrder(root->Rchild);
    }
}
//中序遍历二叉树的递归算法描述
void InOrder(BiTree root) {
    if(root) {
        InOrder(root->Lchild);
        Visit(root);
        InOrder(root->Rchild);
    }
}
//后续遍历二叉树的递归算法描述
void PostOrder(BiTree root) {
    if(root) {
        PostOrder(root->Lchild);
        PostOrder(root->Rchild);
        Visit(root);
    }
}

🌳二叉树遍历的非递归实现

• 先序遍历二叉树的非递归实现
  ①从根开始，当前结点存在或栈不为空，重复②③步骤。
  ②访问当前结点，当前节点入栈，进入其左子树，直至当前结点为空。
  ③如栈非空，则退栈顶结点，进入其右子树
  先序遍历二叉树的非递归算法描述：

  void PerOrder(BiTree root) {
      SeqStack *S;
      BiTree p;
      InitStack(S);
      p = root;
      while(p!=NULL || !IsEmpty(S)) {
          while(p!=NULL) {
              Visit(p->date);
              Push(S,p);
              p = p->Lchild;
          }
          if(! IsEmpty(S)) {
              Pop(S,&p);
              p = p->Rchild;
          }
      }
  }

• 中序遍历二叉树的非递归实现
  非递归算法描述1
  ①从根开始，当前节点存在或栈不为空，重复②③步骤
  ②当前节点进栈，进入其左子树，重复直至当前结点为空。
  ③若栈非空则退栈，访问出栈结点，进入其右子树。
  中序遍历二叉树非递归实现的算法描述：

  void InOrder1(BiTree root) {
      SeqStack* S;
      BiTree p;
      InitStack(S);
      p = root;
      while(p != NULL || !IsEmpty(S)) {
          while(p != NULL) {
              Push(S,p);
              p=p->Lchild;
          }
          if(!IsEmpty(S)) {
              Pop(S,&p);
              Visit(p->date);
              p = p-> Rchild;
          }
      }
  }

  非递归算法描述2
  ①从根开始，当前结点存在或栈不为空，重复②③步骤
  ②当前节点存在，当前结点入栈，进入其左子树
  ③否则，退栈访问初战结点，进入其右子树。
   

  void InOrder(BiTree) {
      SeqStack * S;
      BiTree p;
      while(p != NULL || !IsEmpty(S)) {
          if(!p) {
              Push(S,p);
              p=p->Lchild;
          } else {
              Pop(S,&p);
              Visit(p->date);
              p->=Rchild;
          }
      }
  }

• 后序遍历二叉树的非递归实现
  ①从根开始，当前结点存在或栈不为空，重复②③步骤
  ②当前结点进栈，进入左子树，重复直至当前结点为空
  ③若栈为非空，判断栈顶结点的右子树是否为空，右子树是否被访问过。是，则退栈，访问p结点，p赋值给q，p置为空；不是则进入p的右子树
   

  void PostOrder(BiTree root) {
      SeqStack * s;
      BiTree p,q;    //p为栈顶结点，q始终指向访问的结点
      InitStack(S);
      while(p != NULL || !IsEmpty(s)) {    //p为空并且栈为空，退出循环，完成后序非递归遍历
          while(p!=NULL) {
              Push(s,p);
              p->=Lchild;
          }
          if(!IsEmpty) {
              Top(s,&p);
              if((p->Rchild == q) || !(p->Rchild)) {
                  Pop(s,&p);
                  Visit(p->date);
                  q = p;
                  p=NULL;
              } else {
                  p->=Rchild;
              }
          }
      }
  }

• 层次遍历
  首先根节点入队，当队列非空时，重复以下步骤：
  ①对头结点出队，访问出队结点
  ②出队结点的非空左右孩子入队
  层次遍历二叉树的算法实现：
   

  void LevelOrder(BiTree root) {
      SeqQueue* Q;
      BiTree p;
      INitQueue(Q);
      EnterQueue(Q,root);
      while(!IsEmpty(Q)) {
          DeleteQueue(Q,&p);//队列中的先进入的结点取出赋值给p
          if(!(p->Lchild)) {
              EnterQueue(Q,p->Lchild);
          }
          if(!(p->Rchild)) {
              EnterQueue(p->Rchild);
          }
      }
  }

🌳由遍历序列确定二叉树

  结论：给定二叉树的先序和中序序列或者中序和后续序列，可以唯一确定一颗二叉树。对于给定的先序和后序序列，不能唯一确定一棵二叉树。

• 由先序(DLR)和中序(LDR)序列确定二叉树
  ①由先序序列的第一个结点确定根节点。
  ②由根节点分割中序序列。根节点之前是左子树L的中序序列，之后是右子树R的中序序列，同时还能确定L和R树的结点个数
  ③根据左子树L的节点个数，分割先序序列：首先是根节点，然后是递归下来的左子树序列，接着是右子树序列。
  例如：某二叉树的先序遍历序列和中序遍历序列为：
  先序序列：(18,14,7,3,11,22,35,27)
  中序序列：(3,7,11,14,18,22,27,35)
  可以得到该二叉树的结构为：
  
•  由中序(LDR)和后序(LRD)序列确定二叉树
  ①由后序序列的最后一个结点确定根节点。
  ②由根节点D分割中序序列，D之前是左子树L的中序序列，之后是右子树R的中序序列，同时获得L和R 的节点个数
  ③根据左子树L的节结点个数分割后序序列，首先是左子树L的后序序列，随后是右子树R 的后序序列，最后是根节点D。