时间戳

首页 > 解决方案 > 用于在二叉树中搜索重复值的布尔检查

c++ - 用于在二叉树中搜索重复值的布尔检查

问题描述

我的 isdup 函数将根作为主函数的树，并搜索树中是否存在重复值。到目前为止，如果 root 和任何其他地方有任何重复值，它都会返回 true 值。但是，如果树在 root->left 和 root->left-left 中有重复值，则该函数返回 false，我不知道为什么递归函数中的逻辑是错误的。

#include "pch.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>

using namespace std;

class node {
public:
    int data;
    node* left;
    node* right;
    node* parent;
    node(int newdata):data(newdata){
        left = nullptr; right = nullptr; parent = nullptr;
    }
};

bool searchit(node*root, int value) {
    if (root == nullptr)
        return false;
    if (value == root->data) return true;
    bool left = searchit(root->left, value);
    if (left) return true;
    bool right= searchit(root->right, value);
    return right;

}

bool isdup(node* root) {
    if (root != nullptr) {
        if (searchit(root->left, root->data))return true;
        if (searchit(root->right, root->data))return true;
        return isdup(root->left) || isdup(root->right);
    }
    else return false;
}


void print(node *root) {
    if(root!=nullptr){
    print(root->left);
    cout << root->data;
    print(root->right);
    }
}


int main() {
    node* root = new node(1);
    root->left = new node(2);
    root->right = new node(4);
    root->left->left = new node(4);
    print(root);
    cout << endl;
    if (isdup(root))cout << "Yes, there is duplicated value in the tree" << endl;
    else cout << "no, there is no duplicated value in the tree" << endl;
}

标签： c++

解决方案

在 isdup 中，前 2 个 searchit 将不会返回任何内容（第一次），因为它会查找根数据……然后左右充当根，并且在左侧（作为）根下方不会找到重复项，原样右（as）根下方的情况。左右根真的不相关

推荐阅读