[Tree] Some operations on a binary search tree

February 22, 2019 nguyenvanquan7826 TT Tree 51 responses

[qads]
Binary search tree (CNPTK) is a binary tree in which each node, key lock button is greater consideration of all the nodes of the tree and left the smaller keys of all the nodes of the tree must.
Here is an example of a binary search tree:

Content
Tree structure
Add elements to the tree
Enter tree
Browse Tree
Find a node in the tree
Deleting a node in the tree
Code Complete Reference

binary search tree
Thanks key constraints on CNPTK, finding becomes oriented. Further, by the search tree structure becomes significantly faster. If N is the number of nodes in the tree, the average search cost about log2N.

Tree structure:

typedef int item; //kieu item la kieu nguyen
struct Node
{
     item key; //truong key cua du lieu
     Node *Left, *Right; //con trai va con phai
};
typedef Node *Tree;  //cay

So we have a tree structure Tree. Now we will take a number of actions.

More 1 element in the tree

Adding an element X in the tree must satisfy the constraint of CNPTK. You can add many different places on the tree, but if you add a leaf node will be the most convenient because we can perform the same search operation. Upon termination of the search process is also time to find room for more.

int insertNode(Tree &T, item x)	// chen 1 Node vao cay
{
	if (T != NULL)
	{
		if (T->key == x) return -1; 	// Node nay da co
		if (T->key > x) return insertNode(T->Left, x);	// chen vao Node trai
		else if (T->key < x) return insertNode(T->Right, x);	// chen vao Node phai
	}
	T = (Node *) malloc(sizeof(Node));
	if (T == NULL) return 0;	// khong du bo nho
	T->key = x;
	T->Left = T->Right = NULL;
	return 1;	// ok
}

That's it bee.

Enter tree

The tree is entering the repeated insertion 1 element into the tree to a certain condition, then stop. In the code below the stop condition input element = 0.

void CreateTree(Tree &T)		// nhap cay
{
	int x;
	while (1)
	{
		printf("Nhap vao Node: ");
		scanf("%d", &x);
		if (x == 0) break; 	// x = 0 thi thoat
		int check = insertNode(T, x);
		if (check == -1) printf("Node da ton tai!");
		else if (check == 0) printf("Khong du bo nho");

	}
}

The import has finished, Although many people like that, but the code does not know what type of tree entry :3 (I have been so)

Browse Tree

Manipulation browse tree on binary search tree is exactly like the binary tree. Especially when browsing the order between, browse button sequence will give a series of buttons in ascending order of the key. (1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 20, 23)

void LNR(Tree T)
{
     if(T!=NULL)
     {
	  LNR(T->Left);
	  printf("%d   ",T->key);
	  LNR(T->Right);
     }
}

The browser in order before or after you do the same.

Find a Node key = x in the tree

Node* searchKey(Tree T, item x)		// tim nut co key x
{
	if (T!=NULL)
	{
		if (T->key == x) { Node *P = T; return P;}
		if (T->key > x) return searchKey(T->Left, x);
		if (T->key < x) return searchKey(T->Right, x);
	}
	return NULL;
}

Finding himself mentioned above is very simple and quick significantly.

Delete Node key = x in the tree

Disposing of an element X from the tree to ensure the constraint of CNPTK. Have 3 the case of a termination node X may occur:
– X is a leaf node: Simply cancel the X because it is not hooked up to any other element.

delete button on a binary search tree

– X only 1 with (left or right): Before canceling X X we hook father to his only child.
– X for all 2 with: It can not be canceled directly by X have enough 2 with. I will destroy indirect. Instead of canceling X, we will find a network element that Q. This element has a maximum. Information stored in Q will be transferred to the store at X. Later, button will be canceled Q really like 2 the first case. The problem is to choose Q such that when the flow Q in place of X, plant remains CNPTK.
Have 2 element satisfactory:
+ The smallest element (leftmost) on seedlings to.
+ The largest element (rightmost) on the left tree.
The selection element is the network element that is completely dependent on the whim of programming. In this code I select element to most.

