输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。#include <iostream> #include <stack> using namespace std; struct node { node* lchild; node* rchild; int data; node(int v) { lchild = rchild =NULL; data = v; } }; node* BuiltBiSearchTree(int arr[],int len) { //建二叉查找树 node* root = new node(arr[0]); for(int i=1;i<len; i++) { node* p = root; while(p) { if(arr[i] < p->data) { if(p->lchild==NULL) { p->lchild = new node(arr[i]); break; } p = p->lchild ; } else { if(p->rchild==NULL) { p->rchild = new node(arr[i]); break; } p=p->rchild; } } } return root; } int midTrave(node* root) { if(root) { midTrave(root->lchild); cout<<root->data<<" "; midTrave(root->rchild); } return 0; } node* BiSearchTreeToLinkList(node* root) { stack <node* > s; node* p = root; node* pre = NULL; //中序非递归遍历 while( p || !s.empty()) { if(p) { s.push(p); p=p->lchild; } else { p = s.top();s.pop(); if(pre != NULL)//前一个不空 { p->lchild = pre; pre->rchild = p; pre = p; } else //前一个为空 { p->lchild = pre; pre = p; } //cout<<p->data<<" "; p = p->rchild ; } } pre->rchild = NULL; return pre; } int main() { int arr[] ={10,7,12,6,8,11,15}; int len = sizeof(arr)/sizeof(arr[0]); node* root = BuiltBiSearchTree(arr,len); cout<<"中序遍历:"; midTrave(root); cout<<endl; node* pEnd = BiSearchTreeToLinkList( root); node* p = pEnd; node* pre =NULL; cout<<"从右到左遍历:"; while(p) { cout<<p->data<<" "; pre = p; p = p->lchild; } cout<<endl<<"从左到右遍历:"; p = pre ; while(p) { cout<<p->data<<" "; p = p->rchild; } cout<<endl; system("pause"); return 0; }
