데이터 구조의 트 리 와 이 진 트 리 - 이 진 트 리 의 기본 동작

5235 단어 데이터 구조
문제: 이 진 트 리 의 기본 조작 함수 입 니 다. 주요 내용 은 이 진 트 리 의 데이터 구조 입 니 다. 이 진 트 리 를 초기 화하 고 이 진 트 리 를 없 애고 이 진 트 리 의 깊이, 이 진 트 리 부모 노드, 이 진 트 리 왼쪽 아이, 이 진 트 리 오른쪽 아이, 이 진 트 리 왼쪽 형제, 이 진 트 리 오른쪽 형 제 를 만 듭 니 다. 이름 에 따라 이 진 트 리 노드 를 찾 고 노드 를 삽입 하 며 노드 를 삭제 합 니 다.
//이 진 트 리 데이터 구조
typedef struct BiTNode
{
	TElemType data;
	struct BiTNode* lchild, * rchild;
}BiTNode, *BiTree;

//이 진 트 리 초기 화
FILE* BTEF;
BiTree InitBiTree()
{
	BiTree bt;
	bt = NULL;
	BTEF = fopen("BiTreeElem.txt", "r");
	return bt;
}

//이 진 트 리 제거
void DestroyBiTree(BiTree bt)
{
	if(bt)
	{
		DestroyBiTree(bt->lchild);
		DestroyBiTree(bt->rchild);
		free(bt);
	}
        fclose(BTEF);
}
 
  //创建二叉树 
   
  

//通过文本文件读取二叉树节点信息,空节点以“0”表示,节点顺序为二叉树先序遍历顺序

void CreatBiTree(BiTree *bt)
{
	char node;

	fread(&node, sizeof(char), 1, BTEF);
	if(node==' ')
		fread(&node, sizeof(char), 1, BTEF);

	if(node=='0')
		*bt = NULL;
	else
	{
		if(*bt==NULL)
			*bt = (BiTree) malloc (sizeof(BiTNode));
		(*bt)->data = node;
		(*bt)->lchild = NULL;
		(*bt)->rchild = NULL;
		CreatBiTree(&(*bt)->lchild);
		CreatBiTree(&(*bt)->rchild);
	}
}

//텍스트 정보 샘플
/*A B D 0 F 0 0 0 C 0 E G 0 0 0*/
//이 진 트 리 깊이 구하 기
int BiTreeDepth(BiTree bt)
{
	int leftBTDepth, rightBTDepth;

	if(bt==NULL)
		return 0;
	else
	{
		leftBTDepth = BiTreeDepth(bt->lchild)+1;
		rightBTDepth = BiTreeDepth(bt->rchild)+1;
		return leftBTDepth>rightBTDepth? leftBTDepth:rightBTDepth;
	}
}

//이 진 트 리 부모 노드
//정 보 를 찾 는 근 거 는 노드 이름 이 고 반환 값 은 노드 포인터 입 니 다.
BiTNode* BiTreeParent(BiTree bt, TElemType elem)
{
	BiTNode* btn;
	if(bt!=NULL)
	{
		if (bt->lchild!=NULL)
		{
			if(bt->lchild->data!=elem)
			{
				btn = BiTreeParent(bt->lchild,elem);
				if(btn!=NULL)
					return btn;
			}
			else
				return bt;
		}
		if (bt->rchild!=NULL)
		{
			if(bt->rchild->data!=elem)
				return BiTreeParent(bt->rchild,elem);
			else
				return bt;
		}
	}
	return NULL;
}

//이 진 트 리 왼쪽 아이
 
  
BiTNode* LeftChild(BiTree bt, TElemType elem)
{
	BiTNode* tbn;
	if(bt!=NULL)
	{
		if(bt->data==elem)
			return bt->lchild;
		else
		{
			tbn = LeftChild(bt->lchild, elem);
			if(tbn!=NULL)
				return tbn;
			return LeftChild(bt->rchild, elem);
		}
	}
	return NULL;
}

//이 진 트 리 오른쪽 아이
 
  
BiTNode* RightChild(BiTree bt, TElemType elem)
{
	BiTNode* tbn;
	if(bt!=NULL)
	{
		if(bt->data==elem)
			return bt->rchild;
		else
		{
			tbn = RightChild(bt->lchild, elem);
			if(tbn!=NULL)
				return tbn;
			return RightChild(bt->rchild, elem);
		}
	}
	return NULL;
}

//이 진 트 리 왼쪽 형제
 
  
BiTNode* LeftSibling(BiTree bt, TElemType elem)
{
	BiTNode *tbn;
	if(bt==NULL)
		return NULL;
	if (bt->rchild!=NULL)
	{
		if(bt->rchild->data==elem)
			return bt->lchild;
		else
		{
			tbn = LeftSibling(bt->rchild, elem);
			if(tbn!=NULL)
				return tbn;
		}
	}
	 return LeftSibling(bt->lchild, elem);
}

//이 진 트 리 오른쪽 형제
 
  
BiTNode* RightSibling(BiTree bt, TElemType elem)
{
	BiTNode *tbn;
	if(bt==NULL)
		return NULL;
	if (bt->lchild!=NULL)
	{
		if(bt->lchild->data==elem)
			return bt->lchild;
		else
		{
			tbn = RightSibling(bt->lchild, elem);
			if(tbn!=NULL)
				return tbn;
		}
	}
	return RightSibling(bt->rchild, elem);
}

//이름 에 따라 이 진 트 리 노드 찾기
 
  
BiTNode* SearchNode(BiTree bt, TElemType elem)
{
	BiTNode *tbn;
	if(bt==NULL)
		return NULL;
	if(bt->data==elem)
		return bt;
	else
	{
		tbn = SearchNode(bt->lchild, elem);
		if(tbn!=NULL)
			return tbn;
		return SearchNode(bt->rchild, elem);
	}
	return NULL;
}

//노드 삽입
//     ,           ,        ,                
int InsertChild(BiTree bt, TElemType elem, int LR, BiTree child)
{
	BiTNode* pn;
	if (!child||!bt||(LR!=0&&LR!=1))
		return -1;
	if (LR==0)
	{
		pn = LeftChild(bt, elem);
		if(pn==NULL)
			SearchNode(bt, elem)->lchild = child;
		else
			return -1;
	} 
	else
	{
		pn = RightChild(bt, elem);
		if(pn==NULL)
			SearchNode(bt, elem)->rchild = child;
		else
			return -1;
	}
	return 0;
}

//노드 삭제
 
  
int DeleteChild(BiTree bt, TElemType elem, int LR)
{
	BiTNode* pn;
	if(!bt||(LR!=0&&LR!=1))
		return -1;
	if(LR==0)
	{
		pn = LeftChild(bt, elem);
		if(pn!=NULL)
		{
			DeleteChild(bt, pn->data, 0);
			DeleteChild(bt, pn->data, 1);
			free(pn);
			if((pn=SearchNode(bt,elem))!=NULL)
				pn->lchild = NULL;
		}
	}else
	{
		pn = RightChild(bt, elem);
		if(pn!=NULL)
		{
			DeleteChild(bt, pn->data, 0);
			DeleteChild(bt, pn->data, 1);
			free(pn);
			if((pn=SearchNode(bt,elem))!=NULL)
				pn->rchild = NULL;
		}
	}
}

좋은 웹페이지 즐겨찾기