Node delete binary tree search

int delKey(Tree &T, item x)     // xoa nut co key x
{
    if (T==NULL) return 0;
    else if (T->key > x) return delKey(T->Left, x);
    else if (T->key < x) return delKey(T->Right, x);
    else // T->key == x
    {
        if (T->Left == NULL) T = T->Right;    // Node chi co cay con phai
        else if (T->Right == NULL) T = T->Left;   // Node chi co cay con trai
        else // Node co ca 2 con
        {
            Node *Q = T->Left;
            while (Q->Right != NULL)
            {
                Q = Q->Right;
            }
            T->key = Q->key;
            delKey(T->Left, Q->key);
        }
    }
    return 1;
}

So has finished deleting a node.

Reference Code:

#include<stdlib.h>
#include<stdio.h>
 
typedef int item; //kieu item la kieu nguyen
struct Node
{
     item key; //truong key cua du lieu
     Node *Left, *Right; //con trai va con phai
};
typedef Node *Tree;  //cay
 
int insertNode(Tree &T, item x) // chen 1 Node vao cay
{
    if (T != NULL)
    {
        if (T->key == x) return -1;  // Node nay da co
        if (T->key > x) return insertNode(T->Left, x); // chen vao Node trai
        else if (T->key < x) return insertNode(T->Right, x);   // chen vao Node phai
    }
    T = (Node *) malloc(sizeof(Node));
    if (T == NULL) return 0;    // khong du bo nho
    T->key = x;
    T->Left = T->Right = NULL;
    return 1;   // ok
}
 
void CreateTree(Tree &T)        // nhap cay
{
    int x;
    while (1)
    {
        printf("Nhap vao Node: ");
        scanf("%d", &x);
        if (x == 0) break;  // x = 0 thi thoat
        int check = insertNode(T, x);
        if (check == -1) printf("Node da ton tai!");
        else if (check == 0) printf("Khong du bo nho");
 
    }
}
 
// Duyet theo LNR
void LNR(Tree T)
{
     if(T!=NULL)
     {
      LNR(T->Left);
      printf("%d   ",T->key);
      LNR(T->Right);
     }
}
 
Node* searchKey(Tree T, item x)     // tim nut co key x
{
    if (T!=NULL)
    {
        if (T->key == x) { Node *P = T; return P;}
        if (T->key > x) return searchKey(T->Left, x);
        if (T->key < x) return searchKey(T->Right, x);
    }
    return NULL;
}
 
int delKey(Tree &T, item x)     // xoa nut co key x
{
    if (T==NULL) return 0;
    else if (T->key > x) return delKey(T->Left, x);
    else if (T->key < x) return delKey(T->Right, x);
    else // T->key == x
    {
        if (T->Left == NULL) T = T->Right;    // Node chi co cay con phai
        else if (T->Right == NULL) T = T->Left;   // Node chi co cay con trai
        else // Node co ca 2 con
        {
            Node *Q = T->Left;
            while (Q->Right != NULL)
            {
                Q = Q->Right;
            }
            T->key = Q->key;
            delKey(T->Left, Q->key);
        }
    }
    return 1;
}
 
int main()
{
    Tree T;
    T=NULL; //Tao cay rong
 
    CreateTree(T); //Nhap cay
    //duyet cay
    printf("Duyet cay theo LNR: \n");
    LNR(T);
    printf("\n");
 
    Node *P;
    item x;
    printf("Nhap vao key can tim: ");
    scanf("%d", &x);
    P = searchKey(T, x);
    if (P != NULL) printf("Tim thay key %d\n", P->key);
    else printf("Key %d khong co trong cay\n", x);
 
    if (delKey(T, x)) printf("Xoa thanh cong\n");
    else printf("Khong tim thay key %d can xoan", x);
    printf("Duyet cay theo LNR: \n");
    LNR(T);
    printf("\n");
    return 0;
}

Read more: Jump binary tree into a binary search tree