如何高效地求二叉树中结点所在层数

Question

c++，或者直接说思想，注意不是二叉搜索树！！
请分析算法的时空复杂度

Answer 1

#define M 10 //假设二叉树最多的层数
BinTree SearchBTree(BinTree *T,DataType x)
{//以前序遍历算法查找值为x的结点
if(*T)
{
if((*T)->data==x )return *T;
SearchBTree(&(*T)->lchild,x);
SearchBTree(&(*T)->rchild,x);
}
}

int InLevel(BinTree T,DataType x)
{
int static l=0;//设一静态变量保存层数
if(T)
{
if(l==0)//若是访问根结点
{
l++;//第1层
if(T->data==x)return l;
if(T->lchild||T->rchild)
l++;//若根有子树，则层数加1
}
else
{ //访问子树结点
if(T->data==x)return l;
if(T->lchild||T->rchild)
l++;//若该结点有子树，则层数加1
else return 0;
}
InLevel(T->lchild,x);//遍历左子树
InLevel(T->rchild,x);//遍历右子树
}
}

Answer 2

如果您的算法需求是要方便的确定某个给定的结点所在的层次，那就用父亲孩子结构存储二叉树好了，这样从一个指定结点位置找到自己所在的层次，最多O（n）即可确定自己的层次，若二叉树是平衡二叉树等则O（logn）即可确定自己的层次本回答被网友采纳

Answer 3

log^2^n+1
以2为底1n为真数10的对数再加一，代表结点数，这是满二叉树求层数的公式。