ツリー、ツリーのソート

ツリーといえば、これはデータ構造の中で非常に重要なデータ構造であり、ツリーの一種であり、それ自体が再帰的な性質を持っているため、ツリーに基づくいくつかのアルゴリズムは再帰アルゴリズムで実現しやすい.非線形構造としては、線形構造よりも比較的複雑で、アルゴリズムの意味さえ読めず、理解できない人が多い.実は最初はこれらのものに接触するのはまだ気絶していますが、何度も見てみると、搭乗実現はそんなに複雑ではないと思います.最後に、これらのデータ構造はプログラム設計の能力を高めるのに役立ち、ソフトウェア開発にも欠かせないことがわかります.
ツリーの表現方法は一般的に2つあり、1つ目は一般的に順序格納構造であり、ツリー内のノード情報を1次元配列に格納する.
2つ目もよく使われる方法で、チェーンテーブルで表すと、ノードに値があり、左サブツリーポインタと右サブツリーポインタは、アルゴリズムの便利さのために親ノードポインタがある場合があります.一般的な構成は次のとおりです.

//BLG        
typedef struct BLGNode 
{
	int data;			//   
	struct BLGNode *lchild;	//   
	struct BLGNode *rchild;	//   
}BLGNode,* BLGTree;

ここでは汎用型は用いず,整数値を代表として用いた.
二叉ソートツリーも二叉木で、二叉検索ツリーとも呼ばれ、動的な検索構造であり、その左サブツリーのノードの値はルートノードの値より小さく、右サブツリーのノードの値はルートノードの値より大きく、左右サブツリーもそれぞれ二叉ソートツリーである.その中順遍歴は昇順ソートに値する.だからこの木をソートツリーと言います.
以下に関連する実装コードを示します.

void initBTree(struct BLGNode **bt)
{
	*bt = NULL;
}

bool emptyBLGTree(BLGTree bt)
{
	if (bt != NULL)
	{
		return true;
	}
	return 0;
}

int blgtreeDepth(BLGTree &bt)
{
	//     ,   0    
	if (NULL == bt)
	{
		return 0;
	}
	else
	{
		int depth1 = blgtreeDepth(bt->lchild);	//     
		int depth2 = blgtreeDepth(bt->rchild);	//     
		if (depth1 > depth2)
		{
			return depth1 + 1;
		}
		else
		{
			return depth2 + 1;
		}
	}
}

void ClearBLGTree(BLGTree *bt)
{
	//
	if (*bt != NULL)
	{
		ClearBLGTree(&((*bt)->lchild));
		ClearBLGTree(&((*bt)->rchild));
		free(*bt);
		*bt = NULL;
	}
	return;
}

void preOrder(BLGTree &bt)
{
	//
	if (bt != NULL)
	{
		printf("%d\t",bt->data);
		preOrder(bt->lchild);
		preOrder(bt->rchild);
	}
	return;
}

void inOrder(BLGTree &bt)
{
	if (bt != NULL)
	{
		inOrder(bt->lchild);
		printf("%d\t",bt->data);
		inOrder(bt->rchild);
	}
	return;
}

void postOrder(BLGTree &bt)
{
	if (bt != NULL)
	{
		postOrder(bt->lchild);
		postOrder(bt->rchild);
		printf("%d\t",bt->data);
	}
	return;
}

int InsertBLG(BLGTree& bt,int e)
{
	//            
	BLGNode* p = (BLGNode *)malloc(sizeof(BLGNode));
	p->data = e;
	p->lchild = NULL;
	p->rchild = NULL;

	if (bt == NULL)
	{
		bt = p;
		return 1;
	}
	else
	{
		if (e < bt->data)
		{
			InsertBLG(bt->lchild,e);	//      
		}
		else
		{
			InsertBLG(bt->rchild,e);	//      
		}
		return 1;
	}
	return 0;
}

void CreateBLGTree(BLGTree& bt,int* value,int cnt)
{
	int i = 0;
	initBTree(&bt);		//       
	for (;i < cnt; i ++)
	{
		InsertBLG(bt,value[i]);
	}

	return;
}

上記のコードはテストで使用できますが、何か改善が必要な場合は、みんなで議論することができます.