现在的位置: 首页 > 综合 > 正文

数据结构(C++) 二叉树完全源代码

2013年10月26日 ⁄ 综合 ⁄ 共 2945字 ⁄ 字号 小 中 大 ⁄ 评论关闭
Code:
  1. typedef struct btreenode   
  2. {   
  3.  char data;   
  4.  struct btreenode *lchild;   
  5.  struct btreenode *rchild;   
  6. }BTreeNode, * BTree;   
  7.   
  8. typedef struct  
  9. {   
  10.  BTree link;   
  11.  int flag;   
  12. }Stack;   
  13.   
  14. void InitBTree(BTree &BT)   
  15. {   
  16.  BT = NULL;   
  17. }   
  18.   
  19. void CreatBTree(BTree &BT)   
  20. {   
  21.   
  22.  char ch;   
  23.  ch = getchar();   
  24.  if (ch == ' ')    
  25.   BT = NULL;   
  26.   else  
  27.   {   
  28.    BT = new BTreeNode;   
  29.    BT->data = ch;   
  30.          CreatBTree(BT->lchild);   
  31.    CreatBTree(BT->rchild);   
  32.  }   
  33. }   
  34. void PreOrder(BTree BT)   
  35. {   
  36.  if(BT == NULL)    
  37.  {   
  38.    cout<<"NULL";   
  39.       return;   
  40.  }   
  41.  else  
  42.  {   
  43.   
  44.  cout<<BT->data;   
  45.  if (BT->lchild != NULL)   
  46.   PreOrder(BT->lchild);   
  47.  if (BT->rchild != NULL)   
  48.   PreOrder(BT->rchild);   
  49.  }   
  50. }   
  51.   
  52. void InOrder(BTree BT)   
  53. {   
  54.  if(BT == NULL)    
  55.  {   
  56.    cout<<"NULL";   
  57.       return;   
  58.  }   
  59.   
  60.  if (BT->lchild != NULL)   
  61.   InOrder(BT->lchild);   
  62.   
  63.  cout<<BT->data;   
  64.   
  65.  if (BT->rchild != NULL)   
  66.   InOrder(BT->rchild);   
  67.     
  68. }   
  69.   
  70. void PostOrder(BTree BT)   
  71. {   
  72.  if(BT == NULL)    
  73.  {   
  74.    cout<<"NULL";   
  75.       return;   
  76.  }   
  77.   
  78.  if (BT->lchild != NULL)   
  79.   PostOrder(BT->lchild);   
  80.   
  81.  if (BT->rchild != NULL)   
  82.   PostOrder(BT->rchild);   
  83.   
  84.  cout<<BT->data;   
  85.     
  86. }   
  87.   
  88. void LevelOrder(BTree BT)   
  89. {   
  90.  BTree Queue[30];   
  91.  int front, rear;   
  92.  if (BT == NULL) return;   
  93.   
  94.  front = -1;   
  95.  rear = 0;   
  96.   
  97.  Queue[rear] = BT;   
  98.   
  99.  while (front != rear)   
  100.  {   
  101.   front++;   
  102.   cout<<Queue[front]->data;   
  103.   if (Queue[front] -> lchild != NULL)   
  104.   {   
  105.    rear ++;   
  106.    Queue[rear] = Queue[front] -> lchild;   
  107.   }   
  108.   
  109.   if (Queue[front] -> rchild != NULL)   
  110.   {   
  111.    rear ++;   
  112.    Queue[rear] = Queue[front] -> rchild;   
  113.   }   
  114.  }   
  115. }   
  116.   
  117. void PreOrder_2(BTree BT)   
  118. {   
  119.  BTree stack[30], p;   
  120.  int top;   
  121.  if (BT == NULL) return;   
  122.  top = -1;   
  123.  p = BT;   
  124.  while (!(p == NULL && top == -1))   
  125.  {   
  126.   while (p!=NULL)   
  127.   {   
  128.    cout<<p->data;   
  129.    if (top < 30)   
  130.    {   
  131.     stack[top + 1] = p;   
  132.     top ++;   
  133.    }   
  134.    else  
  135.    {   
  136.     cout<<"Stack is full!"<<endl;   
  137.     return;   
  138.    }   
  139.    p = p->lchild;   
  140.   }   
  141.      
  142.   if (top < 0) return ;   
  143.   else  
  144.   {   
  145.    top--;   
  146.    p = stack[top + 1];   
  147.    p = p-> rchild;   
  148.   }   
  149.  }   
  150. }   
  151.   
  152. void PostOrder_2(BTree BT)   
  153. {   
  154.  Stack s[30];   
  155.  BTree p;   
  156.  int top, sign;   
  157.  if (BT == NULL) return;   
  158.  top = -1;   
  159.  p = BT;   
  160.  while (!(p == NULL && top == -1))   
  161.  {   
  162.   if ( p!= NULL)   
  163.   {   
  164.    s[++top].link = p;   
  165.    s[top].flag = 1;   
  166.    p = p->lchild;   
  167.   }   
  168.   else  
  169.   {   
  170.    p = s[top].link;   
  171.    sign = s[top].flag;   
  172.    top--;   
  173.    if(sign == 1)   
  174.    {   
  175.     s[++top].link = p;   
  176.     s[top].flag = 2;   
  177.     p = p->rchild;   
  178.    }   
  179.    else  
  180.    {   
  181.     cout<<p->data;   
  182.     p = NULL;   
  183.    }   
  184.   }   
  185.  }   
  186. }   
  187.   
  188. void main()   
  189. {   
  190.  BTree T;   
  191.  InitBTree(T);   
  192.  cout<<"InitTree completed!"<<endl;   
  193.  cout<<"Create Tree:"<<endl;   
  194.  CreatBTree(T);   
  195.  cout<<"/nPreOrder:"<<endl;   
  196.  PreOrder(T);   
  197.  cout<< "/nInOrder:"<<endl;   
  198.  InOrder(T);   
  199.  cout<< "/nPosetOrder:"<<endl;   
  200.  PostOrder(T);   
  201.  cout<< "/nLevelOrder:"<<endl;   
  202.  LevelOrder(T);   
  203.  cout<< "/nPreOrder_2:"<<endl;   
  204.  PreOrder_2(T);   
  205.  cout<< "/nPostOrder_2:"<<endl;   
  206.  PostOrder_2(T);   
  207.  system("pause");   
  208. }   
  209.   

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