10063. Tree Поиск

Задано бинарное дерево поиска. Найдите элемент в дереве.

Определение дерева:

//Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

left = null;

right = null;

}

}

// C++

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

Реализуйте функцию Find которая возвращает указатель на найденный элемент. Если требуемый элемент не найден, верните NULL.

// Java

TreeNode Find(TreeNode tree, int element)

// C++

TreeNode* Find(TreeNode *tree, int element)

Пример

Функция Find с element = 9 возвращает указатель на вершину со значением 9.

РЕШЕНИЕ

дерево

Анализ алгоритма

Если tree = NULL, то возвращаем NULL.

Начиная с корня, сравниваем число element со значением в текущей вершине. Если они равны, то поиск завершен. Если element < tree → val, то поиск продолжаем в левом поддереве, в противном случае – в правом. Длина поиска не больше высоты дерева.

Реализация алгоритма

TreeNode* Find(TreeNode* tree, int element)

{

Если tree = NULL, то возвращаем NULL.

if (tree == NULL) return NULL;

Если element совпадает со значением в текущей вершине, то возвращаем указатель на текущую вершину.

if (element == tree->val) return tree;

Если element < tree → val, то поиск продолжаем в левом поддереве, в противном случае – в правом.

if (element < tree->val) return Find(tree->left, element);

else return Find(tree->right, element);

}

Java реализация

TreeNode Find(TreeNode tree, int element)

{

if (tree == null) return null;

if (element == tree.val) return tree;

if (element < tree.val) return Find(tree.left, element);

else return Find(tree.right, element);

}