Cây tìm kiếm nhị phân(BST) - Thêm, Xóa và Duyệt cây tìm kiếm nhị phân

This entry is part 8 of 16 in the series Cấu trúc dữ liệu

Trong bài viết này, chúng ta sẽ tiếp tục tìm hiểu về cấu trúc dữ liệu Cây, và cụ thể là cây tìm kiếm nhị phân. Đây là một cấu trúc dữ liệu được dùng khá phổ biến và có tính ứng dụng cao. Hãy cùng Nguyễn Văn Hiếu tìm hiểu và cài đặt cây tìm kiếm nhị phân sử dụng ngôn ngữ C/C++ nhé.

NỘI DUNG BÀI VIẾT

1. Lý thuyết về cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân(TA: Binary Search Tree – viết tắt: BST) – là một cây nhị phân và có thêm các ràng buộc sau đây:

Giá trị của tất cả các Node ở cây con bên trái phải <= giá trị của Node gốc.
Giá trị của tất cả các Node ở cây con bên phải phải > giá trị của Node gốc.
Tất cả các cây con(bao gồm bên trái và phải) cũng đều phải đảm bảo 2 tính chất trên.

Nhận biết cây tìm kiếm nhị phân. Hình thứ 2 không phải BST do vi phạm ràng buộc số 2

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu hiệu quả cho phép chúng ta xây dựng nên một danh sách mà dữ liệu trên đó được sắp xếp:

Nó được gọi là cây nhị phân vì mỗi Node của cây chỉ có tối đa hai con
Nó được gọi là cây tìm kiếm nhị phân vì nó có thể được sử dụng để tìm kiếm sự hiện diện của một phần tử trong thời gian O(log (n)).

2. Cài đặt cây BST

Sau đây, tôi sẽ cùng các bạn đi cài đặt cây tìm kiếm nhị phân sử dụng danh sách liên kết. Do đó, cái bạn cần lưu giữ là Node root của cây mà thôi. Có được root chúng ta có thể duyệt qua mọi phần tử của cây.

Đầu tiên, chúng ta sẽ định nghĩa kiểu dữ liệu cho các Node của cây:

typedef struct Node
{
    int data;
    Node* left;
    Node* right;
} node_t;

typedef struct Node

{

int data;

Node* left;

Node* right;

} node_t;

Tiếp theo, chúng ta sẽ triển khai code cho tức chức năng của cây BST. Chúng ta sẽ sử dụng đệ quy rất nhiều trong các chức năng này. Bạn có thể tự tìm hiểu cách viết khử đệ quy nhé.

2.1. Hàm giải phóng dữ liệu

Chúng ta sẽ sử dụng hàm này khi muốn xóa một cây con hoặc toàn bộ cây bằng cách cung cấp Node root của cây muốn xóa. Việc giải phóng được thực hiện theo trình tự:

Gọi đệ quy xóa cây con bên trái
Gọi đệ quy xóa cây con bên phải
Giải phóng vùng nhớ cho con trỏ hiện tại

void Free( node_t* root )
{
    if ( root == NULL )
        return;
    Free( root->left );
    Free( root->right );
    free( root );
}

void Free( node_t* root )

{

if ( root == NULL )

return;

Free( root->left );

Free( root->right );

free( root );

}

2.2. Hàm điều hướng của cây

2 hàm dưới đây sẽ phục vụ chúng ta trong quá trình Insert(thêm phần tử vào cây) và Tìm kiếm trên cây tìm kiếm nhị phân.

Nếu bạn cho phép cây BST có giá trị trùng lặp, hãy lưu ý hàm LeftOf nhé. Ở đây tôi sẽ không cho phép thêm phần tử đã có trên cây(bỏ qua trùng lặp giá trị).

int LeftOf( const int value, const node_t* root )
{
    // Nếu bạn muốn cây BST cho phép giá trị trùng lặp, hãy sử dụng dòng code thứ 2
    return value < root->data;
//    return value <= root->data;
}

int RightOf( const int value, const node_t* root )
{
    return value > root->data;
}

int LeftOf( const int value, const node_t* root )

{

// Nếu bạn muốn cây BST cho phép giá trị trùng lặp, hãy sử dụng dòng code thứ 2

return value < root->data;

// return value <= root->data;

}

int RightOf( const int value, const node_t* root )

{

return value > root->data;

}

2.3. Thêm phần tử vào BST

