二叉木の深さを求めて、再帰と非再帰のアルゴリズム
871 ワード
再帰アルゴリズム:
非再帰アルゴリズム:
int FindTreeDeep(BiTree BT){
int treeDeep=0;
if(BT){
int lchild=FindTreeDeep(BT->lchild);
int rchild=FindTreeDeep(BT->rchild);
treeDeep=lchild>=rchild?lchild+1:rchild+1;
}
return treeDeep;
}
非再帰アルゴリズム:
// ,
void PostOrderTraverse(const BiTree T){
int treeDepth = 0; //
vector t_vTree;
BiTree p=T;
BiTree have_visited=NULL; //
while (p || !t_vTree.empty())
{
if (p){
t_vTree.push_back(p);
p = p->lchild;
}
else{
p = t_vTree.back(); // P ,
if (p->rchild==NULL ||p->rchild==have_visited)
{
// ,
treeDepth = treeDepthrchild;
}
} //while
cout<