二叉木の遍歴と実現方法

3765 ワード

二叉木の遍歴は二叉木の操作の基礎である.二叉木は再帰的に定義されているので、再帰的なアルゴリズムが二叉木を巡ることを考えやすいのですが、二叉木を巡る非再帰的なアルゴリズムを書くことができますか?答えは一定だ.次に、非再帰アルゴリズムを実現する考えを説明します.非再帰アルゴリズムを実装する場合,ツリーのルートノードを順次スタックに入れ,その後スタックを出る.では、自然な問題は、ツリーのルートノードがいつスタックに入るかということです.いつ宿を出ますか.次は私の実装コードです.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct node 
{
	char str, flag;
	struct node * lchild, * rchild;
}Tree_Node;

void build_Tree(Tree_Node* & root)
{
	//                ：
	char c;
	scanf("%c",&c);
	if(c == '#')return;
	//       :
    Tree_Node *tmp_Node = (Tree_Node *)malloc(1*sizeof(Tree_Node));
	tmp_Node->str = c; tmp_Node->flag = '\0';
	tmp_Node->lchild = tmp_Node->rchild = NULL;
	root = tmp_Node;
	//        ：
	build_Tree(tmp_Node->lchild);
	//        ：
	build_Tree(tmp_Node->rchild);
}

void PreOrderTraverse_recursive(Tree_Node * root)
{
	if(root == NULL)return;
	printf("%c",root->str);
	PreOrderTraverse_recursive(root->lchild);
	PreOrderTraverse_recursive(root->rchild);
}
void InOrderTraverse_recursive(Tree_Node * & root)
{
	if(root == NULL)return;
	InOrderTraverse_recursive(root->lchild);
	printf("%c",root->str);
	InOrderTraverse_recursive(root->rchild);
}

void NextOrderTraverse_recursive(Tree_Node * root)
{
	if(root == NULL)return;
	NextOrderTraverse_recursive(root->lchild);
	NextOrderTraverse_recursive(root->rchild);
	printf("%c",root->str);
}
void PreOrderTraverse_no_recursive(Tree_Node * root)
{
	stack S; S.push(root);
	while(!S.empty())
	{
		Tree_Node * tmp = S.top();
		if(tmp == NULL)S.pop();
		else if(tmp->flag == '\0')
		{
			printf("%c",tmp->str);
			tmp->flag = 'l';
			S.push(tmp->lchild);
		}
		else if(tmp->flag == 'l') 
		{
			tmp->flag = 'r';
			S.push(tmp->rchild);
		}
		else if(tmp->flag == 'r')
		{
			S.pop(); tmp->flag = '\0';
		}
	}
}
void InOrderTraverse_no_recursive(Tree_Node * & root)
{
	stack S;
    Tree_Node * tmp;
	S.push(root);
	while(!S.empty())
	{
		while((tmp = S.top()) && tmp)S.push(tmp->lchild); //      ;
		S.pop();
		if(!S.empty())
		{
			tmp = S.top(); S.pop();
			printf("%c",tmp->str);
			S.push(tmp->rchild);
		}
	}
}

void NextOrderTraverse_no_recursive(Tree_Node * root)
{
	stack S; S.push(root);
	Tree_Node * tmp = NULL;
	while(!S.empty())
	{
		tmp = S.top();
		if(tmp == NULL)S.pop();
		else if(tmp->flag == '\0')
		{
			tmp->flag = 'l';
			S.push(tmp->lchild);
		}
		else if(tmp->flag == 'l')
		{
			tmp->flag = 'r';
			S.push(tmp->rchild);
		}
		else
		{
			printf("%c",tmp->str); tmp->flag = '\0';
			S.pop();
		}
	}
}
int main()
{
	Tree_Node * root;
	build_Tree(root);
	printf("         ：
");
	PreOrderTraverse_recursive(root);
	printf("
");
	printf("          ：
");
	PreOrderTraverse_no_recursive(root);
	printf("
");
	printf("         ：
");
	InOrderTraverse_recursive(root);
	printf("
");
	printf("          ：
");
	InOrderTraverse_no_recursive(root);
	printf("
");
	printf("         ：
");
	NextOrderTraverse_recursive(root);
	printf("
");
	printf("          ：
");
	NextOrderTraverse_no_recursive(root);
	printf("
");
	return 0;
}

PageRankアルゴリズム

VCにおけるCDCとHDCの違いと両者の変換