Việc thêm 1 phần tử vào cây nhị phân tìm kiếm vẫn phải đảm bảo được các ràng buộc của một BST đã trình bày ở trên. Như vậy, bạn cần phải tìm kiếm vị trí thích hợp trong BST để lưu giữ nó.

Nếu bạn để ý, bạn sẽ nhận ra vị trí của các Node được thêm vào sẽ luôn Node lá(không có Child nào hết). Như vậy, tại vị trí đó trước khi các Node mới tới ở thì nó là NULL. Ta có quy trình như sau:

Nếu Node hiện tại = NULL, đó là vị trí cần thêm. Thêm vào BST và kết thúc
Nếu giá trị cần thêm < giá trị root hiện tại, gọi đệ quy Insert vào cây con bên trái
Nếu giá trị cần thêm > giá trị root hiện tại, gọi đệ quy Insert vào cây con bên phải.

node_t* Insert( node_t* root, const int value )
{
    if ( root == NULL )
    {
        node_t* node = (node_t*)malloc( sizeof( node_t ) );
        node->left = NULL;
        node->right = NULL;
        node->data = value;
        return node;
    }
    if ( LeftOf( value, root ) )
        root->left = Insert( root->left, value );
    else if ( RightOf( value, root ) )
        root->right = Insert( root->right, value );
    return root;
}

node_t* Insert( node_t* root, const int value )

{

if ( root == NULL )

{

node_t* node = (node_t*)malloc( sizeof( node_t ) );

node->left = NULL;

node->right = NULL;

node->data = value;

return node;

}

if ( LeftOf( value, root ) )

root->left = Insert( root->left, value );

else if ( RightOf( value, root ) )

root->right = Insert( root->right, value );

return root;

}

Hãy xem hình ảnh mô phỏng việc thêm giá trị 4 vào BST dưới đây:

2.4. Tìm kiếm trên BST

Việc tìm kiếm cũng tương tự như việc thêm phần tử vào BST. Ta có quy trình như sau:

Nếu Node hiện tại có giá trị = giá trị cần tìm, trả về true và kết thúc.
Nếu Node hiện tại có giá trị > giá trị cần tìm, gọi đệ quy tìm ở cây con bên trái.
Nếu Node hiện tại có giá trị < giá trị cần tìm, gọi đệ quy tìm ở cây con bên phải
Nếu tìm đến hết cây(Node đó = NULL) mà không xảy ra (1), trả về false và kết thúc.

bool Search( const node_t* root, int value )
{
    if ( root == NULL )
        return false;
    if(root->data == value){
        return true;
    }else if ( LeftOf( value, root ) ){
        return Search( root->left, value );
    }else if( RightOf( value, root ) ){
        return Search( root->right, value );
    }
}

bool Search( const node_t* root, int value )

