PDA

View Full Version : ADT - Cây nhị phân tìm kiếm - Cách cài đặt trong C++



Achillesbk
29-11-2007, 12:12 AM
Mấy hôm nay subforum Cấu trúc dữ liệu hình như nóng lên thì phải,em mới gia nhập diễn đàn thôi,mí hôm nọ định đóng góp thêm bài viết về Stack và Queue cài đặt dùng Danh sách liên kết,nhưng mờ lại đang thi tư tưởng HCM,hôm này tưng hửng về định đăng thì các bác lại chuyển sang chủ đề khác mất roài,thôi thì iem mới nghiên cứu về ADT Cây nhị phân tìm kiếm,đăng lun để mọi người góp ý cho iem,và nếu ai đang nghiên cứu thì bàn luận.

Định nghĩa :Cây nhị phân tìm kiếm là cây nhị phân mà trong đó giá trị khoá của mọi nút là lớn hơn giá trị khoá trong các nút thuộc cây con trái,và nhỏ hơn giá trị khoá trong các nút thuộc cây con phải của nó.
Chú ý : Ta có thể xem mỗi nút như một nút gốc,mà cây con trái và cây con phải bao gồm các nút con trái và con phải tương ứng của nó.

-Để thuận tiện cho việc cài đặt ta có thể định nghĩa cấu trúc của một nút đơn giản như sau :
+ Con trỏ left trỏ tới cây con trái.
+ Con trỏ right trỏ tới cây con phải.
+ Trường info dùng để lưu trữ dữ liệu người dùng.


struct TreeNode
{
ItemType info;// ItemType la kieu du lieu.
TreeNode *left;
TreeNode *right;
};
Trong các bài toán phức tạp hơn ta có thể định nghĩa cấu trúc của nút một cách tuơng tự.


Các phép toán cơ bản
1.MakeEmpty()
+Chức năng: Khởi tạo cây tới trạng thái rỗng.
+Điều kiện sau : Cây tồn tại và ở trạng thái rỗng

2.Boolean IsEmpty()
+Chức năng: Kiểm tra xem liệu cây có rỗng hay không.
+Điều kiện sau : Giá trị hàm = ( cây là rỗng ? ).

3.Boolean IsFull()
+Chức năng: Kiểm tra xem cây có đầy hay không.
+Điều kiện sau : Giá trị hàm = ( cây là đầy ? ).

4.int LengthTree()
+Chức năng : Cho biết số lượng phần tử hiện có trong cây.
+Điều kiện sau : Giá trị hàm = Số lượng phần tử trong cây.

-Số lượng nút trên cây nhị phân là xác định nếu như ta biết được số lượng nút trên cây con trái và số lượng nút trên cây con phải.Khi đó
Nút trên cây = Nút trên cây con trái + nút trên cây con phải + 1.
-Điều này gợi ý cho ta cài đặt dùng thuật toán đệ quy.Sử dụng hàm CountNodes để đếm số lượng nút, sau đó hàm LengthTree() sẽ gọi và truyền con trỏ root tới CountNodes như một đối số.
Hàm CountNodes
+ Chức năng : Đếm số lượng Nút.
+ BS : Nếu cây rỗng trả lại 0.
+ RS : Trả lại CountNodes( left-> subtree) + CountNodes( right-> subtree) + 1.

5.RetrieveItem( ItemType& item, bool& found )
+Chức năng : Truy tìm trong cây phần tử có key giống với key của item.
+Điều kiện trước:Khoá của item đã được khởi tạo.
+Điều kiện sau : Nếu như tồn tại một phần tử someItem mà key của nó giống với key của item thì found = true,và item là một bản sao của someItem, nếu không found = false.

