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

  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     else134     {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 }