{

if ( root == NULL )

return false;

if(root->data == value){

return true;

}else if ( LeftOf( value, root ) ){

return Search( root->left, value );

}else if( RightOf( value, root ) ){

return Search( root->right, value );

}

Chúng ta sẽ quan sát cách BST tìm kiếm giá trị 4 trong hình ảnh dưới đây:

2.5. Lấy giá trị con trái nhất

Rất đơi giản, duyệt theo con trỏ trỏ đến cây con bên trái tới chừng nào không còn con bên trái nữa thì đó là con trái nhất rồi.

Hàm này sẽ được chúng ta sử dụng trong việc xóa một Node có giá trị chỉ định trên BST ở mục tiếp theo.

int LeftMostValue( const node_t* root )
{
    while ( root->left != NULL )
        root = root->left;
    return root->data;
}

int LeftMostValue( const node_t* root )

{

while ( root->left != NULL )

root = root->left;

return root->data;

}

Hình ảnh dưới đây mô phỏng hàm LestMostChild hoạt động:

Vậy chúng ta có cần hàm RightMostChild không? Câu trả lời là có. Tuy nhiên, bạn có thể tận dùng hàm LeftMostChild này, chẳng hạn: Số 25 là right most child của root(15) có thể tính bằng LeftMostChild(root->right->right).

2.6. Xóa Node trong BST

Việc xóa Node trong BST có lẽ là phức tạp nhất trong các chức năng của cây tìm kiếm nhị phân. Nếu Node bạn cần xóa là Node lá thì việc xóa rất đơn giản. Cái khó ở chỗ xóa một Node ở trung gian, khi đó, bạn phải tìm cách xóa và nối lại mà vẫn đảm bảo cây mới vẫn là BST. Chúng ta sẽ xem xét từng trường hợp trước khi code nhé:

1. Node cần xóa là Node lá(không có child nào cả)

Giả sử ta cần xóa 20 trong hình dưới đây, đơn giản là chỉ cần giải phóng ô nhớ đó.

              50                            50
           /     \         delete(20)      /   \
          30      70       --------->    30     70 
         /  \    /  \                     \    /  \ 
       20   40  60   80                   40  60   80

50 50

/ \ delete(20) / \

30 70 ---------> 30 70

/ \ / \ \ / \

20 40 60 80 40 60 80

2. Node cần xóa có 1 child

Trong trường hợp này, Node bị xóa sẽ được giải phóng và cây con duy nhất của Node bị xóa sẽ được liên kết trực tiếp với cha của Node bị xóa.

              50                            50
           /     \         delete(30)      /   \
          30      70       --------->    40     70 
            \    /  \                          /  \ 
            40  60   80                       60   80

50 50

/ \ delete(30) / \

30 70 ---------> 40 70

\ / \ / \

40 60 80 60 80

3. Node cần xóa có đủ 2 child

Xóa node có 2 con trong BST — Giả sử cần xóa Node khoanh đỏ. Khi đó, ta cần tìm Node thế thân cho Node đỏ này, đó là Node LeftMostChild của cây con bên phải của Node đỏ(72) = Node khoanh màu xanh(54) . Sau đó, gọi đệ quy Xóa Node màu xanh. Khi đó Node cần xóa sẽ quay trở về trường hợp 1 hoặc 2(Trong ảnh này là trường hợp 2 – có 1 child).

Đây là trường hợp nan giải nhất, nhưng chúng ta vẫn có cách làm như sau:

Tìm Node của con trái nhất(giả sử nó là leftmost) của cây con bên phải của Node cần xóa.
Cập nhật giá trị của Node cần xóa = giá trị của Node leftmost.
Gọi đệ quy hàm Delete xóa Node leftmost khỏi BST.

Giải thích:

Khi muốn xóa Node có 2 con, ta cần tìm Node nào đó trong BST thỏa mãn tính chất lớn hơn lớn hơn tất cả các con bên trái và nhỏ hơn tất cả các con bên phái -> Node đó chính là LeftMostChild của con bên phải của Node cần xóa.
Ta chỉ cần sửa giá trị của Node cần xóa, không cần xóa Node đó làm gì. Thay vào đó, xóa Node bị thế thân(LeftMostChild của con bên phải của Node cần xóa).

node_t* Delete( node_t* root, int value )
{
    if ( root == NULL )
        return root;
    if ( LeftOf( value, root ) )
        root->left = Delete( root->left, value );
    else if ( RightOf( value, root ) )
        root->right = Delete( root->right, value );
    else
    {
        // root->data == value, delete this node
        if ( root->left == NULL )
        {
            node_t* newRoot = root->right;
            free( root );
            return newRoot;
        }
        if ( root->right == NULL )
        {
            node_t* newRoot = root->left;
            free( root );
            return newRoot;
        }
        root->data = LeftMostValue( root->right );
        root->right = Delete( root->right, root->data );
    }
    return root;
}

node_t* Delete( node_t* root, int value )

{

if ( root == NULL )

return root;

if ( LeftOf( value, root ) )

root->left = Delete( root->left, value );

else if ( RightOf( value, root ) )

root->right = Delete( root->right, value );

else

{

// root->data == value, delete this node

if ( root->left == NULL )

{

node_t* newRoot = root->right;

free( root );

return newRoot;

}

if ( root->right == NULL )

{

node_t* newRoot = root->left;

free( root );

return newRoot;

}

root->data = LeftMostValue( root->right );

root->right = Delete( root->right, root->data );

}

return root;

}

3. Duyệt cây tìm kiếm nhị phân

Ở mục này mình sẽ trình bày về 3 cách duyệt cây tìm kiếm nhị phân. Chúng ta sẽ đi vào chi tiết từng cách nhé. Thứ tự duyệt được đặt tên phụ thuộc vào vị trí của Node root trong quá trình duyệt:

PreOrder: Node -> Left -> Right
InOrder: Left -> Node -> Right
PostOrder: Left -> Right -> Node
Thực ra 3 phần tử Left, Right, Node có tất cả 6 hoán vị cơ. Còn 3 cái nữa các bạn tự cài nhé.

3.1. Duyệt PreOrder

Quy trình duyệt PreOrder sẽ thực hiện theo thứ tự Node -> Left -> Right, cụ thể như sau:

Ghé thăm Node root
Gọi đệ quy duyệt qua cây con bên trái
Gọi đệ quy duyệt qua cây con bên phải

Duyệt pre_order BTS — Thứ tự duyệt pre_order trên BTS

void PreOrder(node_t* root){
    if(root != NULL)
    {
        printf("%d ", root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

void PreOrder(node_t* root){

if(root != NULL)

{

printf("%d ", root->data);

PreOrder(root->left);

PreOrder(root->right);

}

3.2. Duyệt InOrder

Quy trình duyệt PreOrder sẽ thực hiện theo thứ tự Left-> Node -> Right, cụ thể như sau:

Gọi đệ quy duyệt qua cây con bên trái
Ghé thăm Node root
Gọi đệ quy duyệt qua cây con bên phải

void InOrder(node_t* root){
    if(root != NULL)
    {
        InOrder(root->left);
        printf("%d ", root->data);
        InOrder(root->right);
    }
}

void InOrder(node_t* root){

if(root != NULL)

{

InOrder(root->left);

printf("%d ", root->data);

InOrder(root->right);

}

3.1. Duyệt PostOrder

Quy trình duyệt PreOrder sẽ thực hiện theo thứ tự Left -> Right -> Node, cụ thể như sau:

Gọi đệ quy duyệt qua cây con bên trái
Gọi đệ quy duyệt qua cây con bên phải
Ghé thăm Node root

void PostOrder(node_t* root){
    if(root != NULL)
    {
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%d ", root->data);
    }
}

void PostOrder(node_t* root){

if(root != NULL)

{

PostOrder(root->left);

PostOrder(root->right);

printf("%d ", root->data);

}

4. Code đầy đủ cây tìm kiếm nhị phân

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    Node* left;
    Node* right;
} node_t;



void Free( node_t* root )
{
    if ( root == NULL )
        return;

    Free( root->left );
    Free( root->right );
    free( root );
}

int LeftOf( const int value, const node_t* root )
{
    // Nếu bạn muốn cây BST cho phép giá trị trùng lặp, hãy sử dụng dòng code thứ 2
    return value < root->data;
//    return value <= root->data;
}

int RightOf( const int value, const node_t* root )
{
    return value > root->data;
}

node_t* Insert( node_t* root, const int value )
{
    if ( root == NULL )
    {
        node_t* node = (node_t*)malloc( sizeof( node_t ) );
        node->left = NULL;
        node->right = NULL;
        node->data = value;
        return node;
    }
    if ( LeftOf( value, root ) )
        root->left = Insert( root->left, value );
    else if ( RightOf( value, root ) )
        root->right = Insert( root->right, value );
    return root;
}

bool Search( const node_t* root, int value )
{
    if ( root == NULL )
        return false;
    if(root->data == value){
        return true;
    }else if ( LeftOf( value, root ) ){
        return Search( root->left, value );
    }else if( RightOf( value, root ) ){
        return Search( root->right, value );
    }
}

int LeftMostValue( const node_t* root )
{
    while ( root->left != NULL )
        root = root->left;
    return root->data;
}

node_t* Delete( node_t* root, int value )
{
    if ( root == NULL )
        return root;
    if ( LeftOf( value, root ) )
        root->left = Delete( root->left, value );
    else if ( RightOf( value, root ) )
        root->right = Delete( root->right, value );
    else
    {
        // root->data == value, delete this node
        if ( root->left == NULL )
        {
            node_t* newRoot = root->right;
            free( root );
            return newRoot;
        }
        if ( root->right == NULL )
        {
            node_t* newRoot = root->left;
            free( root );
            return newRoot;
        }
        root->data = LeftMostValue( root->right );
        root->right = Delete( root->right, root->data );
    }
    return root;
}

void PreOrder(node_t* root){
    if(root != NULL)
    {
        printf("%d ", root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

void InOrder(node_t* root){
    if(root != NULL)
    {
        InOrder(root->left);
        printf("%d ", root->data);
        InOrder(root->right);
    }
}

void PostOrder(node_t* root){
    if(root != NULL)
    {
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%d ", root->data);
    }
}


int main()
{
    node_t* root = NULL;

    root = Insert( root, 25 );
    root = Insert( root, 15 );
    root = Insert( root, 50 );
    root = Insert( root, 10 );
    root = Insert( root, 22 );
    root = Insert( root, 35 );
    root = Insert( root, 70 );
    root = Insert( root, 4 );
    root = Insert( root, 12 );
    root = Insert( root, 18 );
    root = Insert( root, 24 );
    root = Insert( root, 31 );
    root = Insert( root, 44 );
    root = Insert( root, 66 );
    root = Insert( root, 90 );
    printf("\nDuyet preorder : ");
    PreOrder(root);
    printf("\nDuyet inorder  : ");
    InOrder(root);
    printf("\nDuyet postorder:");
    PostOrder(root);

    printf("\n==Thu them phan tu 15 vao BTS==\n");
    Insert(root, 15);
    printf("\nDuyet preorder : ");
    PreOrder(root);
    printf("\nDuyet inorder  : ");
    InOrder(root);
    printf("\nDuyet postorder:");
    PostOrder(root);


    printf("\n==Thu xoa phan tu 50 khoi BTS==\n");
    Delete(root, 50);
    printf("\nDuyet preorder : ");
    PreOrder(root);
    printf("\nDuyet inorder  : ");
    InOrder(root);
    printf("\nDuyet postorder:");
    PostOrder(root);




    Free( root );
    root = NULL;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

#include <stdio.h>

#include <stdlib.h>

typedef struct Node

{

int data;

Node* left;

Node* right;

} node_t;

void Free( node_t* root )

{

if ( root == NULL )

return;

Free( root->left );

Free( root->right );

free( root );

}

int LeftOf( const int value, const node_t* root )

{

// Nếu bạn muốn cây BST cho phép giá trị trùng lặp, hãy sử dụng dòng code thứ 2

return value < root->data;

// return value <= root->data;

}

int RightOf( const int value, const node_t* root )

{

return value > root->data;

}

node_t* Insert( node_t* root, const int value )

{

if ( root == NULL )

{

node_t* node = (node_t*)malloc( sizeof( node_t ) );

node->left = NULL;

node->right = NULL;

node->data = value;

return node;

}

if ( LeftOf( value, root ) )

root->left = Insert( root->left, value );

else if ( RightOf( value, root ) )

root->right = Insert( root->right, value );

return root;

}

bool Search( const node_t* root, int value )

{

if ( root == NULL )

return false;

if(root->data == value){

return true;

}else if ( LeftOf( value, root ) ){

return Search( root->left, value );

}else if( RightOf( value, root ) ){

return Search( root->right, value );

}

int LeftMostValue( const node_t* root )

{

while ( root->left != NULL )

root = root->left;

return root->data;

}

node_t* Delete( node_t* root, int value )

{

if ( root == NULL )

return root;

if ( LeftOf( value, root ) )

root->left = Delete( root->left, value );

else if ( RightOf( value, root ) )

root->right = Delete( root->right, value );

else

{

// root->data == value, delete this node

if ( root->left == NULL )

{

node_t* newRoot = root->right;

free( root );

return newRoot;

}

if ( root->right == NULL )

{

node_t* newRoot = root->left;

free( root );

return newRoot;

}

root->data = LeftMostValue( root->right );

root->right = Delete( root->right, root->data );

}

return root;

}

void PreOrder(node_t* root){

if(root != NULL)

{

printf("%d ", root->data);

PreOrder(root->left);

PreOrder(root->right);

}

void InOrder(node_t* root){

if(root != NULL)

{

InOrder(root->left);

printf("%d ", root->data);

InOrder(root->right);

}

void PostOrder(node_t* root){

if(root != NULL)

{

PostOrder(root->left);

PostOrder(root->right);

printf("%d ", root->data);

}

int main()

{

node_t* root = NULL;

root = Insert( root, 25 );

root = Insert( root, 15 );

root = Insert( root, 50 );

root = Insert( root, 10 );

root = Insert( root, 22 );

root = Insert( root, 35 );

root = Insert( root, 70 );

root = Insert( root, 4 );

root = Insert( root, 12 );

root = Insert( root, 18 );

root = Insert( root, 24 );

root = Insert( root, 31 );

root = Insert( root, 44 );

root = Insert( root, 66 );

root = Insert( root, 90 );

printf("\nDuyet preorder : ");

PreOrder(root);

printf("\nDuyet inorder : ");

InOrder(root);

printf("\nDuyet postorder:");

PostOrder(root);

printf("\n==Thu them phan tu 15 vao BTS==\n");

Insert(root, 15);

printf("\nDuyet preorder : ");

PreOrder(root);

printf("\nDuyet inorder : ");

InOrder(root);

printf("\nDuyet postorder:");

PostOrder(root);

printf("\n==Thu xoa phan tu 50 khoi BTS==\n");

Delete(root, 50);

printf("\nDuyet preorder : ");

PreOrder(root);

printf("\nDuyet inorder : ");

InOrder(root);

printf("\nDuyet postorder:");

PostOrder(root);

Free( root );

root = NULL;

return 0;

}

Trong hàm main tôi đã cài đặt BTS cho cây nhị phân sau:

Cây tìm kiếm nhị phân - Binary search tree — Cây nhị phân tìm kiếm được sử dụng trong source code

Nhờ các bạn kiểm tra kết quả chạy của code:

Duyet preorder : 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90
Duyet inorder  : 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90
Duyet postorder:4 12 10 18 24 22 15 31 44 35 66 90 70 50 25
==Thu them phan tu 15 vao BTS==

Duyet preorder : 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90
Duyet inorder  : 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90
Duyet postorder:4 12 10 18 24 22 15 31 44 35 66 90 70 50 25
==Thu xoa phan tu 50 khoi BTS==

Duyet preorder : 25 15 10 4 12 22 18 24 66 35 31 44 70 90
Duyet inorder  : 4 10 12 15 18 22 24 25 31 35 44 66 70 90
Duyet postorder:4 12 10 18 24 22 15 31 44 35 90 70 66 25
Process returned 0 (0x0)   execution time : 0.047 s
Press any key to continue.

Duyet preorder : 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90

Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90

Duyet postorder:4 12 10 18 24 22 15 31 44 35 66 90 70 50 25

==Thu them phan tu 15 vao BTS==

Duyet preorder : 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90

Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90

Duyet postorder:4 12 10 18 24 22 15 31 44 35 66 90 70 50 25

==Thu xoa phan tu 50 khoi BTS==

Duyet preorder : 25 15 10 4 12 22 18 24 66 35 31 44 70 90

Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 66 70 90

Duyet postorder:4 12 10 18 24 22 15 31 44 35 90 70 66 25

Process returned 0 (0x0) execution time : 0.047 s

Press any key to continue.

5. Bài tập thực hành

https://vn.spoj.com/problems/NKTREE/
http://ntucoder.net/Problem/List?ThemeID=17
https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/

Cây tìm kiếm nhị phân – Binary search tree

1. Lý thuyết về cây tìm kiếm nhị phân

2. Cài đặt cây BST

2.1. Hàm giải phóng dữ liệu

2.2. Hàm điều hướng của cây

2.3. Thêm phần tử vào BST

2.4. Tìm kiếm trên BST

2.5. Lấy giá trị con trái nhất

2.6. Xóa Node trong BST

1. Node cần xóa là Node lá(không có child nào cả)

2. Node cần xóa có 1 child

3. Node cần xóa có đủ 2 child

3. Duyệt cây tìm kiếm nhị phân

3.1. Duyệt PreOrder

3.2. Duyệt InOrder

3.1. Duyệt PostOrder

4. Code đầy đủ cây tìm kiếm nhị phân

5. Bài tập thực hành

Bài 70. Đọc ghi file trong C

Tính tổng các giá trị đối xứng trong mảng gồm các số nguyên.

Cài đặt code bài toán người du lịch cài đặt bằng C++, Java

Bài 37. Đổi số thập phân sang nhị phân và ngược lại

Hàm Khởi Tạo Và Hàm Huỷ

Bài 11. In mã ASCII của ký tự nhập từ bàn phím

1. Lý thuyết về cây tìm kiếm nhị phân

2. Cài đặt cây BST

2.1. Hàm giải phóng dữ liệu

2.2. Hàm điều hướng của cây

2.3. Thêm phần tử vào BST

2.4. Tìm kiếm trên BST

2.5. Lấy giá trị con trái nhất

2.6. Xóa Node trong BST

1. Node cần xóa là Node lá(không có child nào cả)

2. Node cần xóa có 1 child

3. Node cần xóa có đủ 2 child

3. Duyệt cây tìm kiếm nhị phân

3.1. Duyệt PreOrder

3.2. Duyệt InOrder

3.1. Duyệt PostOrder

4. Code đầy đủ cây tìm kiếm nhị phân

5. Bài tập thực hành

Similar Posts