Mình cần giúp đỡ về cây nhị phân !!!

[buon_vi_dep_2003]

Mình mới tham gia diễn đàn này .Mong các bạn chỉ dẫn giùm nha !!!
Thầy giảng không hiểu gì hết đó !!!

Mình đọc sách thầy Nguyễn Hồng Chương “Cấu trúc dữ liệu cài đặt bằng C”.Phần cây nhị phân thì thầy định nghĩa như sau :

#include <…>

#typedef int Item

struct nodetype
{
item data;
struct nodetype *left;
struct nodetype *right;
// struct nodetype * father;
};
typedef struct nodetype * NODEPTR;

bây giờ muốn định nghĩa lại theo cấu trúc Class của C++ thì phải định nghĩa ra sao? Mong các anh,các bạn chỉ giúp ???.
Tương tự,như vậy cho Hash Table (bảng băm) thì sao ?

#include <…>

#typedef int Item
#define M 100
struct nodes
{
Item key;
Struct nodes * next;
};
typedef struct nodes * NODEPTR;
NODEPTR bucket (M);

viết lại theo class ????

[Xmen]

đơn giản là bạn thay chữ struct bằng chữ class, rồi trong đó để public tuốt tuồn tuột:

class nodetype
{
public:
item data;
nodetype *left;
nodetype *right;
nodetype * father;


};
tương tự cho hash table.

[dongthao]

Theo mình nghĩ bạn nên có kiến thức về C++ trước khi học ve CTDL.
Bạn nên xem kĩ lại về phần Class va struct thì sẽ hiểu thôi mà. Nếu đã xem rồi mà vẫn không hiểu thì hỏi tiếp nhé. Vì bây giờ nếu có trả lời như anh Xmen thì có lẽ bạn cũng không rõ đâu.

[buon_vi_dep_2003]

Theo mình nghĩ bạn nên có kiến thức về C++ trước khi học ve CTDL.
Bạn nên xem kĩ lại về phần Class va struct thì sẽ hiểu thôi mà. Nếu đã xem rồi mà vẫn không hiểu thì hỏi tiếp nhé. Vì bây giờ nếu có trả lời như anh Xmen thì có lẽ bạn cũng không rõ đâu.

Cảm ơn bạn dongthao nhắc nhở nhưng mà mình học môn đó rồi .Trường mình thì Struct và Class học trong phần Kỹ thuật lập trình và mình đã qua rồi mới dám đăng ký học CTDL2 (Cấu Trúc Dữ Liệu 2)==> không hiểu bài Binary Tree ,AVL Tree và Hash Table .Mình mới post bài lên đây hỏi nè !!!

[mhz_bk]

Thế em học trường nào mà lại có môn CTDL2 vậy? Ai giảng mà em không hiểu gì hết đấy?

[buon_vi_dep_2003]

Cho mình hỏi với ?Mình có bài tập như sau :
Xuất : Nhập số phần tử n : Nhập : ( gỉa sử) 5
Xuất : ( gỉa sử ) 6 2 8 9 4 (hàm randomInit)
Xuất : left ://số vòng quay trái
Nhập : (giả sử ) 3
Xuất : 8 9 4 6 2
Xuất : right : // số vòng quay phải
Nhập : (giả sử) 2
Xuất : 4 6 2 8 9

Câu hỏi : Xây dựng hàm theo cấu trúc Class đối với class Link & List (danh sách liên kết)và các hàm thành viên để chạy chương trình miêu tả trên
bài này mình giải quyết bằng mảng được rồi nhưng mà cấu trúc Link & List thì đành post lên hỏi vậy ?????Mong giúp đỡ?Mình đả giải quyết bằng mảng được rồi còn Link & List thì post lên đây ?Nhờ mọi người giúp?

[buon_vi_dep_2003]

Sao bài này mình post lâu rồi mà khộng ai giúp hết vậy ???? buồn !!!

[bete]

Thân gửi bvd:bạn thử cài đặt cấu trúc xâu liên kết kép vòng (Circular doubly linked list) xài cái class nodetype của bạn coi sao.

Bạn có thể tham khảo ví dụ mẫu ở:

http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Dllists/

http://www.google.com/search?hl=en&ie=UTF-8&q=circular+doubly+linked+list

[black hole]

help me
Cả nhà cho tôi hỏi một chút được không.
Giả sử chúng ta đã có một mảng một chiều đã được sắp thứ tự thì có thể chuyển thành một cây nhị phân tìm kiếm bằng một thuật toán tương đối dễ dàng và rất nhanh.
Thế còn bây giờ đã có một cây nhị phân tìm kiếm thì làm thế nào để chuyển nó thành một mảng một chiều đã được sắp xếp, thuật toán cụ thể thế nào và độ phức tạp thời gian là bao nhiêu?
Có ai có thể trả lời giúp tôi không?

[black hole]

hỏi mãi sao không có ai trả lời thế nhỉ.

[bete]

Thế còn bây giờ đã có một cây nhị phân tìm kiếm thì làm thế nào để chuyển nó thành một mảng một chiều đã được sắp xếp, thuật toán cụ thể thế nào và độ phức tạp thời gian là bao nhiêu?

Tui nghĩ bạn duyệt theo thứ tự giữa (con bên trái -- gốc -- con bên phải) => O(E+V) ?
(E: số cạnh; V: số đỉnh)

-thân

[black hole]

Theo mình thì như thế vẫn còn chậm lắm vì mỗi một đỉnh cha phải duyệt qua 3 lần vì nó là con trái hoặc con phải của một đỉnh nào đó và lại là cha của hai con.
Có cách nào nhanh hơn không nhỉ.

[Antone]

Nếu đã có một cây nhị phân tìm kiếm rồi thì chuyện đưa sang mảng một chiếu cực kì đơn giản, bagn chỉ cần duyệt theo LNR ( Left Node Right) là xong thôi, duyệt theo phương pháp này thì được một mảng có thứ tự tăng!

[741274177611]

các bạn có code vời duyệt cây nhị phân bằng đồ họa không vậy cho mình xin với,thanks