Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn Phí
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn PhíĐăng Nhập

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu

power_settings_newLogin to reply
4 posters

descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệuThu Oct 21, 2010 8:57 am

more_horiz
mình có 1 đề bài là Kiểm tra cây nhị phân T có phải là "cây nhị phân tìm kiếm" hay không?

mình thì có ý tưởng thế nhưng ko biết có đúng hết hay ko?

mình duyệt hết tất cả các nút (có thể duyệt theo thứ tự Left - Node - Right)

Tại nút đó
mình chia ra 3 trường hợp
trường hợp nút lá
--> khỏi kiểm tra
trường hợp nút 1 nhánh
--> nếu như có nhánh Left xét Node->Left->info >= Node->info thì ko phải cây tìm kiếm
--> nếu như có nhánh Right xét Node->Right->info <= Node->info thì ko phải cây tìm kiếm
trường hợp nút 2 nhánh
--> Xét !(Node->Left->info < Node->info && Node->info < Node->Right->info) thì ko phải cây tìm kiếm

ko bit ý tượng như vậy có đúng ko?
xin mọi người góp ý dùm


descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyRe: Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệuThu Oct 21, 2010 11:39 am

more_horiz
CHO CẤU TRÚC DỮ LIỆU CÂY NHỊ PHÂN

Code:

//Cau truc cua Node
typedef struct Node{
  int info;
  Node*Left;
  Node*Right;
}Node;
//Dinh nghia cay nhi phan
typedef Node * Tree;

KIỂM TRA CÂY T CÓ PHẢI CÂY TÌM KIẾM NHỊ PHÂN HAY KHÔNG
Hàm trả về 0 nếu T là cây nhị phân ngược lại là 1

Code:

char Test(Tree T) {
   if(!T->Left && !T->Right)
      return 0;
   else
   if(!T->Left && T->Right && T->info<T->Right->info)
      return Test(T->Right)
   else
   if(!T->Right && T->Left &&T->info>T->Left->info)
      return Test(T->Left)
   else
   if(T->Left && T->Right && T->Left->info<T->info && T->info<T->Right->info)
         return Test(T->Left) + Test(T->Right);
   else
      return 1;
}


Được sửa bởi Admin ngày Fri Oct 22, 2010 11:10 am; sửa lần 2.

descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyRe: Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệuFri Oct 22, 2010 6:52 am

more_horiz
nếu theo cái cây này thì đoạn code trên sẽ return 0 có nghĩa là cây nhị phân tìm kiếm nhưng rõ ràng đây ko phải là cây nhị phân tìm kiếm
Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu Cayj

descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyRe: Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệuFri Oct 22, 2010 7:02 am

more_horiz
Bạn chỉ cần duyệt trung tự (LNR): danh sách duyệt theo thứ tự tăng là ok!

descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyCây tổng quát - cài đặt bằng con trỏThu Jan 06, 2011 4:15 pm

more_horiz
Cho một cây tổng quát mà mỗi nút của cây được đánh số thứ tự từ 0. Người ta biểu diễn cây này bằng cách sử dụng một danh sách liên kết các nút trong. Mỗi nút trong này có chứa một con trỏ, trỏ đến danh sách các nút con của nó. Hãy khai báo cấu trúc dữ liệu có tên là Tree để biểu diễn cây tổng quát được mô tả ở trên

Mình có cách khai báo sau, xin mọi người chỉnh sửa giúp

Code:

#define maxnodes…

typedef struct{
int no;
Node *Next;
} Node;

typedef Node *ChildList;

typedef struct {
ChildList Clist[maxnodes];
int numnodes;
} Tree;


descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyRe: Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệuThu Jan 06, 2011 5:14 pm

more_horiz

Code:

#define MaxNodes …

typedef struct{
   int no;
   Node *Next;
} Node;

typedef Node *ChildList;

typedef struct {
   ChildList CList[MaxNodes];
   unsigned int NumNodes;
} Tree;


Cấu trúc dữ liệu được mô tả trên là khá tốt và nó sẽ tốt hơn nữa khi bạn khai báo các tên biến cho phù hợp với phong cách lập trình. Tuy nhiên, quá trình cài đặt có thành công ý tưởng của bạn hay không còn tuỳ thuộc rất nhiều vào kỹ thuật lập trình của bạn. Chúc bạn thành công.

descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyRe: Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệuThu Jan 06, 2011 6:47 pm

more_horiz
Hình như có chút vấn đề thì phải

Cho một cây tổng quát mà mỗi nút của cây được đánh số thứ tự từ 0. Người ta biểu diễn cây này bằng cách sử dụng một danh sách liên kết các nút trong. Mỗi nút trong này có chứa một con trỏ, trỏ đến danh sách các nút con của nó. Hãy khai báo cấu trúc dữ liệu có tên là Tree để biểu diễn cây tổng quát được mô tả ở trên

Code:

#define maxnodes…

typedef struct{
int no;
Node *Next;
} Node;

typedef Node *ChildList;

typedef struct {
ChildList Clist[maxnodes];  //Danh sách các nodes trong được thực thi bởi mảng, không phải là danh sách liên kết
int numnodes;
} Tree;

descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyRe: Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệuFri Jan 07, 2011 10:21 am

more_horiz
typedef struct {
ChildList Clist[maxnodes]; //Danh sách các nodes trong được thực thi bởi mảng, không phải là danh sách liên kết
int numnodes;
} Tree;


Mỗi phần tử của mảng là 1 danh sách liên kết.

descriptionHỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu EmptyRe: Hỏi đáp - Trao đổi về cây trong Cấu trúc dữ liệu

more_horiz
privacy_tip Permissions in this forum:
Bạn không có quyền trả lời bài viết
power_settings_newLogin to reply