-Để tìm kiếm một phần tử item nào đó với thành phần key đã xác định trên cây nhị phân tìm kiếm.Trước hết, ta so sánh key của nó với key của nút gốc để quyết định xem liệu nút cần tìm có phải là nút gốc hay không, nếu không thì sẽ tiếp tục quá trình tìm kiếm trên cây con trái hay cây con phải.
-Việc tìm kiếm trên cây con trái hay cây con phải cũng được thực hiện tương tự cho tới khi tìm kiếm được,hoặc là không.
Như vậy, quá trình tìm kiếm có thể được thực hiện một cách đệ quy.Trường hợp cở sở xuất hiện khi hoặc nút cần tìm là nút gốc hoặc cây là rỗng (item không được tìm thấy trên cây).
-Ta có thể cài đặt hàm đệ quy Retrieve() mà hàm RetrieveItem() gọi tới và truyền cho nó con trỏ root như một đối số.

Hàm Retrieve
+ Chức năng : Truy tìm trên cây phân tử có key giống với key của item.
+ BS : (1) key của item bằng với key của nút gốc, khi đó thiết lập
found = true và lưu item vào tree -> info( cập nhật lại).
(2) Nếu cây là rỗng thì found = false.
+ RS : Nếu key của item nhỏ hơn key của tree -> info thì
Retrieve( tree -> left,item,found), nếu không
Retrieve( tree -> right,item,found).
6.InsertItem( ItemType item )
+Chức năng : Thêm một phần tử vào cây.
+Điều kiện trước: Cây chưa đầy.
+Điều kiện sau: item được chèn vào vị trí thích hợp trên cây đảm bảo duy trì thuộc tìm kiếm nhị phân

-Chèn một phần tử mới vào cây không những đòi hỏi phải duy trì thuộc tính hình dạng của cây mà còn phải đảm bảo thuộc tính tìm kiếm nhị phân của nó.Ta sẽ chèn thêm một nút mới vào cây tại một vị trí thích hợp như một nút lá.
-Cũng như các thuật toán đã cài đặt ở trên,ta viết hàm đệ quy Insert để chèn một phần tử vào cây,hàm mang theo một con trỏ tree tới nút gốc của cây.Hàm InsertItem đơn giản gọi tới hàm này và truyền cho nó con trỏ root như một tham chiếu

7.DeleteItem( ItemType item )
+Chức năng : Xoá phần tử có key giống với key của item.
+Điều kiện trước : Thành phần key của item đã được khởi tạo
Có duy nhất một phần tử trên cây có key giống với key của item.
+Điền kiện sau : Không tồn tại phần tử nào trên cây có key giống với key của item

- Trước hết, ta viết hàm Delete mang theo một con trỏ tree tới gốc của một cây để xoá đi một nút trên cây.Hàm DeleteItem đơn giản gọi tới và truyền cho hàm này con trỏ root như một tham chiếu.
- Để xoá đi một nút trên cây hàm Delete cần thực hiện hai bước sau :
+ Tìm nút cần xoá trên cây.
+ Loại bỏ nút cần xoá khỏi cây.
-Bước thứ nhất được thực hiện hoàn toàn giống như đã thực hiện khi cài đặt hàm Retrieve.Bước thứ hai phức tạp hơn xong ta có thể khái quát thành ba trường hợp cơ bản sau, tuỳ thuộc vào nút cần xoá:
• Nút cần xoá là một nút lá : Việc xoá nó được thực hiện hết sức đơn giản, ta chỉ cần thiết lập liên kết cha của nút đó thành NULL.
• Nút cần xoá chỉ có một con : Việc xoá được thực hiện bằng cách thiết lập liên kết giữa cha của nút cần xoá tới con của nó.
• Nút cần xoá có hai con : Trường hợp này phức tạp hơn,ta không thể áp dụng phương pháp đã thực hiện khi xoá nút với chỉ một con, vì như thế sẽ làm mất đi thuộc tính hình dạng của cây nhị phân tìm kiếm.Thay vào đó ta đưa ra giải pháp thay thế thành phần info của nút cần xoá bằng thành phần info từ một nút khác mà vẫn duy trì được thuộc tính tìm kiếm nhị phân.,sau đó nút khác này sẽ được xoá đi.Như vậy, ta chỉ cần giải quyết vấn đề nút được thay thế. Đó chính là nút mà giá trị key của nó gần nhất nhưng nhỏ hơn ( hoặc lớn hơn )giá trị key nút cần xoá,nút này còn được gọi là tiền nhiệm –predecessor ( kế nhiệm-successor).Nút tiền nhiệm (cũng như kế nhiệm ) này chỉ có thể có một nút con hoặc không có nút con nào,việc xoá nó sau đó được thực hiện đơn giản.
-Trong phân tích trên,hàm Delete sẽ cần tới một thủ tục xoá đi một nút, để chương trình được sáng sủa ta viết hàm DeleteNode để xoá đi một nút, hàm này sẽ được Delete gọi tới,và một hàm GetPredecessor để tìm người tiền nhiệm.

