• 二叉树的创建、前序遍历、中序遍历、后序遍历
    时间:2008-09-06   作者:佚名   出处:互联网

    #include "stdafx.h"
    #include "stdlib.h"

    #define  MAX_NODE 100
    #define  NODE_COUNT1 8
    #define  NODE_COUNT2 15

    int TreeValue0[NODE_COUNT1][2] = {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}};
    int TreeValue1[NODE_COUNT1][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}};
    int TreeValue2[NODE_COUNT2][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}};
    struct BTree
    {
     int data;
     int order;
     BTree *lchild;
     BTree *rchild;
    };

    void Swap(int *p1,int *p2)
    {
     int t;
     t = *p1;
     *p1 = *p2;
     *p2 = t;
    }
    /*
    function CreateBTree()功能:创建一颗二叉树,并返回一个指向其根的指针
    */
    BTree *CreateBTree(int data[][2],int n)
    {
     BTree *Addr[MAX_NODE];
     BTree *p,
        *head;
     int nodeorder,//节点序号
      noderoot, //节点的双亲
      i;
     if(n>MAX_NODE)
     {
      printf("参数错误!\n");
      return(0);
     }
     for(i=1;i<=n;i++)
     {
      p = (BTree *)malloc(sizeof(BTree));
      if(p==NULL)
      {
       printf("内存溢出错误!\n");
       return(0);
      }
      else
      {
       p->data = data[i][0];
       p->lchild = NULL;
       p->rchild = NULL;
       nodeorder = data[i][1];
       p->order = nodeorder;
       Addr[nodeorder] = p;
       if(nodeorder>1)
       {
        noderoot = nodeorder/2;
        if(nodeorder %2 == 0)
         Addr[noderoot]->lchild = p;
        else
         Addr[noderoot]->rchild = p;
       }
       else
        head = p;
       printf("BTree[%d] = %c\t",p->order,p->data);
      }
      //free(p);
     }
     return(head);
    }

    /*
    function FirstOrderAccess0()功能:实现二叉树的前序遍历
    二叉树前序遍历的思想:
     从根节点开始,沿左子树一直走到没有左孩子的节点为止,
    依次访问所经过的节点,同时所经[节点]的地址进栈;
     当找到没有左孩子的节点时,从栈顶退出该节点的双亲的
    右孩子,此时,此节点的左子树已访问完毕;
     在用上述方法遍历该节点的右子树,如此重复到栈空为止。
    */
    void FirstOrderAccess0(BTree * header)
    {
     BTree * stack[MAX_NODE];
     BTree *p;
     int top;
     top = 0;
     p = header;
     do
     {
      while(p!=NULL)
      {
       printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
       top = top+1;
       stack[top] = p;
       p = p->lchild;//继续搜索节点P的左子树
      }
      if(top!=0)
      {
       p = stack[top];
       top = top-1;
       p = p->rchild;//继续搜索节点P的右子树
      }
     }while((top!=0)||(p!=NULL));
    }
    /*
    function FirstOrderAccess1()功能:实现二叉树的前序遍历
    二叉树前序遍历的思想:
     从根节点开始,沿左子树一直走到没有左孩子的节点为止,
    依次访问所经过的节点,同时所经[节点的非空右孩子]进栈;
     当找到没有左孩子的节点时,从栈顶退出该节点的双亲的
    右孩子,此时,此节点的左子树已访问完毕;
     在用上述方法遍历该节点的右子树,如此重复到栈空为止。
    */
    void FirstOrderAccess1(BTree * header)
    {
     BTree * stack[MAX_NODE];
     BTree *p;
     int top;
     top = 0;
     p = header;
     do
     {
      while(p!=NULL)
      {
       printf("BTree[%d] = %c\t",p->order,p->data);
       if(p->rchild!=NULL)
        stack[++top] = p->rchild;
       p = p->lchild;
      }
      if(top!=0)
       p = stack[top--];
     }while((top>0)||(p!=NULL));
    }

    /*
    function MiddleOrderAccess()功能:实现二叉树的中序遍历
    二叉树中序遍历的思想:
     从根节点开始,沿左子树一直走到没有左孩子的节点为止,
    并将所经[节点]的地址进栈;
     当找到没有左孩子的节点时,从栈顶退出该节点并访问它,
    此时,此节点的左子树已访问完毕;
     在用上述方法遍历该节点的右子树,如此重复到栈空为止。
    */
    void MiddleOrderAccess(BTree * header)
    {
     BTree * stack[MAX_NODE];
     BTree *p;
     int top;
     top = 0;
     p = header;
     do
     {
      while(p!=NULL)
      {
       stack[++top] = p;//节点P进栈
       p = p->lchild;  //继续搜索其左子树
      }
      if(top!=0)
      {
       p = stack[top--];//节点P出栈
       printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
       p = p->rchild;//继续搜索其左子树
      }
     }while((top!=0)||(p!=NULL));
    }

    /*
    function LastOrderAccess()功能:实现二叉树的后序遍历
    二叉树后序遍历的思想:
     从根节点开始,沿左子树一直走到没有左孩子的节点为止,
    并将所经[节点]的地址第一次进栈;
     当找到没有左孩子的节点时,此节点的左子树已访问完毕;
    从栈顶退出该节点,判断该节点是否为第一次进栈,如是,再
    将所经[节点]的地址第二次进栈,并沿该节点的右子树一直走到
    没有右孩子的节点为止,如否,则访问该节点;此时,该节点的
    左、右子树都已完全遍历,且令指针p = NULL;
     如此重复到栈空为止。
    */
    void LastOrderAccess(BTree * header)
    {
     BTree * stack[MAX_NODE];//节点的指针栈
     int count[MAX_NODE];//节点进栈次数数组
     BTree *p;
     int top;
     top = 0;
     p = header;
     do
     {
      while(p!=NULL)
      {
       stack[++top] = p;//节点P首次进栈
       count[top] = 0;
       p = p->lchild;   //继续搜索节点P的左子树
      }
      p = stack[top--];//节点P出栈
      if(count[top+1]==0)
      {
       stack[++top] = p;//节点P首次进栈
       count[top] = 1;
       p = p->rchild;  //继续搜索节点P的左子树
      }
      else
      {
       printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
       p = NULL;
      }
     }while((top>0));
    }
    /*
    function IsLeafNode()功能:判断给定二叉树的节点是否是叶子节点
    */
    int IsLeafNode(BTree *node)
    {
     if((node->lchild==NULL)&&(node->rchild==NULL))
      return(1);
     else
      return(0);
    }
    /*
    function PrintLeafNode()功能:输出给定二叉树的叶子节点
    */
    void PrintLeafNode(BTree *header)
    {
     BTree * stack[MAX_NODE];//节点的指针栈
     BTree *p;
     int top;
     p = header;
     top = 0;
     do
     {
      while(p!=NULL)
      {
       stack[++top] = p;
       p = p->lchild;//继续搜索节点P的左子树
      }
      if(top!=0)
      {
       p = stack[top--];
       if(IsLeafNode(p))
        printf("LNode[%d] = %c\t",p->order,p->data);//访问叶子节点
       p = p->rchild;//继续搜索节点P的右子树
      }
     }while(top>0||p!=NULL);
    }
    /*
    function HasTwoChildNode()功能:判断给定二叉树的节点是否存在两个孩子节点
    */
    int HasTwoChildNode(BTree *node)
    {
     if((node->lchild!=NULL)&&(node->rchild!=NULL))
      return(1);
     else
      return(0);
    }
    /*
    function SwapChildNode()功能:交换给定二叉树的所有节点的左、右孩子
    */
    void SwapChildNode(BTree *header)
    {
     BTree * stack[MAX_NODE];//节点的指针栈
     BTree *p;
     int top;
     p = header;
     top = 0;
     do
     {
      while(p!=NULL)
      {
       stack[++top] = p;
       p = p->lchild;//继续搜索节点P的左子树
      }
      if(top!=0)
      {
       p = stack[top--];
       if(HasTwoChildNode(p))
        Swap(&p->lchild->data,&p->rchild->data);//交换节点P的左、右孩子
       p = p->rchild;//继续搜索节点P的右子树
      }
     }while(top>0||p!=NULL);
    }


    int main(int argc, char* argv[])
    {
     BTree * TreeHeader;
     printf("二叉树创建数据结果:\n");
     TreeHeader = CreateBTree(TreeValue1,NODE_COUNT1-1);
     //TreeHeader = CreateBTree(TreeValue2,NODE_COUNT2-1);
     if (TreeHeader==0)
     {
      printf("二叉树创建失败!\n");
      return(0);
     }
     else
     {
      printf("\n二叉树前序遍历结果:\n");
      FirstOrderAccess1(TreeHeader);
      printf("\n二叉树中序遍历结果:\n");
      MiddleOrderAccess(TreeHeader);
      printf("\n二叉树后序遍历结果:\n");
      LastOrderAccess(TreeHeader);
      //printf("\n二叉树的所有叶子节点:\n");
      //PrintLeafNode(TreeHeader);
      //SwapChildNode(TreeHeader);
      //printf("\n二叉树交换孩子的结果:\n");
      //MiddleOrderAccess(TreeHeader);
      printf("\n程序运行完毕!\n");
      return 0;
     }
    }

    网友留言/评论

    我要留言/评论