duongvandeoit Administrator
Tổng số bài gửi : 41 Join date : 24/03/2010 Age : 36 Đến từ : Cà Mau City
| Tiêu đề: Tổng hợp bài tập về Cây Tue Mar 01, 2011 9:48 am | |
| code cài đặt cây bằng mảng. Dưới đây là code cài đặt cây bằng mảng, bạn nào không hiểu thì pm admin hướng dẫn thêm. - Code:
-
/* Chuong trinh cai dat cay tong quat bang mang*/ #include "conio.h" #include "stdio.h"
#define MAXLENGTH 100 //chi so toi da cua mang #define NIL -1 typedef char DataType; typedef int Node; typedef struct { DataType Data[MAXLENGTH]; //Luu gia tri cua nut Node Parent[MAXLENGTH]; //Cha cua nut i se luu o vi tri i trong mang int MaxNode; }Tree;
//Khoi tao cay rong void MakeNull_Tree (Tree *T) { (*T).MaxNode=0; } //Kiem tra cay rong int EmptyTree(Tree T) { return T.MaxNode == 0; } //Xac dinh nut cha cua nut tren cay Node Parent(Node n,Tree T) { if (EmptyTree(T) || (n>T.MaxNode-1)) return NIL; else return T.Parent[n]; } //Xac dinh gia tri cua nut tren cay DataType Label_Node(Node n,Tree T) { if (!EmptyTree(T) && (n<=T.MaxNode-1)) return T.Data[n]; } //Xac dinh nut goc trong cay Node Root(Tree T) { if (!EmptyTree(T)) return 0; else return NIL; } //Ham xac dinh con trai nhat cua mot nut Node LeftMostChild(Node n,Tree T) { Node i; int found; if (n<0) return NIL; i=n+1; found=0; while ((i<=T.MaxNode-1) && !found) if (T.Parent[i]==n) found=1; else i=i+1; if (found) return i; else return NIL; } //Ham xac dinh anh em ruot phai cua mot nut Node RightSibling(Node n,Tree T) { Node i,parent; int found; if (n<0) return NIL; parent=T.Parent[n]; i=n+1; found=0; while ((i<=T.MaxNode-1) && !found) if (T.Parent[i]==parent) found=1; else i=i+1; if (found) return i; else return NIL; } //Duyet tien tu void PreOrder(Node n,Tree T) { Node i; printf("%c ",Label_Node(n,T)); i=LeftMostChild(n,T); while (i!=NIL) { PreOrder(i,T); i=RightSibling(i,T); } } //Duyet trung tu void InOrder(Node n,Tree T) { Node i; i=LeftMostChild(n,T); if (i!=NIL) InOrder(i,T); printf("%c ",Label_Node(n,T)); i=RightSibling(i,T); while (i!=NIL){ InOrder(i,T); i=RightSibling(i,T); } } //Duyet hau tu void PostOrder(Node n,Tree T) { Node i; i=LeftMostChild(n,T); while (i!=NIL){ PostOrder(i,T); i=RightSibling(i,T); } printf("%c ",Label_Node(n,T)); } //Doc cay void ReadTree(Tree *T){ int i; MakeNull_Tree(&*T); do { printf("Cay co bao nhieu nut? "); scanf("%d",&(*T).MaxNode); } while (((*T).MaxNode<1) || ((*T).MaxNode>MAXLENGTH)); printf("Nhap nhan cua nut goc: "); fflush(stdin); scanf("%c",&(*T).Data[0]); (*T).Parent[0]=NIL; /* nut goc khong co cha */ for (i=1;i<=(*T).MaxNode-1;i++){ printf("Nhap cha cua nut %d: ",i); scanf("%d",&(*T).Parent[i]); printf("Nhap nhan cua nut %d: ",i); fflush(stdin); scanf("%c",&(*T).Data[i]); } } //Chuong trinh chinh void main(){ clrscr(); Tree T; printf("Nhap du lieu cho cay tong quat\n"); ReadTree(&T); printf("\nDanh sach duyet tien tu cua cay vua nhap la\n"); PreOrder(Root(T),T); printf("\nDanh sach duyet trung tu cua cay vua nhap la\n"); InOrder(Root(T),T); printf("\nDanh sach duyet hau tu cua cay vua nhap la\n"); PostOrder(Root(T),T); getch(); }
| |
|