面试题 -二元查找树转变成排序的双向链表

  1 // Tree.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include <malloc.h>
  6 #include <iostream>
  7 using namespace std;
  8 
  9 template<class Type>
 10 struct BinaryNode
 11 {
 12 private:
 13     Type value;
 14     BinaryNode<Type> *left;
 15     BinaryNode<Type> *right;
 16 public:
 17     BinaryNode(Type val):left(NULL),right(NULL)
 18     {
 19         value = val;
 20     }
 21     BinaryNode<Type> * GetLeftBiggest();
 22     BinaryNode<Type> * GetRightSmallest();
 23     void convert();
 24     void Insert(BinaryNode<Type> *ptr);
 25     void Print();
 26     void PrintList();
 27 };
 28 
 29 template<class Type>
 30 void BinaryNode<Type>::Print()
 31 {
 32     if(this==NULL)
 33     {
 34         return;
 35     }
 36     cout<<value<<endl;    
 37     left->Print();
 38     right->Print();
 39 }
 40 
 41 template<class Type>
 42 void BinaryNode<Type>::PrintList()
 43 {
 44     BinaryNode *l = left;
 45     BinaryNode *r = right;
 46 
 47     while(l->left!=NULL)
 48     {
 49         l = l->left;
 50     }
 51     while(l->right!=NULL)
 52     {
 53         cout<<l->value<<endl;
 54         l = l->right;
 55     }
 56     while(l->left != NULL)
 57     {
 58         cout<<l->value<<endl;
 59         l=l->left;
 60     }
 61 
 62 }
 63 
 64 
 65 
 66 template<class Type>
 67 BinaryNode<Type> * BinaryNode<Type>::GetLeftBiggest()
 68 {
 69     BinaryNode<Type> *result=NULL;
 70     if(left!= NULL)
 71     {
 72         result = left;
 73         while(result->right!=NULL)
 74         {
 75             result = result->right;
 76         }
 77     }
 78     return result;
 79 
 80 }
 81 
 82 template<class Type>
 83 BinaryNode<Type> * BinaryNode<Type>::GetRightSmallest()
 84 {
 85     BinaryNode<Type> *result=NULL;
 86     if(right!= NULL)
 87     {
 88         result = right;
 89         while(result->left!=NULL)
 90         {
 91             result = result->left;
 92         }
 93     }
 94         return result;
 95 }
 96 
 97 template<class Type>
 98 void BinaryNode<Type>::convert( )
 99 {
100     if(left!=NULL)
101     {
102         BinaryNode<Type> *ptr = GetLeftBiggest();
103         left->convert();
104         ptr->right = this;
105         this->left = ptr;
106     }
107     if(right!=NULL)
108     {
109         BinaryNode<Type> * ptr = GetRightSmallest();
110         right->convert();
111         ptr->left = this;
112         this->right = ptr;
113     }
114 }
115 
116 template<class Type>
117 void BinaryNode<Type>::Insert(BinaryNode<Type> *ptr)
118 {
119     if((value>=ptr->value)&&(left == NULL))
120     {
121         left = ptr;
122         return;
123     }
124     else if((value>=ptr->value)&&(left != NULL))
125     {
126         return left->Insert(ptr);
127     }
128     else if((value<ptr->value)&&(right == NULL))
129     {
130         right = ptr;
131         return;
132     }
133     else
134     {
135         return right->Insert(ptr);
136     }
137 }
138 
139 int _tmain(int argc, _TCHAR* argv[])
140 {
141     int value;
142     cout<<"Please input the root value"<<endl;
143     cin>>value;
144     BinaryNode<int> *root=  new BinaryNode<int>(value);;
145     
146     int TreeNodeNumber;
147     cout<<"Please input the Tree Node Numbers:"<<endl;
148     cin>>TreeNodeNumber;
149     BinaryNode<int> **nodes = new BinaryNode<int> *[TreeNodeNumber];
150     for(int index=0;index<TreeNodeNumber;index++)
151     {
152         int value;
153         cout<<"Please input the "<<index+1<<" Node"<<endl;
154         cin>>value;
155         nodes[index] = new BinaryNode<int>(value);        
156         root->Insert(nodes[index]);
157     }
158 
159     root->Print();
160     root->convert();
161     root->PrintList();
162     
163     return 0;
164 }