把二元查找树转变成排序的双向链表
[cpp]<span style="color: rgb(51, 51, 51); font-family: Arial; font-size: 14px; line-height: 26px; "><strong>把二元查找树转变成排序的双向链表
</strong>题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
10
/ /
6 14
/ / / /
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。</span>
[cpp]
#include <iostream>
using namespace std;
class Node{
public:
int data;
Node *left;
Node *right;
Node(int d = 0, Node *lr = 0, Node *rr = 0):data(d), left(lr), right(rr){}
};
Node *create()
{
Node *root;
Node *p4 = new Node(4);
Node *p8 = new Node(8);
Node *p6 = new Node(6, p4, p8);
Node *p12 = new Node(12);
Node *p16 = new Node(16);
Node *p14 = new Node(14, p12, p16);
Node *p11 = new Node(11);
Node *p13 = new Node(13);
p12->left = p11;
p12->right = p13;
Node *p15 = new Node(15);
Node *p19 = new Node(19);
Node *p18 = new Node(18);
Node *p20 = new Node(20);
p16->left = p15;
p16->right = p19;
p19->left = p18;
p19->right = p20;
Node *p10 = new Node(10, p6, p14);
root = p10;
return root;
}
void BTreeToLink(Node* &node,int curIndex)
{
Node* ptr;
if (node->left)
{
BTreeToLink(node->left,curIndex+1);
node->left->right = node;
}
if (node->right)
{
BTreeToLink(node->right,curIndex+1);
ptr = node->right;
while(ptr->left) //移向值最小的节点
ptr = ptr->left;
ptr->left = node; //将节点连接起来
node->right = ptr;
while(node->right) //指向最大的节点
node = node->right;
}
}
int main(int argc, char* argv[])
{
Node *root = create();
Node *ptr = NULL;
BTreeToLink(root,0);
ptr = root;
while (ptr->left!=NULL)
{
ptr = ptr->left;
}
while(ptr)
{
cout<<ptr->data<<endl;
ptr = ptr->right;
}
return 0;
}
补充:软件开发 , C++ ,