数据结构——树的双亲表示法

  
  
  

   
   
   
   
   
   #include 
   
   
   <
   
   
   iostream
   
   
   >
   
   
   

   
   
   using
   
   
    
   
   
   namespace
   
   
    std;


   
   
   #define
   
   
    MAX_TREE_SIZE 100
   
   
   
typedef 
   
   
   struct
   
   
    
   
   
   //
   
   
   节点结构
   
   
   

   
   
   {

   
   
   char
   
   
    data;

   
   
   int
   
   
    parent; 
   
   
   //
   
   
   双亲位置域
   
   
   

   
   
   }PTNode;

typedef 
   
   
   struct
   
   
    
   
   
   //
   
   
   树结构
   
   
   

   
   
   {
 PTNode node[MAX_TREE_SIZE];

   
   
   int
   
   
    count; 
   
   
   //
   
   
   根的位置和节点个数
   
   
   

   
   
   }PTree;


   
   
   //
   
   
   初始化树
   
   
   

   
   
   void
   
   
    init_ptree(PTree 
   
   
   &
   
   
   tree)
{
 tree.count
   
   
   =-
   
   
   1
   
   
   ;
}

   
   
   //
   
   
   添加节点
   
   
   

   
   
   void
   
   
    add_ptnode(PTree 
   
   
   &
   
   
   tree, PTNode ptnode)
{
 tree.count
   
   
   ++
   
   
   ;
 tree.node[tree.count].data 
   
   
   =
   
   
    ptnode.data;
 tree.node[tree.count].parent 
   
   
   =
   
   
    ptnode.parent;
}

   
   
   //
   
   
   输出树
   
   
   

   
   
   void
   
   
    print_ptree(PTree 
   
   
   &
   
   
   tree)
{

   
   
   int
   
   
    i;

   
   
   for
   
   
   (i
   
   
   =
   
   
   0
   
   
   ;i
   
   
   <=
   
   
   tree.count;i
   
   
   ++
   
   
   )
 {
 cout
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   i
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   tree.node[i].data
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   tree.node[i].parent
   
   
   <<
   
   
   endl;
 }
}

   
   
   //
   
   
   前序遍历
   
   
   

   
   
   void
   
   
    PreOrder(PTree 
   
   
   &
   
   
   tree , 
   
   
   int
   
   
    num)
{

   
   
   for
   
   
   (
   
   
   int
   
   
    i
   
   
   =
   
   
   num; i
   
   
   <=
   
   
   tree.count; i
   
   
   ++
   
   
   )
 {

   
   
   if
   
   
   (i 
   
   
   ==
   
   
    num)
 {
 cout
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   i
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   tree.node[i].data
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   tree.node[i].parent
   
   
   <<
   
   
   endl;

   
   
   for
   
   
   (
   
   
   int
   
   
    j
   
   
   =
   
   
   num
   
   
   +
   
   
   1
   
   
    ; j
   
   
   <=
   
   
   tree.count; j
   
   
   ++
   
   
   )
 {

   
   
   if
   
   
   (tree.node[j].parent 
   
   
   ==
   
   
    i)
 {
 PreOrder(tree , j);
 }
 }
 }
 }
}
   
   
   //
   
   
   PreOrder

   
   
   //
   
   
   树没有中序遍历

   
   
   //
   
   
   后序遍历
   
   
   

   
   
   void
   
   
    BackOrder(PTree 
   
   
   &
   
   
   tree , 
   
   
   int
   
   
    num)
{

   
   
   for
   
   
   (
   
   
   int
   
   
    i
   
   
   =
   
   
   num; i
   
   
   <=
   
   
   tree.count; i
   
   
   ++
   
   
   )
 {

   
   
   if
   
   
   (i 
   
   
   ==
   
   
    num)
 {

   
   
   for
   
   
   (
   
   
   int
   
   
    j
   
   
   =
   
   
   num
   
   
   +
   
   
   1
   
   
    ; j
   
   
   <=
   
   
   tree.count; j
   
   
   ++
   
   
   )
 {

   
   
   if
   
   
   (tree.node[j].parent 
   
   
   ==
   
   
    i)
 {
 BackOrder(tree , j);
 }
 }
 cout
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   i
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   tree.node[i].data
   
   
   <<
   
   
   "
   
   
    
   
   
   "
   
   
   <<
   
   
   tree.node[i].parent
   
   
   <<
   
   
   endl;

 }
 }
}
   
   
   //
   
   
   BackOrder
   
   
   

   
   
   

   
   
   int
   
   
    main()
{
 FILE 
   
   
   *
   
   
   fin
   
   
   =
   
   
   fopen(
   
   
   "
   
   
   树的表示法.txt
   
   
   "
   
   
   ,
   
   
   "
   
   
   r
   
   
   "
   
   
   );

 PTree ptree;
 init_ptree(ptree);
 PTNode ptnode;


   
   
   while
   
   
   (fscanf(fin,
   
   
   "
   
   
   %c%d
   
   
   "
   
   
   ,
   
   
   &
   
   
   ptnode.data,
   
   
   &
   
   
   ptnode.parent)
   
   
   !=
   
   
   EOF)
 {
 add_ptnode(ptree,ptnode);
 fscanf(fin,
   
   
   "
   
   
   %c%d
   
   
   "
   
   
   ,
   
   
   &
   
   
   ptnode.data,
   
   
   &
   
   
   ptnode.parent);
 }

   
   
   //
   
   
   输出树
   
   
   

   
   
    cout
   
   
   <<
   
   
   "
   
   
   数组下标 节点值 双亲位置
   
   
   "
   
   
   <<
   
   
   endl;
 print_ptree(ptree);



   
   
   //
   
   
   前序遍历

   
   
   //
   
   
   cout<<endl;

   
   
   //
   
   
   PreOrder(ptree,0);


   
   
   //
   
   
   后序遍历

   
   
   //
   
   
   cout<<endl;

   
   
   //
   
   
   BackOrder(ptree,0);
   
   
   

   
   
   
 fclose(fin);

   
   
   return
   
   
    
   
   
   0
   
   
   ;
}