8.PrintOrderTree
+Chức năng : In ra các phần tử theo kiểu duyệt cây.

-Để duyệt một danh sách tuyến tính chỉ có hai cách : tiến (forward) hoặc lùi (backward).Song đối với cây nhị phân ta có nhiều cách ,phổ dụng nhất là :
+ Duyệt theo thứ tự trước (PreOrder) .
+ Duyệt theo thứ tự giữa ( InOrder).
+ Duyệt theo thứ tự sau (PostOrder).
-Mỗi cách duyệt thể hiện ưu điểm riêng của nó tuỳ trong trường hợp cụ thể.Chẳng hạn như để in ra các phần tử theo thứ tự tăng dần ta duyệt cây theo thứ tự giữa, hay để huỷ một cây thì duyệt theo thứ tự sau là thích hợp nhất,mỗi nút sẽ được xoá đi nếu như cây con trái và cây con phải của nó đã được phá huỷ.
-Việc duyệt cây có thể được định nghĩa đệ quy một cách khái quát như sau :

PreOrder(tree)
Nếu tree # NULL thì :
Thăm tree->info;
PreOrder(tree->left);
PreOrder(tree->right);

InOrder(tree)
Nếu tree # NULL thì :
InOrder(tree->left);
Thăm tree->info;
InOrder(tree  left);

PostOrder(tree)
Nếu tree # NULL thì :
PostOrder(tree->left);
PostOrder(tree->right);
Thăm tree->info;

-Khi ta nói “Thăm” một nút ,điều đó được hiểu là những thao tác trên nút,chẳng hạn in ra giá trị,tính tổng của các thành phần,hay cập nhật lại một trường nào đó trong thành phần info của mỗi nút.
-Để minh hoạ cho các phép duyệt, ta viết hàm PrintOrderTree để in ra giá trị của các nút theo kiểu duyệt do người dùng nhập vào,và tuỳ vào kiểu duyệt mà hàm gọi tới các hàm hỗ trợ tương ứng.
[/TEX]
Và dưới đây là toàn bộ mã của ADT BST:

Khai báo lớp ADT BST được đặt trong file TreeType.h


// Khai bao lop ADT Cay nhi phan tim kiem.
#include<iostream>

struct TreeNode;

enum OrderType { PRE_ORDER, IN_ORDER, POST_ORDER };

typedef int ItemType;
// Gia su rang thanh phan key chua trong moi nut co kieu don gian int
// Doi voi nhung kieu phuc tap hon ta co the dinh nghia tuong tu.

#ifndef TREETYPE_H
#define TREETYPE_H

class TreeType
{
public:
TreeType(); // Constructor.
~TreeType(); // Destructor.
TreeType( const TreeType& originalTree );// Copy Constructor.
void operator=( const TreeType& originalTree );
// Ham nap chong toan tu.
void MakeEmpty(); // Dua cay ve trang thai rong.
bool IsEmpty() const; // Kiem tra xem cay co rong hay khong.
bool IsFull() const; // Kiem tra xem cay co day hay khong.
int LengthTree();// Ham tra lai so phan tu co tren cay.
int DepthTree(); // Ham tra lai chieu sau cua cay.
void RetrieveItem( ItemType& item,bool &found );
// Ham truy luc toi phan tu tren cay co key giong voi key cua item.
void InsertItem( ItemType item ); // Chen mot phan tu vao cay.
void DeleteItem( ItemType item);
// Xoa phan tu tren cay co key giong voi key cua item.
void Print( std::ofstream& outFile);
// In ra outFile cac phan tu theo thu tu tang dan.
void PrintOrderTree( OrderType order );
// In ra noi dung cac nut theo kieu duyet order.
private:
TreeNode *root;
};

