[데이터 구 조 를 깊이 이해] 이 진 트 리 실천

데이터 구조의 본질:
데이터 구 조 는 데이터 의 논리 구조 와 물리 구조 와 그들의 상호 관 계 를 연구 하고 이런 구조 에 대해 해당 하 는 연산 을 정의 하 는 것 이다.
무엇이 논리 구조 입 니까?
데이터 간 의 논리 적 관 계 는 우 리 는 보통 네 가지 로 나 뉜 다.
1) 집합 , 구조 중의 데이터 요 소 는 같은 유형 에 속 하 는 것 을 제외 하고 다른 관계 가 없다.
2) 선형 구조 , 구조 중의 데이터 요소 사이 에 일대일 의 관계 가 존재 한다.
3) 트 리 구조 ,  구조 중의 데이터 요소 사이 에는 한 쌍 이상 의 관계 가 존재 한다.
4) 도형 구조 또는 망상 구조 , 구조 중의 데이터 요소 사이 에는 여러 쌍 의 관계 가 존재 한다.
무엇이 물리 구조 입 니까?
메모리 에 저 장 된 데이터 형식 은 보통 두 가지 로 나 뉜 다.
1) 순서대로 저장 하고 메모리 에 엄 격 히 연속 저장 하 며 배열 을 통 해 이 루어 질 수 있 습 니 다.
2) 체인 저장, 메모리 에 연속 저장 되 지 않 고 포인터 로 이 루어 집 니 다.
논리 구조 와 물리 구조의 상호 관 계 는 어떤 의의 가 있 습 니까?
논리 구조 가 복잡 할 수록 순서 저장 의 단점 이 뚜렷 하고 체인 식 저장 의 장점 이 두드러진다.
주: 다음은 모두 체인 저장 소 로 분석 합 니 다.
 
단 방향 링크

typedef struct node
{
     datetype val;      //     
     struct node *next; //       
}

양 방향 링크

typedef struct node
{
     datetype val;      //     
     struct node *head; //       
     struct node *rear; //       
}

이 진 트 리
하나의 결점 과 두 그루 가 서로 교차 하지 않 는 좌우 자나무 로 구성 되 어 있 으 며, 좌우 자 나 무 는 모두 이 진 트 리 이다.

typedef struct btree
{
     datetype val; //    
     btree *left;  //     
     btree *right; //     
}B;

 

/*
   ：Btree.c
  ：
1）            ，      ，      ，       （       ——DLR）。
2）         ，    ——  ——  ——    。

    ：2012-7-3 15:23
  ：  
*/
#include<stdio.h>
#include<stdlib.h>

typedef struct Bitree
{
	int data;
	struct Bitree *Lchild;   //   
	struct Bitree *Rchild;   //   
}BitreeNode;

typedef BitreeNode *LinkBitree;

typedef struct Stack
{
	LinkBitree data[20];
	int top,bottom;
}Stack;

typedef Stack *StackList;
//  
LinkBitree CreatBitree();
//    
StackList InitStack();
//    
void InorderTraverse(LinkBitree Head, StackList Stack);


int main()
{
	LinkBitree BitreeHead;
	StackList Stack;

	printf("        ：e = ");
	BitreeHead = CreatBitree();

	Stack = InitStack();

	InorderTraverse(BitreeHead, Stack);

	return 0;
}

/*
  ：  ‘     ’    
  ：       
  ： 
*/
LinkBitree CreatBitree()
{
	int edata;//   
	LinkBitree Head;

	scanf("%d", &edata);
     //      0，            
	if(edata==0)
	{
		Head = NULL;
	}
	else
	{
          Head = (LinkBitree)malloc(sizeof(BitreeNode));
          //memory check
	     if(Head == NULL)
		{
			printf("      ！！");
		     exit(0);
		}
		else
		{
			Head->data = edata;
			printf("     %d      ：e= ", Head->data);
			Head->Lchild = CreatBitree();
			printf("     %d      ：e= ", Head->data);
			Head->Rchild = CreatBitree();
		}
	}
	return Head;
}

/*
  ：    
            。
*/
StackList InitStack()
{
	StackList Stack;
	Stack = (StackList)malloc(sizeof(Stack));
	if(Stack == NULL)
	{
		printf("      ！！");
		exit(0);
	}
	else
	{
		Stack->top = 0;
		Stack->bottom = 0;
	}
	return Stack;
}

//      ，     ，     
void InorderTraverse(LinkBitree Head, StackList Stack)
{
	do
	{
		while (Head != NULL) //          
		{
			printf("%d ", Head->data);     //        
			Stack->data[Stack->top] = Head;//         
			Stack->top++;                  //  
			Head = Head->Lchild;           //        
		}
		if (Stack->top != 0)//     
		{
			Stack->top--;
			Head = Stack->data[Stack->top]; //  
			Head = Head->Rchild;            //        
		}
	}
	while(Stack->top != 0 || Head != NULL);
}