数据结构第五章(中)

• 二叉树先序遍历算法

  Status PreOrderTiraverse（BiTree T）{
      if(T==NULL)return OK;
      else{
          visit(T);								//访问根结点
          PreOrderTiraverse(T->lchild);			//递归遍历左子树，递归调用
          PreOrderTiraverse(T->rchild);			//递归遍历右子树
      }
  }

  • 

    其中涉及到了递归调用的逐层返回

    

如果去掉输出语句，从递归的角度看，三种三发事完全相同的，只是访问的十几不同

时间复杂度是3n，其中3是常数可以去掉，所以O(n)

5.5.1.1 遍历二叉树的非递归算法

• 二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树

• 基本思想

  1. 建立一个栈

  2. 根结点进栈，遍历左子树

  3. 根结点出栈，输出根结点，遍历右子树

  4. Status InOrderTraverse(BiTree T){
         BiTree p;InitStack(S);P=T;
         while(p||!StackEmpty(S)){		//StackEmpty（S），S空返回true,非空返回false
             if(p){Push (S,p); p=p->lchild;}//push（S，p）是把p值入栈S
             else {Pop(S,q); printf("%c", q->data);//pop（S，q）是出栈值给q
                  p=q->rchild;}
         }//while
     }
          ***走到D时，左右子树都为空返回时，q会指向A应为栈内一开始就存放了A，然后再访问A的右子树***
     
     ##### 5.5.1.2 二叉树的层次遍历
     
     - 队列类型定义
     
       ```c
       typedef struct{
           BTNode data[MaxSize];
           int front,rear;
       }SqQueue;
     
     

  二叉树层次遍历算法：

  void LevelOrder(BTNode*b){
      BTNode *p;   SqQueue *qu;
      InitQueue(qu);//初始化队列
      enQueue(qu, b);//根结点指针进入队列
      while(!QueueEmpty（qu)）{
          deQueue(qu,p);//出队结点p
          printf("%c",p->data);//访问结点p
          if(p->lchild!=NULL)enQueue(qu,p->lchild);//有左孩子时将其进队
          if(p->rchild!=NULL)enQueue(qu,p->rchild);//有右孩子时将其进队
      }
  }

5.5.1.3 遍历算法的应用——二叉树的建立

• 算法描述：

Statys CreatBiTree(BiTree &T){
    scanf(&ch);
    if(ch=="#")T=NULL;
    else{
        if(!(BiTNode*)malloc(sizeof(BiTNode)))	//分配一块儿结点空间
            exit(OVERFLOW);	
        T->data=ch;								//生成根结点
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

5.5.1.4 复制二叉树

int Copy(BiTree T,BiTree &NewT){
    if(T==NULL){
        NewT==NULL;return 0;
    }
    else{
        NewT=new BiTNode;
        NewT->data=T->data;
        copy(T->lchild, NewT->lchild);
        copy(T->rchild, NewT->rchild);
    }
}

5.5.1.5 计算二叉树的深度

• 如果是空树，则深度为0

​ 否则，递归计算左子树深度记为m，右子树深度为n，二叉树深度则为n和m的较大者加1

int Depth(BiTree T){
    if(T==NULL) return 0;
    else {
        m=Depth {T->lchild); 
		n=Depth {T->rchild);
		if{m>n) return{m+l);
        else return(n+l);
    }
}

5.5.1.6 计算二叉树的结点总数

• 如果是空树，则结点个数为0

​ 否则，结点个数为左子树的结点个数+右子树的结点个数再加1

int NodeCount(BiTree T){
    if (T==NULL) 
        return O;
    else
        return NodeCount (T->lchild) +Node Count (T->rchild) + 1;
}

5.5.1.7 计算二叉树叶子结点数

int leafcount(BiTree T){
    if(T=NULL)
        return 0:
    if(T->lchild==NULL&&T->rchild==NULL)
        return 1;
    else
        return LeafCount(T->lchild)+LeafCount(T->rchild;)
}

5.5.2 线索二叉树

• 利用二叉链表中的空指针域：

  如果某个节点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果右孩子为空，则其指针域改为指向其后继————将改变指向的指针称为**“线索”，加上了线索的二叉树称为线索二叉树**

  

• 为了区分是指向孩子的指针还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域ltag和rtag，这样结点的结构就为【lchild | ltag | data | rtag | rchild 】并约定：

  • ltag=0/rtag=0 指针指向孩子

  • ltag=1/rtag=1 指针指向前驱/后继

    

5.6 树和森林

本节将讨论树的表示及其遍历操作，并建立森林与二叉树的对应关系。

5.6.1 树的存储结构

5,6,6,1 双亲表示法

实现：定义结构数组存放树的结点，每个结点含两个域；

• 数据域：存放结点本身信息

• 双亲域：指示本结点的双亲结点在数组中的位置
  

• C语言的类型描述：

  typedef struct PTNode{
      TElemType data;
      int parent;
  }PTNode;

• 树结构：

  #define MAX_TREE_SIZE 100
  typedef struct{
      PTNode nodes[MAX_TREE_SIZE];
      int r,n;//根结点的位置和结点个数
  }

5.6.1.2 孩子链表

• 把每个结点的孩子结点排列起来。看成一个线性表，用单链表存储

• C语言描述：

  typedef struct CTNode{
      int child;
      struct CTNode *next;
  }*Childptr;

• 树结构

  typedef struct{
      CTBox nodes[MAX_TREE_SIZE];
      int n,r;
  }CTree;

5.6.1.3 孩子兄弟表示法

• C语言描述

  typedef struct CSNode{
      ElemType data;
      struct CSNode *firstchild,*nextsibling;
  }CSNode,*CSTree;

  

5.6.2 树与二叉树的转换

• 将树转换为二叉树进行处理，利用二叉树的算法来实现对树的操作。

• 由于树和二叉树都可以用二叉链表做存储结构，则以二叉链表做媒介可以导出树与二叉树之间的一个对应关系。

• 给定一棵树可以找到唯一的一颗二叉树与之对应

  • 加线：在兄弟之间加一条线，

  • 抹线：对每个结点，除了其左孩子外，去除其余孩子之间的关系

  • 旋转：以树根结点为轴心，将整树顺时针旋转45°

    树变二叉树：兄弟相连留长子。其中根结点的油茶树一定为空

• 反之可以把二叉树转换成树

  • 加线：若p结点是双亲节点的左孩子，则将p的右孩子，右孩子的右孩子……沿分支找到所有右孩子，都与p的双亲用线连起来

  • 抹线：抹掉原二叉树中双亲与右孩子之间的连线

  • 调整：将结点按层次排列，形成树结构。

    二叉树变树：左孩右右连双亲，去掉原来右孩线

5.6.3 森林与二叉树的转换

• 森林转换成二叉树（二叉树与多棵树之间的关系）

  • 将个棵树分别转换成二叉树

  • 将每棵树的根结点用线相连

  • 以第一课树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

    森林变二叉树：树变二叉根相连

• 二叉树转换成森林

  • 抹线：将二叉树中根结点与其右孩子连线，及沿有分支搜索到的所有右孩子之间的连线抹掉，使之变成孤立的二叉树

  • 还原：将孤立的二叉树还原成树

    二叉树变森林：去掉全部右孩线，孤立二叉再还原

5.6.4 树和森林的遍历

5.6.4.1树的遍历

• 先根遍历：若树不为空，则先访问根结点，然后一次先根遍历各棵子树。
• 后根遍历：若树不为空，则先依次后根遍历各棵子树，然后访问根结点。
• 层次遍历：若树不为空，则自上而下自左至右访问树种每个结点。

5.6.4.2 森林的遍历

• 将森林看作由三部分构成：

  1. 森林中第一棵树的根结点；
  2. 森林中第一棵树的子树森林；
  3. 森林中其他树构成的森林。

• 先序遍历：若森林不为空，则依次从左至右对森林中的每一棵树进行先根遍历

• 中序遍历：若森林不为空，则

  1. 中序遍历森林中第一棵树的子树森林；

  2. 访问森林中第一棵树的根结点；

  3. 中序遍历森林中（除第一棵树之外）其余树构成的森林。

     即：依次从左至右对森林中每一个棵树进行后根遍历