#endif


Định nghĩa ADT BST được đặt trong file TreeType.cpp


#include<iostream>
#include<cstddef>
#include<iomanip>
#include<fstream>

using namespace std;

#include "TreeType.h"

struct TreeNode
{
ItemType info;// Thong tin tren node;
TreeNode *left;// Con tro toi cay con trai.
TreeNode *right;// Con tro toi cay con phai.
};

// Nguyên mẫu của các hàm bổ trợ

void Destroy(TreeNode*& tree);
void CopyTree( TreeNode*& copy,const TreeNode *originalTree );
int CountNodes(TreeNode *tree);
int Depth(TreeNode *tree);
void Retrieve( TreeNode *tree, ItemType& item, bool& found);
void Insert( TreeNode*& tree, ItemType item);
void Delete( TreeNode*& tree, ItemType item);
void DeleteNode(TreeNode*& tree);
void GetPredecessor(TreeNode *tree, ItemType& data);
void PrintTree( TreeNode *tree, std::ofstream& outFile );
void PrintPreOrder( TreeNode *tree );
void PrintInOrder( TreeNode *tree );
void PrintPostOrder( TreeNode *tree );


// Dinh nghia cac ham cua lop.

TreeType::TreeType()
{
root = NULL;
}

TreeType::~TreeType()
{
Destroy(root);
}

TreeType::TreeType( const TreeType& originalTree )
{
CopyTree( root, originalTree.root );
}

void TreeType::operator=( const TreeType& originalTree )
{
if(&originalTree == this)
return;

Destroy(root);
CopyTree(root,originalTree.root);
}

void TreeType::MakeEmpty()
{
Destroy(root);
root = NULL;
}

bool TreeType::IsEmpty() const
{
return(root == NULL);
}

bool TreeType::IsFull() const
{
TreeNode *location;

location = new TreeNode;

if(location == NULL)
return true;
else
return false;
delete location;
}

int TreeType::LengthTree()
{
return CountNodes(root);
}

int TreeType::DepthTree()
{
return Depth(root);
}

void TreeType::RetrieveItem( ItemType& item, bool& found)
{
Retrieve(root,item,found);
}

void TreeType::InsertItem(ItemType item)
{
if( IsFull() )
{
cout << "Het bo nho de cap phat !\n";
exit(1);
}

Insert(root,item);
}

void TreeType::DeleteItem( ItemType item)
{
if( IsEmpty() )
{
cout << setw(25) << " " << "Cay rong !\n";
return;
}

Delete(root,item);
}

void TreeType::Print(std::ofstream& outFile)
{
PrintTree(root,outFile);
}

void TreeType::PrintOrderTree( OrderType order )
{
switch(order)
{
case PRE_ORDER: PrintPreOrder(root);
break;
case IN_ORDER:
PrintInOrder(root);
break;
case POST_ORDER : PrintPostOrder(root);
break;
}
}


// Dinh nghia cac ham ho tro.


void Destroy(TreeNode*& tree)
{
if(tree != NULL)
{
Destroy(tree->left);
Destroy(tree->right);
delete tree;
}
}

void CopyTree( TreeNode*& copy,const TreeNode *originalTree )
{
if(originalTree == NULL )
copy = NULL;
else
{
copy = new TreeNode;
copy->info = originalTree->info;

CopyTree(copy->left,originalTree->left);
CopyTree(copy->right,originalTree->right);
}
}

int CountNodes(TreeNode *tree)
{
if(tree == NULL)
return 0;
else
return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}

