두 갈래 나무의 기본 반복 작업

  1 #include <queue>
  2 #include <iostream>
  3 using namespace std;
  4 
  5 #define QSIZE 100
  6 struct BTree
  7 
  8 {
  9     int value;
 10     struct BTree* lChild;
 11     struct BTree* rChild;
 12 };
 13 
 14 void VisitNode(BTree * T)
 15 {
 16     cout<<T->value<<" ";
 17 }
 18 BTree * Insert(BTree* T, int value) //T is the root of binary tree
 19 {
 20     if(T == NULL)
 21     {
 22         T = new BTree;
 23         if( T == NULL)
 24             cout<<"Malloc Failed."<<endl;
 25         else
 26         {
 27             T->value  = value;
 28             T->lChild = T->rChild = NULL;
 29         }
 30     }
 31     else if(value < T->value)
 32         T->lChild = Insert(T->lChild,value);  
 33     else if(value > T->value)
 34         T->rChild = Insert(T->rChild, value);
 35     return T;
 36 }
 37 
 38 BTree* MakeEmpty(BTree* T) 
 39 {
 40     if(T != NULL)
 41     {
 42         MakeEmpty(T->lChild);
 43         MakeEmpty(T->rChild);
 44         delete T;
 45     }
 46     return NULL;
 47 }
 48 
 49 void LevelTraversal(BTree * T)
 50 {
 51     if(T == NULL)
 52         return;
 53     queue<BTree> Queue;
 54     Queue.push(*T);
 55     while(!Queue.empty())
 56     {
 57         VisitNode(&Queue.front());
 58         if(Queue.front().lChild != NULL)
 59             Queue.push(*Queue.front().lChild);
 60         if(Queue.front().rChild != NULL)
 61             Queue.push(*Queue.front().rChild);
 62         Queue.pop();
 63     }
 64 }
 65 
 66 void PreOrder(BTree * T)
 67 {
 68     if(T == NULL)
 69         return;
 70     VisitNode(T);
 71     PreOrder(T->lChild);
 72     PreOrder(T->rChild);
 73 }
 74 
 75 void InOrder(BTree * T)
 76 {
 77     if(T == NULL)
 78         return;
 79     InOrder(T->lChild);
 80     VisitNode(T);
 81     InOrder(T->rChild);
 82 }
 83 
 84 void PosOrder(BTree * T)
 85 {
 86     if(T == NULL)
 87         return;
 88     PosOrder(T->lChild);
 89     PosOrder(T->rChild);
 90     VisitNode(T);
 91 }
 92 
 93 int HeightofBTree(BTree * T)
 94 {
 95     if(T == NULL)
 96         return 0;
 97 
 98     int hLeft = HeightofBTree(T->lChild);
 99     int hRight = HeightofBTree(T->rChild);
100     return (hLeft > hRight ? hLeft : hRight) + 1;
101 }
102 
103 int main()
104 {
105     BTree* T = NULL;
106     T = Insert(T,45);
107     T = Insert(T,21);
108     T = Insert(T,65);
109     T = Insert(T,10);
110     T = Insert(T,50);
111     T = Insert(T,70);
112     T = Insert(T,24);
113 
114     cout<<"Level Traversal:";
115     LevelTraversal(T);
116     cout<<endl;
117 
118     cout<<"Preorder Traversal:";
119     PreOrder(T);
120     cout<<endl;
121 
122     cout<<"Inorder Traversal:";
123     InOrder(T);
124     cout<<endl;
125 
126     cout<<"Posorder Traversal:";
127     PosOrder(T);
128     cout<<endl;
129 
130     cout<<"Height of BTree is "<<HeightofBTree(T);
131 
132     MakeEmpty(T);
133     cout<<endl;
134     return 0;
135 }