【アルゴリズム導論】二叉木の深さ優先遍歴

ツリーの深さ優先ループ
二叉木の遍歴は深さ優先遍歴と広さ優先遍歴に分けられる.本編では深さ優先遍歴,次編では広さ優先遍歴を紹介する.
ツリーの再帰的定義から,ツリーはルートノード(D),左サブツリー(L),右サブツリー(R)の3つの基本部分から構成されていることが分かる.この3つの基本部分を順に遍歴できれば、二叉木全体を遍歴することができます.この3つの部分の配列は3!=6種類に限定されて左から右へ遍歴すると、DLR(先序)、LDR(中序)、LRD(後序)の3種類しか遍歴しない.
具体的には、次のようになります.

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define maxsize 10
typedef int datatype;
typedef struct node
{
	datatype data;
	struct node *lchild,*rchild;
} bitree;//        

bitree* CreatBitree(int* arrayA,int n);//     （       ）
void preorder(bitree *p);//      
void midorder(bitree *p);//      
void postorder(bitree *p);//      

void main()
{
	int arrayA[9]={0,1,2,3,4,5,6,7,8};//             ，       
	int n=sizeof(arrayA)/sizeof(int);

	bitree *head=NULL;//           

	head=CreatBitree(arrayA,n);//    

	printf("    ：");
	preorder(head);
	printf("
    ：");
	midorder(head);
	printf("
    ：");
	postorder(head);
	printf("
");
}

bitree* CreatBitree(int* arrayA,int n)//          
{
	bitree *root;
	bitree *queue[maxsize];//              
	bitree *p;
	int front,rear;
	front=1;rear=0;//       
	root=NULL;

	for(int i=1;i<n;i++)
	{
		p=(bitree*)malloc(sizeof(bitree));//       
		p->data=arrayA[i];
		p->lchild=NULL;
		p->rchild=NULL;

		rear++;
		queue[rear]=p;

		if(rear==1)//             
			root=p;
		else
		{
			if(i%2==0)//       
				queue[front]->lchild=p;
			else//       
			{
				queue[front]->rchild=p;
				front=front+1;
			}
		}

	}

	return root;
}

void preorder(bitree *p)//    
{
	if(p!=NULL)
	{
		printf("%d ",p->data);
		preorder(p->lchild);
		preorder(p->rchild);
	}
	return;
}

void midorder(bitree *p)//    
{
	if(p!=NULL)
	{
		
		midorder(p->lchild);
		printf("%d ",p->data);
		midorder(p->rchild);
	}
	return;
}

void postorder(bitree *p)//    
{
	if(p!=NULL)
	{
		postorder(p->lchild);
		postorder(p->rchild);
		printf("%d ",p->data);
	}
	return;
}

注:プログラムが間違っている場合は、次のリンクをクリックしてください.説明
原文:http://blog.csdn.net/tengweitw/article/details/9787223
作者:nineheadedbird