现在的位置: 首页 > 综合 > 正文

二叉查找树 转换成 排序的双向链表

2013年01月06日 ⁄ 综合 ⁄ 共 1659字 ⁄ 字号 评论关闭

http://www.cnblogs.com/XjChenny/archive/2011/10/01/2197783.html

 

自己写的代码:

#include<iostream>
#include<stack>
using namespace std;

class Tree{
public:
 Tree():element(0),left(NULL),right(NULL){}
 Tree(int num):element(num){left=right=NULL;}
 Tree* search(int num);
 Tree* insert(int num);
 Tree* getleft(){return left;}
 Tree* getright(){return right;}
 int getElement(){return element;}
 void transform(Tree* root);
 static Tree * list ;
private:
 int element;
 Tree *left;
 Tree *right;
};

Tree * Tree::list=NULL;

Tree* Tree::search(int num)
{
 if(element == num)
 {
  return this;
 }
 else if(left!=NULL)
 {
  return left->search(num);
 }
 else if(right!=NULL)
 {
  return right->search(num);
 }
 else return NULL;
}

Tree* Tree::insert(int num)
{

 if(num>element)
 {
  if(right==NULL)
   right=new Tree(num);
  else
   right->insert(num);
 }
 else if(num<element)
 {
  if(left == NULL)
   left=new Tree(num);
  else
   left->insert(num);
 }
 else if(num==element)
 {
  cout<<"This version do not support two same nodes"<<endl;
  exit(1);
 }
 return this;

}

void Tree::transform(Tree* root)
{
 if(root->left !=NULL)
 {
  transform(root->left);
 }
 
 if(list == NULL)
 { 
  list = root;
  list->left = NULL;
 }
 else
 {
  list->right = root;
  root->left = list;
  list =root;
 }

 if(root->right !=NULL)
 {
  transform(root->right);
 }
}

int main()
{
 Tree *root = new Tree(10);
 root->insert(5);
 root->insert(15);
 root->insert(3);
 root->insert(8);
 root->insert(11);
 root->insert(16);
 root->transform(root);
 
 while(Tree::list->getleft()!=NULL)
 {
  cout<<Tree::list->getElement()<<" ";
  Tree::list = Tree::list->getleft();
 }
 cout<<Tree::list->getElement()<<endl;

 while(Tree::list->getright() !=NULL)
 {
  cout<<Tree::list->getElement()<<" ";
  Tree::list = Tree::list->getright();
 }
 cout<<Tree::list->getElement()<<endl;

 return 0;
}

 

抱歉!评论已关闭.