+ Trả lời chủ đề
Hiện kết quả từ 1 tới 2 của 2

Chủ đề: Cây nhị phân - Cài đặt bằng mảng

  1. #1
    Status : ngovanhieu_Alpha đang ẩn
    Tham gia ngày : Aug 2011
    Bài gửi : 200

    Cây nhị phân - Cài đặt bằng mảng

    Cây nhị phân - Cài đặt bằng mảng


    Tại nút thứ i:
    • - Con trái là nút 2*(i+1)-1
      - Con phải 2*(i+1)


    Chương trình minh họa cây nhị phân cài đặt bằng mảng.
    Mã:
    #include <stdio.h>
    #include <conio.h>
    #define max 100
    #define MAXLENGTH 100			//chi so toi da cua mang
    #define NIL -1
    typedef int DataType;
    typedef int Node;
    typedef struct {
    	DataType Data[MAXLENGTH];	//Luu gia tri cua nut
    	int MaxNode;
    }Tree;
    //Kiem tra cay rong
    int EmptyTree(Tree T) {
    	return T.MaxNode == 0;
    }
    //Xac dinh nut goc trong cay
    Node Root(Tree T) {
    	if (!EmptyTree(T))
    		return 0;
    	else
    		return NIL;
    }
    //con trai cua nut p
    int Left_Child(Node p, Tree T) {
    		return 2*(p+1) - 1;
    }
    //con phai cua nut p
    int Right_Child(Node p, Tree T) {
    		return 2*(p+1);
    }
    //duyet tien tu
    void NLR(Node p, Tree T) {
    	if(T.Data[p]!=NIL) {
    		printf("%d  ", T.Data[p]);
    		NLR(Left_Child(p,T),T);
    		NLR(Right_Child(p,T),T);
    	}
    }
    //duyet trung tu
    void LNR(Node p, Tree T) {
    	if(T.Data[p]!=NIL) {
    		LNR(Left_Child(p,T),T);
    		printf("%d  ", T.Data[p]);
    		LNR(Right_Child(p,T),T);
    	}
    }
    //duyet hau tu
    void LRN(Node p, Tree T) {
    	if(T.Data[p]!=NIL) {
    		LRN(Left_Child(p,T),T);
    		LRN(Right_Child(p,T),T);
    		printf("%d  ", T.Data[p]);
    	}
    }
    /*doc cay
    neu khong co con trai hoac phai thi nhap -1*/
    void Read_Tree(Tree * T) {
    	int i = 0, Child = 0;
    	printf("Nhap vao so nut: ");
    	scanf("%d",&(*T).MaxNode);
    	while(i<(*T).MaxNode) {
    		if(i==0)
    		{
    			printf("Nut goc:");
    			scanf("%d",&(*T).Data[i]);
    			(*T).Data[Left_Child(i,*T)] = NIL;
    			(*T).Data[Right_Child(i,*T)] = NIL;
    			i++;
    		}
    		else
    		if((*T).Data[Child]!=NIL)
    		{	int k;
    			printf("Con trai %d: ",Child);
    			k = Left_Child(Child,*T);
    			scanf("%d",&(*T).Data[k]);
    			if((*T).Data[k] != NIL) {
    				(*T).Data[Left_Child(k,*T)] = NIL;
    				(*T).Data[Right_Child(k,*T)] = NIL;
    				i++;
    			}
    			printf("Con phai %d: ",Child);
    			k = Right_Child(Child,*T);
    			scanf("%d",&(*T).Data[k]);
    			if((*T).Data[k] != NIL) {
    				(*T).Data[Left_Child(k,*T)] = NIL;
    				(*T).Data[Right_Child(k,*T)] = NIL;
    				i++;
    			}
    			Child++;
    		}
    	}
    }
    void main() {
    	Tree T;
    	clrscr();
    	Read_Tree(&T);
    	printf("Duyet tien tu.\n");
    	NLR(Root(T),T);
    	printf("\nDuyet trung tu.\n");
    	LNR(Root(T),T);
    	printf("\nDuyet hau tu.\n");
    	LRN(Root(T),T);
    	getch();
    }

  2. #2
    Status : Administrator đang ẩn
    Tham gia ngày : Aug 2011
    Đến từ : Ninh Kiều - Cần Thơ
    Bài gửi : 1.450

    Re: Cải tiến

    Mã:
    #include <stdio.h>
    #include <conio.h>
    #define MAXLENGTH 100			//chi so toi da cua mang
    #define NIL -1
    typedef int DataType;
    typedef int Node;
    typedef struct {
    	DataType Data[MAXLENGTH];	//Luu gia tri cua nut
    	int MaxNode;
    }Tree;
    //Kiem tra cay rong
    int EmptyTree(Tree T) {
    	return T.MaxNode == 0;
    }
    //Xac dinh nut goc trong cay
    Node Root(Tree T) {
    	if (!EmptyTree(T))
    		return 0;
    	else
    		return NIL;
    }
    //con trai cua nut p
    int Left_Child(Node p, Tree T) {
    		return 2*(p+1) - 1;
    }
    //con phai cua nut p
    int Right_Child(Node p, Tree T) {
    		return 2*(p+1);
    }
    //duyet tien tu
    void NLR(Node p, Tree T) {
    	if(T.Data[p]!=NIL) {
    		printf("%d  ", T.Data[p]);
    		NLR(Left_Child(p,T),T);
    		NLR(Right_Child(p,T),T);
    	}
    }
    //duyet trung tu
    void LNR(Node p, Tree T) {
    	if(T.Data[p]!=NIL) {
    		LNR(Left_Child(p,T),T);
    		printf("%d  ", T.Data[p]);
    		LNR(Right_Child(p,T),T);
    	}
    }
    //duyet hau tu
    void LRN(Node p, Tree T) {
    	if(T.Data[p]!=NIL) {
    		LRN(Left_Child(p,T),T);
    		LRN(Right_Child(p,T),T);
    		printf("%d  ", T.Data[p]);
    	}
    }
    /*doc cay
    neu khong co con trai hoac phai thi nhap -1*/
    void Read_Tree(Tree * T) {
    	int i = 0, Child = 0;
    	printf("Nhap vao so nut: ");
    	scanf("%d",&(*T).MaxNode);
    	while(i<(*T).MaxNode) {
    		if(i==0)
    		{	printf("Nut goc:");
    			scanf("%d",&(*T).Data[i]);
    			(*T).Data[Left_Child(i,*T)] = NIL;
    			(*T).Data[Right_Child(i,*T)] = NIL;
    			i++;
    		}
    		else
    		if((*T).Data[Child]!=NIL)
    		{	int k;
    			printf("Con trai %d: ",Child);
    			k = Left_Child(Child,*T);
    			scanf("%d",&(*T).Data[k]);
    			if((*T).Data[k] != NIL) {
    				(*T).Data[Left_Child(k,*T)] = NIL;
    				(*T).Data[Right_Child(k,*T)] = NIL;
    				i++;
    			}
    			printf("Con phai %d: ",Child);
    			k = Right_Child(Child,*T);
    			scanf("%d",&(*T).Data[k]);
    			if((*T).Data[k] != NIL) {
    				(*T).Data[Left_Child(k,*T)] = NIL;
    				(*T).Data[Right_Child(k,*T)] = NIL;
    				i++;
    			}
    			Child++;
    		}
    		else
    		{
    			Child++;
    		}
    	}
    }
    void main() {
    	Tree T;
    	clrscr();
    	Read_Tree(&T);
    	printf("Duyet tien tu.\n");
    	NLR(Root(T),T);
    	printf("\nDuyet trung tu.\n");
    	LNR(Root(T),T);
    	printf("\nDuyet hau tu.\n");
    	LRN(Root(T),T);
    	getch();
    }

+ Trả lời chủ đề

Quyền viết bài

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
Trang Chủ Việc Làm Gia Sư Gia sư