int Depth(TreeNode *tree)
{
if(tree == NULL)
return 0;
int leftSubTreeDepth = Depth(tree->left);
int rightSubTreeDepth = Depth(tree->right);

return (1 + (leftSubTreeDepth > rightSubTreeDepth ? leftSubTreeDepth : rightSubTreeDepth));
}

void Retrieve( TreeNode *tree, ItemType& item, bool& found)
{
if(tree == NULL)
found = false;
else if(item < tree->info)
Retrieve(tree->left,item,found);
else if(item > tree->info)
Retrieve(tree->right,item,found);
else
{
found = true;
item = tree->info;
}
}

void Insert( TreeNode*& tree, ItemType item)
{
if(tree == NULL)
{
tree = new TreeNode;

tree->info = item;
tree->left = NULL;
tree->right = NULL;
}

else if(item < tree->info)
Insert(tree->left,item);// Chen vao cay con trai.
else if(item > tree->info)
Insert(tree->right,item);// Chen vao cay con phai.
}

void Delete( TreeNode*& tree, ItemType item )
{
if(item < tree->info)
Delete(tree->left,item);
else if(item > tree->info)
Delete(tree->right,item);
else
DeleteNode(tree);
}

void DeleteNode(TreeNode*& tree)
{
ItemType data;
TreeNode *temPtr;

temPtr = tree;

if(tree->left == NULL)
{
tree = tree->right;
delete temPtr;
}
else if(tree->right == NULL)
{
tree = tree->left;
delete temPtr;
}
else
{
GetPredecessor(tree->left,data);

tree->info = data;
Delete(tree->left,data);
}
}

void GetPredecessor( TreeNode *tree, ItemType& data )
{
while(tree->right != NULL)
tree = tree->right;

data = tree->info;
}

void PrintTree( TreeNode *tree, std::ofstream& outFile )
{
if(tree != NULL)
{
PrintTree(tree->left,outFile);
outFile << tree->info;
PrintTree(tree->right,outFile);
}
}

void PrintPreOrder( TreeNode *tree )
{
if( tree != NULL )
{
cout << setw(3) << tree->info;
PrintPreOrder( tree->left );
PrintPreOrder( tree->right );
}
}

void PrintInOrder( TreeNode *tree )
{
if( tree != NULL )
{
PrintInOrder( tree->left );
cout << setw(3) << tree->info;
PrintInOrder( tree-> right );
}
}

void PrintPostOrder( TreeNode *tree )
{
if( tree != NULL )
{
PrintPostOrder( tree->left );
PrintPostOrder( tree->right );
cout << setw(3) << tree->info;
}
}

Hàm main có thể được cài đặt như sau để kiểm tra cây nhị phân mà ta vừa cài đặt trên.


// Test thu cac ham thao tac tren Cay nhi phan tim kiem.
#include<iostream>
#include<iomanip>

using namespace std;

#include "TreeType.h"

