一般化テーブルのツリーの作成

2421 ワード

ツリーの作成には一般的に3つの作成方法があります.ここでは、一般化テーブルを使用してツリーを作成する方法についてのみ説明します.広義の表創樹の方法は、まずルートノードであり、次に左かっこであり、各左かっこに対応する右かっこが対応していることに注意し、息子のノードの作成が終了したことを示す.次に、息子のノードが作成され、カンマごとに別の息子が作成され、各息子は上記のように自分の息子のノードを再帰的に作成します.二叉木の作成は木の作成と全く同じですが、各ノードには最大2人の息子のノードがあります.例えばa(b,c(d,e))は、aが根結点を示し、bが左息子、cが右息子、bが息子結点を示さず、cの左息子がd、右息子がeである.
では、具体的には、作成中に先にツリーを作成する必要があります.これにより、スタックに接続し、父をスタックに圧縮し、スタックの先進的な特徴を利用して先にツリーを作成する必要があります.もちろん、中順序と後順序法でツリーを作成することもできます.ここでは配列シミュレーションスタックを利用する.次に二叉木の凹入法出力二叉木で、同じレベルの結点などの距離出力を特徴とし、息子の結点は父の結点に4つの距離を多く出力するように教えた.先に巡回する方法で出力します.
作成されたコードは次のとおりです.
#include 
#include 
#define Max 100
//#define Low 0
//#ddfine High 1
typedef char type;
typedef enum symbol{Low=0,High=1};
typedef struct Bitree{
	type data;
	struct Bitree *left;
	struct Bitree *right;
}Bitree,*ptree;
ptree Creat_Bitree(char *ch){ //          
	ptree stack[Max];
	ptree p,q=NULL;
	int index=0;
	int top=-1;
    symbol trag;
	while(ch[index]){
		switch(ch[index])
		{
	case '(': 
			top++;
			stack[top]=p;
			trag=Low;
			break;
	case ',':
		    trag=High;
			break;
    case ')':
		    top--;
			break;
	default:
		    p=(ptree)malloc(sizeof(Bitree));
			p->data=ch[index];
			p->left=NULL;
			p->right=NULL;
			if(q==NULL)
				q=p;
			else{
				switch(trag)
				{
			case 0:
					stack[top]->left=p;
					break;
			case 1:
				    stack[top]->right=p;
					break;
				}
			}
		}
		index++;
	}
	return q;
}

void Out_Bitree(ptree p){
	int top=1,width=4,len;
	int level[Max+1][2];
	char ch;
	level[top][0]=3; //  
	level[top][1]=width;//  
	ptree stack[Max+1];
	stack[top]=p;
	ptree q=NULL;
	while(top>0){
		q=stack[top];
		len=level[top][1];
		switch(level[top][0])
		{
		case 1: ch='0';break;
	    case 2: ch='1';break;
        case 3: ch='r';break;
		}
		for(int i=0;idata,ch);
		top--;
		if(q->right!=NULL){
			stack[++top]=q->right;
			level[top][0]=2;
			level[top][1]=len+width;
		}
		if(q->left!=NULL){
			stack[++top]=q->left;
			level[top][0]=1;
			level[top][1]=len+width;
		}
	}
}

int main(){
	char ch[Max];
	ptree p=NULL;
	printf("              n");
	scanf("%s",ch);
	p=Creat_Bitree(ch);
	Out_Bitree(p);
	return 0;
}

テストデータ:
一般表に示すツリーシーケンスA(B,C(D,E))A(r)B(0)C(1)D(0)E(1)Terminated with return code 0 Press any key to continue...