程序员面试100题_01 把二元查找树转变成排序的双向链表

题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。

    10

   / \

 6  14

 / \    / \

4 8 12 16

 转换成双向链表

4=6=8=10=12=14=16

 

 首先我们定义的二元查找树 节点的数据结构如下:

struct BTNode{
    int value;
    BTNode *left;
    BTNode *right;
};

typedef BTNode BTree;

  1 #include <iostream>
  2 #include <cassert>
  3 #include <stack>
  4 using namespace std;
  5 
  6 struct BTNode{
  7     int value;
  8     BTNode *left;
  9     BTNode *right;
 10 };
 11 typedef BTNode BTree;
 12 
 13 void DestoryLink(BTree *T){
 14     BTree *tmp;
 15     while(T){
 16         tmp=T;
 17         T=T->right; 
 18         delete tmp;
 19     }
 20 }
 21 void PrintTree(BTree *T){
 22     if(!T)return;
 23     PrintTree(T->left);
 24     cout<<T->value<<"  ";
 25     PrintTree(T->right);
 26 }        
 27 
 28 
 29 
 30 void Insert(BTree *T,BTNode *node){
 31     if(!T)return;
 32     BTNode *tmp=T,*pre;
 33     while(tmp){
 34         if(tmp->value > node->value){
 35             pre=tmp;
 36             tmp=tmp->left;
 37         }else if(tmp->value < node->value){
 38             pre=tmp;
 39             tmp=tmp->right;
 40         }else{
 41             cout<<"must be unique key"<<endl;
 42             return ;
 43         }
 44     }
 45     if(pre->value > node->value){
 46         pre->left=node;
 47     }else{
 48         pre->right=node;
 49     }
 50 }
 51 
 52 int BuildBTree(BTree *&T,int array[],int num){
 53     assert(num>0);
 54     
 55     T=new BTNode;
 56     T->left=T->right=NULL;
 57     T->value=array[0];
 58     
 59     BTNode *tmp=NULL;
 60     
 61     for(int i=1;i<num;i++){
 62         tmp=new BTNode;
 63         tmp->left=tmp->right=NULL;
 64         tmp->value=array[i];
 65         Insert(T,tmp);
 66         //cout<<array[i]<<" * ";
 67     }
 68     cout<<endl;
 69     //PrintTree(T);
 70     return 1;
 71 }
 72 
 73 int BTreeToDoubleLinkList(BTree *&T,BTNode *&Head){
 74     if(!T)return 0;
 75     
 76     
 77     BTNode *pre,*next,*tmp,*connect;
 78     pre=next=NULL;
 79     Head=NULL;
 80     //return 1;
 81     stack<BTNode*> st;
 82     st.push(T);
 83     tmp=T;
 84     int i=0;
 86     while(!st.empty()){
 87         
 88         tmp=st.top();
 89         while(tmp->left){//一直向左边查找; 
 90             st.push(tmp->left);
 91             
 92             tmp=tmp->left;
 93         }
 94         
 95         if(NULL == Head)Head=tmp;//记录头结点; 
 96         tmp=st.top();
 97         st.pop();
 98         
 99         if(NULL == pre){//记录前驱; 
100             pre=tmp;
101         }else
102             //进行链接; 
103             pre->right=tmp;
104             tmp->left=pre;
105             pre=tmp;
106             
107         }
108         
109         if(tmp->right){
110             tmp=tmp->right;
111             st.push(tmp);
112         }else{
113             //当前元素出栈; 
114             tmp=st.top();
115             st.pop();
116             while(!tmp->right){
117                 //右节点为空,进行链接; 
118                 pre->right=tmp;
119                tmp->left=pre;// 
120                pre=tmp;
121                
122                if(st.empty())break;
123                tmp=st.top();
124                st.pop();
125                
126             }
127             
128             if(tmp->right){
129                 //右节点不为空,进行链接,入栈; 
130                 pre->right=tmp;
131                 tmp->left=pre;
132                pre=tmp;
133                st.push(tmp->right);
134             }
135                
136             
137             //tmp=tmp->right;
138         }
139     }
140 }    
141 
142 
143 int main(){
144     
145     //int array[]={10,6,11,4,9,13,8,12,16,7,15,14};
146     int array[]={14,13,15,7,16,10,20,9,12,19,18} ;
147     int num=sizeof(array)/sizeof(int);
148     
149     BTree *T=NULL;
150     BTNode *Head=NULL;
151     BuildBTree(T,array,num);
152     
153     BTreeToDoubleLinkList(T,Head);
154     
155     BTNode *tmp=Head,*pre;
156     
157     cout<<" \n in main  print list"<<endl;
158     
159     while(tmp){
160         cout<<tmp->value<<" ";
161         pre=tmp;
162         tmp=tmp->right;
163     }
164     cout<<" \nfrom tail to head"<<endl;
165     while(pre){
166         cout<<pre->value<<" ";
167         pre=pre->left;
168     }
169     
170     cout<<endl;
171     DestoryLink(Head);
172     
173     system("pause");
174     return 0;
175 }
176 
177         
178     
179         
180 
181         
182         
183     
184         
185     
186             
187             
188             
189 




 


posted on 2011-05-31 17:12 bluedream 阅读(349) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔档案(6)

搜索

最新评论

阅读排行榜

评论排行榜