int main()
{
TreeType myTree;
ItemType item;
OrderType order;
int choice,option;
bool found;

cout << setw(15) << " " << "CHUONG TRINH TEST THU CAY NHI PHAN TIM KIEM\n"
<< setw(15) << " " << "==========================================="
<< "\n\n\n";
cout << setw(20) << " " << "1:Tao cay ADT BST\n"
<< setw(20) << " " << "2:Chen phan tu moi vao cay BST\n"
<< setw(20) << " " << "3:Xoa phan tu khoi cay BST\n"
<< setw(20) << " " << "4:Truy tim phan tu\n"
<< setw(20) << " " << "5:In ra tong so phan tu\n"
<< setw(20) << " " << "6:In ra chieu sau cua cay\n"
<< setw(20) << " " << "7:In ra cac phan tu theo kieu duyet\n"
<< setw(20) << " " << "8:Huy cay da duoc tao\n"
<< setw(20) << " " << "9:Thoat khoi ung dung\n\n";

while(1)
{
cout << "Nhap vao lua chon cua ban:";
cin >> choice;

switch(choice)
{
case 1: int number;
cout << "Nhap so luong nut :";
cin >> number;

while(number > 0)
{
cout << "Nhap gia tri :";
cin >> item;

myTree.InsertItem(item);
number--;
}
break;

case 2: cout << "Nhap vao mot so nguyen :";
cin >> item;

myTree.InsertItem(item);
break;

case 3: cout << "Nhap vao phan tu can xoa :";
cin >> item;
myTree.DeleteItem(item);
break;

case 4: cout << "Nhap phan tu can tim kiem :";
cin >> item;

myTree.RetrieveItem(item,found);

if( found == true)
cout << "Phan tu co mat tren cay !\n";
else
cout << "Phan tu khong co tren cay !\n";
break;

case 5: cout << "So phan tu hien co tren cay la: "
<< myTree.LengthTree() << endl;
break;

case 6: cout << "Chieu sau cua cay la: "
<< myTree.DepthTree() << endl;
break;

case 7: cout << setw(20) << " " << "1:Duyet theo thu tu truoc\n"
<< setw(20) << " " << "2:Duyet theo thu tu giua\n"
<< setw(20) << " " << "3:Duyet theo thu tu sau\n";

cout << "Nhap vao lua chon cua ban:";
cin >> option;

order = (OrderType) (option-1);

if( myTree.IsEmpty() )
{
cout << "Cay rong!\n";
break;
}

else
myTree.PrintOrderTree(order);
cout << endl;
break;
case 8: myTree.MakeEmpty();
break;
case 9: return 0;

}
}

return 0;
}


Hì hì muộn roài,có chi các bác cho ý kiến,lần sau iem xin cài đặt một số hàm hok dùng đệ quy.

kidkid
29-11-2007, 08:20 AM
Cậu viết BST mà lại ko có chức năng rotation thì làm sao đảm bảo cây balance được. Updates gấp nhé.

Thế này , hôm nào tớ viết cái này rồi mang lên đây cùng thảo luận giờ tớ nói chay nhé.

Cái hàm delete của cậu theo tớ có chút vấn đề, vấn đề nhỏ thôi vì chả có sách nào nói cả .

Nếu mà Node cần del có 2 lá. Thì cậu đi tìm nút tiền nhiệm (min leftSubTree) hoặc nút kế nhiệm ( max rightSubTree ) đúng ko ? Điều tớ muốn nói là ở chỗ chữ hoặc. Chính nó là nguyên nhân khiến cây mất cân bằng mà với thao tác này ( tớ nghĩ ra ) sẽ giảm khả năng đó đi.

ví dụ tớ cho cây con subRoot (A,B) với độ cao A= B - 1 hay A nhỏ hơn B 1. giờ xóa subRoot , node này có 2 subTree A,B mặc định theo funtion của cậu thì sẽ delete node tiền nhiệm có nghĩa là độ cao có khả năng = B - 2 dẫn đến mất cân bằng . Nhưng nếu thay vào đó cậu tìm nút kế nhiệm thì có phải là độ cao A=B ko ?

