二叉树预序

Question

我的预排序方法在 main 中不起作用，但是数组元素已经正确形成（我通过打印每一步来检查它）。定义中使用的所有 functions/methods 均正常工作。我认为问题的发生是因为行“return elem;”。任何人都可以提出任何想法，这太重要了。

T* TreeNode<T>::preorder()const 
{
    T* elem = new T[elCount(left)+elCount(right)+1];
    elem[0] = data;
    TreeNode<T>* curr = left;
    Stack<TreeNode<T>*> st;
    if (right) {
        st.push(right);
    }
    int i = 1;
    while (curr) {
        elem[i++] = curr->getData();
        //std::cout << elem[i - 1];
        
        if (curr->getRight()) 
            st.push(curr->getRight());
        
        curr = curr->getLeft();
        if (!curr) 
        {
            curr = st.getTop();
            st.pop();
        }   }
    return elem;
}

Answer 1

由于未指定，因此很难确切地看到您正在尝试做什么，但您似乎正在尝试从二叉树中获取所有数据。 This GFG article 对如何遍历二叉树做了一个非常简单的解释和分解。显然你的节点更复杂，但大体逻辑是一样的。我会问自己 preorder() 函数是否真的需要成为树节点 class 的一部分，以及一个单独的函数是否会更有用。我还会考虑使用 std::vector 而不是您当前使用的 carray。如果您需要固定大小，std::array 可能也会更好。

要展示如何重写代码，您可以尝试类似的方法

std::vector<int> vect;

template<class T>
void preorder(const TreeNode<T>& node, vector<T>& elem) {
    if(!node.getData()) {
        return;
    }

    elem.push(node.getData());

    if(node.getLeft()) {
        preorder(node.getLeft());
    }

    if(node.getRight()) {
        preorder(node.getRight());
    }
}

这并不完美，因为我是凭空写下的，但它应该为遍历二叉树和提取所有数据提供一个简单的基础。一点递归应该会使它变得容易得多。

二叉树预序

Binary tree preorder

c++

binary-tree

return

data-structures

preorder