时间戳

首页 > 解决方案 > 查找二叉搜索树是否有重复值

c++ - 查找二叉搜索树是否有重复值

问题描述

对于二叉搜索树，查看树是否具有重复值。我采用了这种邮购方式。

我的目标是保留当前节点的值，然后使用其他函数遍历树以查看是否有与该当前值匹配的值，如果找到任何重复值，它会带来“真实值”。我选择使用递归，因为它似乎更容易跟踪。但是当我运行程序时没有输出。

#include "pch.h"
#include <iostream>

using namespace std;

class BSTNode {
public:
int data;
BSTNode* left;
BSTNode* right;

BSTNode() {};


};

BSTNode* newnode(int newdata) { BSTNode *curr = new BSTNode; curr->data = newdata; curr->left = curr->right = nullptr; return curr; }
void print(BSTNode* root) {
    if (root != nullptr) {
        print(root->left);
        cout << root->data << endl;
        print(root->right);
    }
}


bool checking(BSTNode* parent, int val) {
    if (val == parent->data){
        bool left = checking(parent->left, val);
        bool right = checking(parent->right, val);
        return left||right;
    }
    else
        return false;
}


bool assist(BSTNode* parent) {
    if (parent != nullptr) {
        assist(parent->left);
        assist(parent->right);
        return checking(parent, parent->data);
    }
    else return false;
}


int main() {

    BSTNode *test = newnode(1);
    test->left=newnode(2);
    test->right=newnode(3);
    test->left->left=newnode(2);
    test->right->right=newnode(5);

    print(test);


    if (assist(test))
        cout << "There is duplicated" << endl;
    else
        cout << "There is no duplicated" << endl;

    return 0;

}

标签： c++

解决方案

您的检查功能应如下所示：

bool checking(BSTNode* parent, int val) {
    if(parent == nullptr)   // point 1
        return false;
    if (val == parent->data){   // point 2
        return true;
    }
    else{
        bool left = checking(parent->left, val);
        bool right = checking(parent->right, val);
        return left||right;
    }
}

您的辅助功能应如下所示：

bool assist(BSTNode* parent) {
    if (parent != nullptr) {   
        if(checking(parent->left, parent->data)) return true;  // point 3
        if(checking(parent->right, parent->data)) return true;
         return assist(parent->left)||assist(parent->right);   // point 4
    }
    else return false;
}

  1. 您需要检查空值。

  2. 如果val相同，为什么还要检查？停下来

  3. 您需要检查左右子树中节点的值。

  4. 为子节点递归它

推荐阅读