首页 文章

打印二进制搜索树中的节点print_node（const Node * n）的值

提问于
浏览 次
-2

我理解递归的想法，而不是实现 . 我不明白你如何传入非root的节点 . 我有一个头文件和一个ccp . 节点类是BST类的私有子类 . 所以我猜它是从BST课程中调用的 . 但是如何遍历树并匹配节点？节点是否可比（节点n ==根 - >左）？比较值，（n-> value == root-> left-> value）会更好吗？如果它们相等则打印出值？既然我也无法改变节点，我该如何递归调用呢？我应该走一个包含两个节点的辅助函数的路径吗？比方说，const Node * n和Node * t

class BST {
class Node { // binary tree node
public:
    Node* left;
    Node* right;
    Value value;
    int level;
    Node(const Value v = Value(), int lev = 1)
        : value(v), level(lev), left(nil), right(nil)
    {}
    Value& content() { return value; }

}; // Node

Node* root;

public：void print_node（const Node * n）{//打印节点的值 .

}

Value print_node(const Node *n, Node *t){

}
c++ algorithm nodes binary-search-tree

2 回答

  • 0

    没有代码或更好的描述就做不了多少，所以我将解释你似乎围绕'root'与'node'的问题 .

    首先，'root'是一种节点 . 代码方面，它实际上看起来不应该与其他节点对象有任何不同，应该通过 Node* root = new Node(); 'Root'设置只是一个名称，我们给出一个没有父节点的特殊类型的节点，并且不保证全新的数据结构体 . 如果我使用带有 gender 字段的 Person 类的单独示例，则可以将 Person* person = new Person(); 对象描述为'female'只是因为字段 gender == female" ，而不必创建一个名为 Female 的全新类 .

    除此之外，由于树的递归实现通常不会查看父项，因此传递“根”应该与传递常规节点完全相同 . 如果您在粗糙伪代码中定义了以下方法：

    define BSTVisit(Node* node, Node* nodeToFind) {
    switch (compareNodes(node, nodeToFind)) {
        case MATCH:
            print(node->name);
            break;
        case LESS_THAN:
            BSTVisit(node->leftChild, nodeToFind);
            break;
        case MORE_THAN:
            BSTVisit(node->rightChild, nodeToFind);
            break;
    }
}

    您可以通过调用 BSTVisit(root, nodeToFind) 来启动代码 . 从那里它将'root'视为常规节点，根据需要访问其子节点，并继续直到它完成 .

    回复于
  • 0

    下面是树遍历可以是非递归的示例，我们从根开始并检查每个节点的键值 . 如果递归深度太大，则可能导致堆栈溢出（即使二进制树遍历不太可能），并且递归遍历比非递归遍历慢 .

    template <class T>
Node* BinTree<T>::findParent(const T& key, bool& bExist) const
{
    Node* parent = root;
    bExist = false ;
    while(root)
    {
        parent = root ;
        if ( key < root->key )
            root = root->left ;
        else if ( key > root->key )
            root = root->right ;    
        else
        {
            bExist = true ;
            return root ;
        }
    }

    return parent;
}
    回复于

相关问题