c++ - C++遍历中的树排序

Question

我正在研究一个问题，给定一个数组，使用基于链表的树排序对其进行排序，然后遍历树以重新生成(现已排序的)数组，而不使用 vector 。这是我的代码:

using namespace std;
#include <iostream>

// sorts b[0..n-1] into non-descending (i.e. ascending) order.

struct tNode { int val; tNode * leftC; tNode * rightC; };

void insert(tNode * &here, int val) {
    //base case
    if (here == NULL) {
        here = new tNode();
        here->val = val;
        here->leftC = here->rightC = NULL;
        return;
    }
    else if (val <= here->val) {
        insert(here->leftC, val);
    }
    else {
        insert(here->rightC,val);
    }
}

int traverse(tNode * node) {
    if (node == NULL) return -1;
    if (!node->leftC == NULL)traverse(node->leftC);
    int r = node->val;
    if (!node->rightC == NULL)traverse(node->rightC);
    else {
        node = NULL;
        return r;
    }

}

void sortWithTree(int b[], int n) {
    tNode * root = NULL;
    tNode * p = root;
    for (int i = 0; i < n; i++) {
        insert(p, b[i]);
    }
    for (int i = 0; i < n; i++) {
        b[i] = traverse(root);
    }
}

Traverse 每次都返回 -1。我做错了什么？

Answer 1

你的问题出在遍历上。

我猜你的意图是让遍历调用返回树中包含的最小数字并将该值从树中删除。
以便连续调用按递增顺序返回成员。
但这很难用你的结构来做，因为节点包含中间值。返回一个值后，您需要将其删除，但不要删除正确的节点。
另一个问题是参数节点不是通过引用传递的(准确地说是通过引用指针)，因此指令 node = NULL; 在树中没有效果。

我不会修复您的遍历，而是采用更简单的策略。在一次遍历中填充数组。 traverse 不会返回任何元素，相反它会收到一个指向数组的指针并将元素存储在那里，并随着指针的增加而增加。

void traverse(tNode * node, int*& p) {
    if (node == NULL) return;
    traverse(node->leftC, p);
    *p = node->val;
    ++p;
    traverse(node->rightC, p);
}

void sortWithTree(int b[], int n) {
    tNode * root = NULL;
    tNode * p = root;
    for (int i = 0; i < n; i++) {
        insert(p, b[i]);
    }
    int *bTmp = b;
    traverse(root, bTmp);
}

你的代码和我的代码都还有事情要做。完成树后，删除所有动态内存。如果您了解我的遍历是如何工作的，您应该能够自己完成。