• 二叉树创建及遍历算法(递归及非递归)
    时间:2008-09-06   作者:佚名   出处:互联网

    //二叉树处理头文件
    //包括二叉树的结构定义,二叉树的创建,遍历算法(递归及非递归),
    /*
     作者:成晓旭
     时间:2001年10月7日(18:49:38-20:00:00)
     内容:完成二叉树创建,二叉树的前,中,后序遍历(递归)
     时间:2001年10月7日(21:09:38-22:09:00)
     内容:完成二叉树的前,中序遍历(非递归)
     时间:2001年10月8日(10:09:38-11:29:00)
     内容:完成查找二叉树的静,动态查找(非递归)
    */
    #include "stdlib.h"

    #define MAXNODE 20
    #define ISIZE 8
    #define NSIZE0 7
    #define NSIZE1 8
    #define NSIZE2 15
    //SHOWCHAR = 1(显示字符) SHOWCHAR = 0(显示数字)
    #define SHOWCHAR 1
    //二叉树结构体
    struct BTNode
    {
     int data;
     BTNode *rchild;
     BTNode *lchild;
    };
    //非递归二叉树遍堆栈
    struct ABTStack
    {
     BTNode *ptree;
     ABTStack *link;
    };
    char TreeNodeS[NSIZE0] = {'A','B','C','D','E','F','G'};
    char PreNode[NSIZE0] = {'A','B','D','E','C','F','G'};
    char MidNode[NSIZE0] = {'D','B','E','A','C','G','F'};
    int TreeNodeN0[NSIZE1][2] = {{0,0},{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7}};
    int TreeNodeN1[NSIZE1][2] = {{0,0},{4,1},{2,2},{6,3},{1,4},{3,5},{5,6},{7,7}};
    int TreeNode0[NSIZE1][2] = {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}};
    int TreeNode1[NSIZE1][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}};
    int TreeNode2[NSIZE2][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7},{'H',8},{'I',9},{'J',10},{'K',11},{'L',12},{'M',13},{'N',14}};
    int InsertNode[ISIZE] = {-10,-8,-5,-1,0,12,14,16};
    //char *prestr = "ABDECFG";
    //char *midstr = "DBEACGF";
    /*
     二叉树创建函数dCreateBranchTree1()<递归算法>
     参数描述:
      int array[]: 二叉树节点数据域数组
      int i:   当前节点的序号
      int n:   二叉树节点个数
     返回值:
      dCreateBranchTree1 = 新建二叉树的根节点指针
     备注:
      根节点 = array[(i+j)/2];
      左子节点 = [array[i],array[(i+j)2-1]]
      右子节点 = [array[(i+j)/2+1,array[j]]
    */
    BTNode *dCreateBranchTree1(char array[],int i,int n)
    {
     BTNode *p; /*二叉树节点*/
     if(i>=n)
      return(NULL);
     p = (BTNode *)malloc(sizeof(BTNode));
     p->data = array[i];
     p->lchild = dCreateBranchTree1(array,2*i+1,n);
     p->rchild = dCreateBranchTree1(array,2*i+2,n);
     return(p);
    }
    /*
     二叉树创建函数dCreateBranchTree2()<递归算法>
     参数描述:
      int array[]: 二叉树节点数据域数组
      int i:   当前节点的序号
      int n:   二叉树节点个数
     返回值:
      dCreateBranchTree2 = 新建二叉树的根节点指针
     备注:
      根节点 = array[(i+j)/2];
      左子节点 = [array[i],array[(i+j)2-1]]
      右子节点 = [array[(i+j)/2+1,array[j]]
    */
    BTNode *dCreateBranchTree2(char array[],int i,int j)
    {
     BTNode *p; /*二叉树节点*/
     if(i>j)
      return(NULL);
     p = (BTNode *)malloc(sizeof(BTNode));
     p->data = array[(i+j)/2];
     p->lchild = dCreateBranchTree2(array,i,(i+j)/2-1);
     p->rchild = dCreateBranchTree2(array,(i+j)/2+1,j);
     return(p);
    }
    /*
     二叉树创建函数dCreateBranchTree3()<非递归算法>
     已知二叉树的前,中序遍历序列串,构造对应的二叉树
     <编程思想>:
      首先,在前序遍历序列中的首元素是二叉树的根节点,接着
     ,在中序遍历序列中找到此节点,那么在此节点以前的节点必为
     其左孩子节点,以后的必为其右孩子节点;
      然后,在中序遍历序列中,根节点的左子树和右子树再分别
     对应子树前序遍历序列的首字符确定子树的根节点,再由中序
     遍历序列中根节点的位置分别确定构成它们的左子树和右子树
     的节点;
      依次类推,确定二叉树的全部节点,构造出二叉树.
     参数描述:
      char *pre:  前序遍历序列
      char *mid:  中序遍历序列
      int n:   遍历序列中节点个数
     返回值:
      dCreateBranchTree3 = 新建二叉树的根节点指针
    */
    BTNode *dCreateBranchTree3(char *pre,char *mid,int n)
    {
     BTNode *p;
     char *t;
     int left;
     if(n<=0)
      return(NULL);
     p = (BTNode *)malloc(sizeof(BTNode));
     p->data = *pre;
     for(t=mid;t<mid+n;t++)
      if(*t==*pre) break;  /*在中序遍历序列中查找根节点*/
     left = t - mid;  /*左子树的节点个数*/
     p->lchild = dCreateBranchTree3(pre+1,t,left);
     p->rchild = dCreateBranchTree3(pre+1+left,t+1,n-1-left);
     return(p);
    }
    /*
     二叉树创建函数CreateBranchTree()<非递归算法>
     参数描述:
      int array[]: 二叉树节点数据域数组
      int n:   二叉树节点个数
     返回值:
      CreateBranchTree = 新建二叉树的根节点指针
    */
    BTNode *CreateBranchTree(int array[][2],int n)
    {
     BTNode *head,*p;
     BTNode *NodeAddr[MAXNODE]; //节点地址临时缓冲区
     int i,norder,rorder;
     head = NULL;
     printf("二叉树原始数据<新建顺序>:\t");
     for(i=1;i<=n;i++)
     {
      p = (BTNode *)malloc(sizeof(BTNode));
      if(p==NULL)
      {
       printf("\n新建节点时内存溢出!\n");
       return(NULL);
      }
      else
      {
       p->data = array[i][0];
       p->lchild = p->rchild = NULL;
       norder = array[i][1];
       NodeAddr[norder] = p;
       if(norder>1)
       {
        rorder = norder / 2; /*非根节点:挂接在自己的父节点上*/
        if(norder % 2 == 0)
         NodeAddr[rorder]->lchild = p;
        else
         NodeAddr[rorder]->rchild = p;
       }
       else
        head = p; /*根节点*/
       if(SHOWCHAR)
        printf("%c    ",p->data);
       else
        printf("%d    ",p->data);
      }
     }
     return(head);
    }
    //------------------------------递归部分------------------------------
    /*
     二叉树前序遍历函数dpre_Order_Access()<递归算法>
     参数描述:
      BTNode *head: 二叉树的根节点指针 
    */
    void dpre_Order_Access(BTNode *head)
    {
     if(head!=NULL)
     {
      if(SHOWCHAR)
       printf("%c    ",head->data);
      else
       printf("%d    ",head->data);
      dpre_Order_Access(head->lchild); /*递归遍历左子树*/
      dpre_Order_Access(head->rchild); /*递归遍历右子树*/
     }
    }
    /*
     二叉树中序遍历函数dmid_Order_Access()<递归算法>
     参数描述:
      BTNode *head: 二叉树的根节点指针 
    */
    void dmid_Order_Access(BTNode *head)
    {
     if(head!=NULL)
     {
      dmid_Order_Access(head->lchild); /*递归遍历左子树*/
      if(SHOWCHAR)
       printf("%c    ",head->data);
      else
       printf("%d    ",head->data);
      dmid_Order_Access(head->rchild); /*递归遍历右子树*/
     }
    }
    /*
     二叉树后序遍历函数dlast_Order_Access()<递归算法>
     参数描述:
      BTNode *head: 二叉树的根节点指针 
    */
    void dlast_Order_Access(BTNode *head)
    {
     if(head!=NULL)
     {
      dlast_Order_Access(head->lchild); /*递归遍历左子树*/
      dlast_Order_Access(head->rchild); /*递归遍历右子树*/
      if(SHOWCHAR)
       printf("%c    ",head->data);
      else
       printf("%d    ",head->data);
     }
    }
    //------------------------------递归部分------------------------------
    //------------------------------非递归部分------------------------------
    /*
     二叉树前序遍历函数pre_Order_Access()<非递归算法>
     参数描述:
      BTNode *head: 二叉树的根节点指针 
    */
    void pre_Order_Access(BTNode *head)
    {
     BTNode *pt;
     ABTStack *ps,*top;
     pt = head;
     top = NULL;
     printf("\n二叉树的前序遍历结果<非递归>:\t");
     while(pt!=NULL ||top!=NULL)  /*二叉树未遍历完,或堆栈非空*/
     {
      while(pt!=NULL)
      {
       if(SHOWCHAR)
        printf("%c    ",pt->data);  /*访问根节点*/
       else
        printf("%d    ",pt->data);  /*访问根节点*/
       ps = (ABTStack *)malloc(sizeof(ABTStack));  /*根节点进栈*/
       ps->ptree = pt;
       ps->link = top;
       top = ps;
       pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
      }
      if(top!=NULL)
      {
       pt = top->ptree; /*栈顶节点出栈*/
       ps = top;
       top = top->link;
       free(ps); /*释放栈顶节点空间*/
       pt = pt->rchild; /*遍历节点右子树*/
      }
     }
    }
    /*
     二叉树中序遍历函数mid_Order_Access()<非递归算法>
     参数描述:
      BTNode *head: 二叉树的根节点指针
    */
    void mid_Order_Access(BTNode *head)
    {
     BTNode *pt;
     ABTStack *ps,*top;
     int counter =1;
     pt = head;
     top = NULL;
     printf("\n二叉树的中序遍历结果<非递归>:\t");
     while(pt!=NULL ||top!=NULL)  /*二叉树未遍历完,或堆栈非空*/
     {
      while(pt!=NULL)
      { 
       ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
       ps->ptree = pt;
       ps->link = top;
       top = ps;
       pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
      }
      if(top!=NULL)
      {
       pt = top->ptree; /*栈顶节点出栈*/
       ps = top;
       top = top->link;
       free(ps); /*释放栈顶节点空间*/
       if(SHOWCHAR)
        printf("%c    ",pt->data); /*访问根节点*/
       else
        printf("%d    ",pt->data); /*访问根节点*/
       pt = pt->rchild; /*遍历节点右子树*/
      }
     }
    }
    /*
     二叉树后序遍历函数last_Order_Access()<非递归算法>
     参数描述:
      BTNode *head: 二叉树的根节点指针 
    */
    void last_Order_Access(BTNode *head)
    {
     BTNode *pt;
     ABTStack *ps,*top;
     int counter =1;
     pt = head;
     top = NULL;
     printf("\n二叉树的后序遍历结果<非递归>:\t");
     while(pt!=NULL ||top!=NULL)  /*二叉树未遍历完,或堆栈非空*/
     {
      while(pt!=NULL)
      { 
       ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
       ps->ptree = pt;
       ps->link = top;
       top = ps;
       pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
      }
      if(top!=NULL)
      {
       pt = top->ptree; /*栈顶节点出栈*/
       ps = top;
       top = top->link;
       free(ps); /*释放栈顶节点空间*/
       printf("%c    ",pt->data); /*访问根节点*/
       pt = pt->rchild; /*遍历节点右子树*/
      }
     }
    }
    /*
     二叉查找树静态查找函数static_Search_STree()<非递归算法>
     参数描述:
      BTNode *head: 二叉查找树的根节点指针
      int key:  查找关键码
     返回值:
      static_Search_STree = 键值为key的节点指针(找到)
      static_Search_STree = NULL(没有找到)
    */
    BTNode *static_Search_STree(BTNode *head,int key)
    {
     while(head!=NULL)
     {
      if(head->data == key)
      {
       printf("\n数据域=%d\t地址=%d\t\n",head->data,head);
       return(head); /*找到*/
      }
      if(head->data > key)
       head = head->lchild; /*继续沿左子树搜索*/
      else
       head = head->rchild; /*继续沿右子树搜索*/
     }
     return(NULL); /*没有查找*/
    }
    /*
     二叉查找树动态查找函数dynamic_Search_STree()<非递归算法>
     参数描述:
      BTNode *head:  二叉查找树的根节点指针
      BTNode **parent: 键值为key的节点的父节点指针的指针
      BTNode **head:  键值为key的节点指针的指针(找到)或NULL(没有找到)
      int key:   查找关键码
     注意:
      *parent == NULL 且 *p == NULL 没有找到(二叉树为空)
      *parent == NULL 且 *p != NULL 找到(找到根节点)
      *parent != NULL 且 *p == NULL 没有找到(叶节点)<可在parent后插入节点>
      *parent != NULL 且 *p != NULL 找到(中间层节点)
    */
    void dynamic_Search_STree(BTNode *head,BTNode **parent,BTNode **p,int key)
    {
     *parent = NULL;
     *p = head;
     while(*p!=NULL)
     {
      if((*p)->data == key)
       return; /*找到*/
      *parent = *p; /*以当前节点为父,继续查找*/
      if((*p)->data > key)
       *p = (*p)->lchild; /*继续沿左子树搜索*/
      else
       *p = (*p)->rchild; /*继续沿右子树搜索*/
     }
    }
    /*
     二叉查找树插入节点函数Insert_Node_STree()<非递归算法>
     参数描述:
      BTNode *head: 二叉查找树的根节点指针
      int key:  查找关键码
     返回值:
      Insert_Node_STree = 1 插入成功
      Insert_Node_STree = 0 插入失败(节点已经存在)
    */
    int Insert_Node_STree(BTNode *head,int key)
    {
     BTNode *p,*q,*nnode;
     dynamic_Search_STree(head,&p,&q,key);
     if(q!=NULL)
      return(0);  /*节点在树中已经存在*/
     nnode = (BTNode *)malloc(sizeof(BTNode)); /*新建节点*/
     nnode->data = key;
     nnode->lchild = nnode->rchild = NULL;
     if(p==NULL)
      head = p; /*原树为空,新建节点为查找树*/
     else
     {
      if(p->data > key)
       p->lchild = nnode; /*作为左孩子节点*/
      else
       p->rchild = nnode; /*作为右孩子节点*/
     }
     return(1); /*插入成功*/
    }
    /*
     二叉查找树插入一批节点函数Insert_Batch_Node_STree()<非递归算法>
     参数描述:
      BTNode *head: 二叉查找树的根节点指针
      int array[]: 被插入的数据域数组
      int n:   被插入的节点数目
    */
    void Insert_Batch_Node_STree(BTNode *head,int array[],int n)
    {
     int i;
     for(i=0;i<n;i++)
     {
      if(!Insert_Node_STree(head,array[i]))
       printf("\n插入失败<键值为%d的节点已经存在>!\n",array[i]);
     }
    }
    //------------------------------非递归部分------------------------------

    网友留言/评论

    我要留言/评论