어떻게 두 갈래 나무의 차원을 두루 훑어볼 수 있습니까

2894 단어 두 갈래 나무
핵심 사상:
우선, 두 갈래 나무의 가장 조상 노드를 대열에 넣는다
그리고 다음 절차를 반복해서 실행하여 대기열이 비어 있음을 알 수 있습니다.
1: 노드 아웃 대기열
2: 이 노드에 왼쪽 아이 노드가 있으면 왼쪽 아이 노드가 대열에 들어간다
3: 이 노드에 오른쪽 아이 노드가 있으면 오른쪽 아이 노드가 대열에 들어간다
void LayerOrder(BiTreeNode *head)
{
	LQueue Q;
	Initiate_Queue(&Q);
	BiTreeNode *p;
	if(head!=NULL) AppendQueue(&Q,head);
	while(QueueNotEmpty(&Q))
	{
		p=QueueDelete(&Q);
		cout<data<LChild!=NULL) AppendQueue(&Q,p->LChild);
		if(p->RChild!=NULL) AppendQueue(&Q,p->RChild);	
	}
}

전체 코드는 다음과 같습니다.
#include
using namespace std;

typedef struct biTreeNode
{
	char data;
	struct biTreeNode *LChild;
	struct biTreeNode *RChild;
}BiTreeNode;


void Initiate_Tree(BiTreeNode **head)
{
	(*head)=(BiTreeNode *)malloc(sizeof(BiTreeNode));
	(*head)->LChild=NULL;
	(*head)->RChild=NULL;
}

 BiTreeNode *InsertLChild(BiTreeNode *head,char x)
{
	if(head==NULL) return NULL;
	else
	{
	BiTreeNode *p1,*p2;
	p1=head->LChild;
	p2=(BiTreeNode*)malloc(sizeof(BiTreeNode));
	p2->data=x;
	p2->RChild=NULL;
	head->LChild=p2;
	p2->LChild=p1;
	return p2;
	}
}


BiTreeNode* InsertRChild(BiTreeNode *head,char x)
{
	if(head==NULL) return NULL;
	{
	BiTreeNode *p1,*p2;
	p1=head->RChild;
	p2=(BiTreeNode*)malloc(sizeof(BiTreeNode));
	p2->data=x;
	p2->LChild=NULL;
	head->RChild=p2;
	p2->RChild=p1;
	return p2;
	}
}

void DLR(BiTreeNode *head)
{
	if(head==NULL)  return;
	else
	{
	cout<data<LChild);
	DLR(head->RChild);
	}
}

//==================================================

typedef struct lNode
{
	BiTreeNode *data;
	struct lNode *next;
}LNode;


typedef struct lQueue
{
	LNode *front;
	LNode *rear;
}LQueue;


void Initiate_Queue(LQueue *Q)
{
	Q->front=NULL;
	Q->rear=NULL;
}

void AppendQueue(LQueue *Q,BiTreeNode *head)
{
	LNode *p1;
	p1=(LNode *)malloc(sizeof(LNode));
	p1->next=NULL;
	p1->data=head;
	if(Q->front==NULL)
	{
		Q->front=Q->rear=p1;
	}
	else
	{
		Q->rear->next=p1;
		Q->rear=p1;
	}
}

BiTreeNode * QueueDelete(LQueue *Q)
{
	if(Q->front==NULL) return NULL;
	else
	{
		BiTreeNode *p;
		p=Q->front->data;
		Q->front=Q->front->next;
		return p;
	}
}

int QueueNotEmpty(LQueue *Q)
{
	if(Q->front==NULL) return 0;
	else return 1;
}

// 
void LayerOrder(BiTreeNode *head)
{
	LQueue Q;
	Initiate_Queue(&Q);
	BiTreeNode *p;
	if(head!=NULL) AppendQueue(&Q,head);
	while(QueueNotEmpty(&Q))
	{
		p=QueueDelete(&Q);
		cout<data<LChild!=NULL) AppendQueue(&Q,p->LChild);
		if(p->RChild!=NULL) AppendQueue(&Q,p->RChild);	
	}
}


void main()
{
	BiTreeNode *head,*p,*p1;
	Initiate_Tree(&head);
	head->data='j';
	p=InsertLChild(head,'k');
	p=InsertLChild(p,'a');
	InsertRChild(head,'b');
	cout<

좋은 웹페이지 즐겨찾기