Điều tớ muốn nói là tại sao sách nào cũng OR mà không phải là AND, nếu cài đặt theo kiểu của tớ thì có phải là khả năng mất cần bằng sẽ giảm rất nhiều. Bằng cách:
if(H(leftSubTree =< rightSubTree)
{tim nút tiền nhiệm}
else
{tìm nút kế nhiệm}

Đặc biệt là các hàm giúp cho cây cân bằng . Ngoài 2 phép quay chuẩn trên liệu có cách nào nữa không ?

Cuối cùng xin thay mặt anh em cảm ơn bài viết rất chi tiết của cậu. Mong được thảo luận nhiều hơn . Thân KidKid.

coolkid
29-11-2007, 09:26 AM
đây là cây BST chứ ko phải AVL nên ko cần balance. Nhưng nếu có balance thì càng tốt.

Achillesbk
29-11-2007, 10:56 AM
thanks bác kidkid đã góp ý.Nhưng theo iem,nhược điểm lớn nhất của ADT BST chính là trường hợp cây mất cân bằng,mà việc này do từ dữ liệu đầu vào,nếu người dùng nhập cây theo thứ tự tăng dần hay giảm dần,thì cây thu được là cây suy biến,việc tìm kiếm một key trên cây giống nhu trong danh sách liên kết vậy 0(N).Ý tưởng trong hàm xóa của bác cũng là một ý kiến hay,có thể sửa code đơn gian như sau,ta thêm một hàm GetSuccessor để tìm người kế nhiệm,chỉnh trong hàm DeleteNode điều kiện như bác nêu ra,nhưng nếu người dùng nhập dữ liệu như iem nói trên thì hok hiệu quả lắm.Nói chung mỗi cấu trúc có một điểm mạnh riêng,ta có thể thấy sự khắc phục tính mất cân bằng trong cây AVL hay trong Heap,Priority Queue, Black-Red tree,có dịp iem xin trình bày

tienlbhoc
13-12-2007, 07:50 PM
cây avl , cây đỏ đen, search trên wikipedia ấy, sẽ có giới thiệu khá tổng quát, cái này khắc phục mất cân bằng của cây nhị phân còn code thế nào thì tìm mấy ebook đầy ra đấy

fuji13
12-11-2011, 10:02 PM
Các anh chị cho em hỏi chút ạ.Ở hàm IsFull() thì có nghĩa là cây chỉ đầy khi mà máy tính không còn đủ bộ nhớ đề cấp phát cho chương trình ạ? Và khi đó nếu yêu cầu cấp phát 1 vung nhớ thì nó sẽ trỏ đến NULL ạ?
Tại em đọc 1 vài tài liệu thì chỉ thấy khi cài đặt bằng mảng người ta mới có Hàm IsFull() thôi
Mong anh chị giúp đỡ !

treatmaster
13-11-2011, 10:46 AM
Các anh chị cho em hỏi chút ạ.Ở hàm IsFull() thì có nghĩa là cây chỉ đầy khi mà máy tính không còn đủ bộ nhớ đề cấp phát cho chương trình ạ? Và khi đó nếu yêu cầu cấp phát 1 vung nhớ thì nó sẽ trỏ đến NULL ạ?
Tại em đọc 1 vài tài liệu thì chỉ thấy khi cài đặt bằng mảng người ta mới có Hàm IsFull() thôi
Mong anh chị giúp đỡ !


cây đầy đủ là cây mà có mọi nút lá đều có bậc bằng nhau.ko phải hết bộ nhớ.

fuji13
13-11-2011, 03:35 PM
cây đầy đủ là cây mà có mọi nút lá đều có bậc bằng nhau.ko phải hết bộ nhớ.

bool IsFull() const; // Kiem tra xem cay co day hay khong.
Bạn hiểu sai ý mình hỏi thì phải

treatmaster
13-11-2011, 09:44 PM
cây chỉ đầy khi mà máy tính không còn đủ bộ nhớ đề cấp phát cho chương trình ạ?

mình đọc đoạn này.
thế ko hiểu ý của bạn là gì nữa nhỉ.

bachkimz
19-10-2012, 09:23 PM
thankz pro ::beauty:

nobjta_9x_tq
04-11-2012, 03:02 AM
Thanks bạn nhé, mình mới học, làm mãi mới được. Trả là cái hàm insert mình không insert root mà tạo con trỏ khác=root sau đó insert con trỏ này, thế là ko được mặc dù đã tham chiếu ItemType*& p rồi, có ai giải thích dùm mình không?

nobjta_9x_tq
04-11-2012, 03:07 AM
Thanks bro nhé.(:))(:))(:))

nghiaofox
13-11-2012, 10:59 PM
bạn ơi làm mình chưa hiểu hàm delete lắm
trong hàm delete thì truy xuất đến deletenode
trong hàm deletenode thì truy xuất đến delete
khi mình để hàm delete trc hàm deletenode thì nó bảo : "deletenode not found " và ngược lại
và cho mình nếu mình dùng hàm search để biết vị trí của node cần xóa, vậy mình có vị trí nó rồi thì minh sữ dụng delete sao nhỉ?