首页 > 代码库 > 二元查找树转换成一个排序的双向链表

二元查找树转换成一个排序的双向链表

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

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

 

#ifndef UTILS_HEADER
#define UTILS_HEADER
#include "utils.h"
#endif
#include "MS.h"


struct treenode* MS01Util(struct treenode* root, int flag){

    if (root == NULL){
        return NULL;
    }
    struct treenode* left = MS01Util(root->lchild, 0);
    struct treenode* right = MS01Util(root->rchild, 1);
    if (left != NULL){
        left->rchild = root;
        root->lchild = left;
    }
    if (right != NULL){
        right->lchild = root;
        root->rchild = right;
    }
    struct treenode* result = root;
    if (flag == 0){
        while (root != NULL){
            result = root;
            root = root->rchild;
        }
    }
    else{
        while (root != NULL){
            result = root;
            root = root->lchild;
        }
    }
    return result;
}
void MS01(){

    double array[] = { 23154263512463214 };
    struct treenode* root = gene2OrTree(array, 17);
    cout << endl;
    root = MS01Util(root, 1);
    while (root != NULL){
        cout << root->value << " ";
        root = root->rchild;
    }
    cout << endl;


    return;

}