Danh sách khoá học Đăng ký Đăng nhập

Thông tin

Tác giả Jérôme Mayolet Anthony Doeraene
Hạn chót Không có hạn chót
Giới hạn nộp bài Không có giới hạn

Tags

Đăng nhập

Đăng nhập

Binary Search Tree

Using the structure node described as below :

struct node {
    struct node *left, *right;
    int value;
};

Here's an exemple of a tree generated by this structure:

https://inginious.org/admin/uclouvain-lepl1503/edit/task/Binary_search_tree/files?action=download&path=/student/arbre.JPG

You have to create a tree by calling the function add repetitively. The function search must check efficiently if the tree contains a certain value.

We will use a binary ordered tree, with all nodes at right having their value greater the the value of root node, and the nodes at left will have their value less than the one of root node. If a value is already contained in the tree, you shouldn't add any new node.

Example of the behaviour when calling add:

https://inginious.org/admin/uclouvain-lepl1503/edit/task/Binary_search_tree/files?action=download&path=/student/sequence%20ajout.JPG
Câu hỏi 1: Search

Write the function to search efficiently a value in a tree

/**
* This function check if "value" is contained in the tree
* @param root  : the root node of the tree (perhaps NULL)
* @param value : the value to search in the tree
* @return 1 if "value" is in the tree , 0 otherwise
*/
int search(struct node *root, int value);
Câu hỏi 2: Add

Write the function to insert correctly a value to the tree

/**
* This function add a node with a value of "value" in the tree.
* If this value is already contained in the tree, nothing is done.
*
* @param root the root of the tree (perhaps NULL)
* @param value the value to insert in the tree
* @return root of the tree
*         NULL if malloc fails
*/
struct node *add(struct node *root, int value);