当前位置:编程学习 > C/C++ >>

把二元查找树转变成排序的双向链表

[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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,