データ構造研究ノート（3）ツリー構造の一般的な二分木の順次ストレージ_binaryリンクリストrepresentation_conversion

Data Structure Study Notes Sequential Storage General Binary Tree Tree Structure_binary Linked List Representation_conversion

以下は、一般的なバイナリツリーのシーケンシャルストレージ表現からバイナリリンクリスト表現への変換であり、最後に、プレオーダートラバーサルの方法で出力されたコードです。

//General binary tree sequential storage notation to binary linked list notation conversion #include using namespace std //Abstract data type-variable definition and variable description const char MaxSize=10 typedef int datatype typedef struct node { datatype data struct node *lchild,*rchild }BTnode,*BinTree typedef struct elem { datatype data int lchild,rchild//-1 means empty int tag//The flag of whether the corresponding node is generated, the initial state is 0, and it is 1 after generation BTnode *link//Store node address, initial state is NULL }element element A[MaxSize] //The binary tree represented by the initialization sequence storage notation void Initialize() { A[0]={'A',1,6,0,NULL} A[1]={'B',2,3,0,NULL} A[2]={'D',-1,-1,0,NULL} A[3]={'E',4,5,0,NULL} A[4]={'H',-1,-1,0,NULL} A[5]={'I',-1,-1,0,NULL} A[6]={'C',7,9,0,NULL} A[7]={'F',-1,8,0,NULL} A[8]={'J',-1,-1,0,NULL} A[9]={'G',-1,-1,0,NULL} } //Transformation function y void Exchange(element* A,BinTree &root) { for(int i=0iif(A[i].tag==0) { A[i].link=p A[i].tag=1 p->data=A[i].data } else p=A[i].link if(A[i].lchild!=-1) { int j=A[i].lchild BTnode *pl=new BTnode A[j].link=pl A[j].tag=1 pl->data=A[j].data p->lchild=pl } else p->lchild=NULL if(A[i].rchild!=-1) { int j=A[i].rchild BTnode *pr=new BTnode A[j].link=pr A[j].tag=1 pr->data=A[j].data p->rchild=pr } else p->rchild=NULL } root=A[0].link } //Use recursion for preorder traversal output void preOrder(BinTree &root) { BTnode *p=root if(p!=NULL) { cout<<char(p->data)<<' ' preOrder(p->lchild) preOrder(p->rchild) } } //Test function int main() { BinTree root Initialize() Exchange(A,root) cout<<'Preorder traversal output converted binary tree:'<return 0 }