一般化テーブルのツリーの作成
2421 ワード
ツリーの作成には一般的に3つの作成方法があります.ここでは、一般化テーブルを使用してツリーを作成する方法についてのみ説明します.広義の表創樹の方法は、まずルートノードであり、次に左かっこであり、各左かっこに対応する右かっこが対応していることに注意し、息子のノードの作成が終了したことを示す.次に、息子のノードが作成され、カンマごとに別の息子が作成され、各息子は上記のように自分の息子のノードを再帰的に作成します.二叉木の作成は木の作成と全く同じですが、各ノードには最大2人の息子のノードがあります.例えばa(b,c(d,e))は、aが根結点を示し、bが左息子、cが右息子、bが息子結点を示さず、cの左息子がd、右息子がeである.
では、具体的には、作成中に先にツリーを作成する必要があります.これにより、スタックに接続し、父をスタックに圧縮し、スタックの先進的な特徴を利用して先にツリーを作成する必要があります.もちろん、中順序と後順序法でツリーを作成することもできます.ここでは配列シミュレーションスタックを利用する.次に二叉木の凹入法出力二叉木で、同じレベルの結点などの距離出力を特徴とし、息子の結点は父の結点に4つの距離を多く出力するように教えた.先に巡回する方法で出力します.
作成されたコードは次のとおりです.
テストデータ:
一般表に示すツリーシーケンス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...
では、具体的には、作成中に先にツリーを作成する必要があります.これにより、スタックに接続し、父をスタックに圧縮し、スタックの先進的な特徴を利用して先にツリーを作成する必要があります.もちろん、中順序と後順序法でツリーを作成することもできます.ここでは配列シミュレーションスタックを利用する.次に二叉木の凹入法出力二叉木で、同じレベルの結点などの距離出力を特徴とし、息子の結点は父の結点に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...