看别人写
键树代码看不懂
就自己写了
个
博客刚开通就当开个张贴份代码上来要下班了改天再重新把注释说详细点顺便把树过程补上#
#using
std;/*
树结构用是左孩子-右兄弟所以定义了移动方向*/#
CHILD1#SIBLING2#NOMOVE3/**树结点左孩子-右兄弟表示法*把成员都做成public了主要是演示下算法www. //test.cpp:Definestheentrypo
fortheconsoleapplication. //
#
\"stdafx.h\" #
<iostream> #
<queue> using
std; /*
themovementdirection*/ #
CHILD1 #
SIBLING2 #
NOMOVE3 /*
*keywordtreenode
*weuseastructureleftchild-rightsibling
*tostorethetree’snodes
*/
knode {
public:
knode
{
c=0;
child=NULL;
sibling=NULL;
}
knode(
cc,knode*pc,knode*ps) {
c=cc;
child=pc;
sibling=ps;
}
charc;
knode*child;
knode*sibling;
};
/*
*insertpatterntokeywordtree
*rootiskeywordtree’srootnode
*stristhe
insertedtothetree */
voidinsertKTree(knode*constroot,char*str)
{
knode*troot=root;
knode*tproot=root;/*savethepreviousnodewhenmove
hetree*/ troot=root->child;
moveDir=NOMOVE; /*
findthematchedportionofsub
instrassoonaspossiable, meanwhile,movethepo
erstr. */
while(troot!=NULL)
{
(troot->c
*str) [Page]{
str
; tproot=troot;
troot=troot->child;
moveDir=CHILD;/*movetochild*/
}
{
tproot=troot;
troot=troot->sibling;
moveDir=SIBLING;/*movetosibling*/
}
}
/*readytoinserttherest
poedtobystrothetree*/ switch(moveDir)
{
NOMOVE:/*treeonlyhasanode(rootnode)*/ CHILD:/*insertnodeaschild*/ while(*str!=’\\0’)
{
tproot->child=
knode(*str,NULL,NULL); tproot=tproot->child;
str
; }
; SIBLING:/*insertnodeassiblingfirst,andtheninsertnodeaschildforallrestcharacters*/ tproot->sibling=
knode(*str,NULL,NULL); str
; tproot=tproot->sibling;
while(*str!=’\\0’)
{
tproot->child=
knode(*str,NULL,NULL); [Page]tproot=tproot->child;
str
; }
; default:/*thebranchisnotreachable*/
; }
}
/*
*pr
allnodesofthetreeinlevelorder */
voidpr
KTree(knode*root) {
queue<knode>Q;
knodetnode;
tnode=*root;
Q.push(tnode);
cout<<\"charis\"<<tnode.c;
/*visittreeinlevelorder*/
while(!Q.empty
) {
/*retrivethefirstnodefromqueue*/
tnode=Q.front
; cout<<\"charis\"<<tnode.c;
Q.pop
; /*pushalltnode’schild
oqueue*/ (tnode.child!=NULL) {
Q.push(*(tnode.child));/*addfirstchild*/
tnode=*(tnode.child);
/*addtherestchild*/
while(tnode.sibling!=NULL)
{
Q.push(*(tnode.sibling));
tnode=*(tnode.sibling); [Page]
}
}
cout<<endl;
}
}
(argc,char*argv
) {
knoderoot;
root.c=-1;
root.child=NULL;
root.sibling=NULL;
char*str1=\"abc\";
char*str2=\"abd\";
char*str3=\"ac\";
char*str4=\"mn\";
insertKTree(&root,str1);
insertKTree(&root,str2);
insertKTree(&root,str3);
insertKTree(&root,str4);
pr
KTree(&root); pr
f(\"HelloWorld!\\n\"); 
0; }
最新评论