Gia sư Cần Thơ, Dạy Kèm Cần Thơ

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

Share

freb
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 4
Join date : 21/10/2010

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

Bài gửi  freb on Thu Oct 21, 2010 8:57 am

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



admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

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

Bài gửi  admin on Thu Oct 21, 2010 11:39 am

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.

freb
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 4
Join date : 21/10/2010

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

Bài gửi  freb on Fri Oct 22, 2010 6:52 am

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

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

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

Bài gửi  admin on Fri Oct 22, 2010 7:02 am

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

ghhg
Nhập môn
Nhập môn

Tổng số bài gửi : 5
Points : 10
Join date : 29/07/2010

Cây tổng quát - cài đặt bằng con trỏ

Bài gửi  ghhg on Thu Jan 06, 2011 4:15 pm

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;


admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

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

Bài gửi  admin on Thu Jan 06, 2011 5:14 pm

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.

redblue
Nhập môn
Nhập môn

Tổng số bài gửi : 1
Points : 1
Join date : 06/01/2011

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

Bài gửi  redblue on Thu Jan 06, 2011 6:47 pm

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;

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

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

Bài gửi  admin on Fri Jan 07, 2011 10:21 am

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.

Sponsored content

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

Bài gửi  Sponsored content Today at 11:35 pm


    Hôm nay: Mon Dec 05, 2016 11:35 pm