Question

假设二叉树采用二叉链表作为存储结构，试编写一个算法：求任意一个指定结点所在的层次。

【说明】：假设二叉树中无结点值相同的，且要求采用非递归算法。

Answer 1

非递归中序遍历

构造变量count记录当前层访问到的节点数，nextcount记录当前层的总个数；
每当访问过一层层数depth++；
此种方法同时可以求最大宽度，访问第几层的第几个节点，求带权路径长度WPL，是一种通用方法！
int TreeDepth(TreeNode* pRoot)
{
	queueq;
	q.push(pRoot);
	if(pRoot==NULL)return 0;
	TreeNode* p；
	int depth = 0;
	int count = 0;
	int nextcount = 1;
	while(!q.empty())
	{
        count++;
        p = q.front();
        q.pop();
        if(p->left!=NULL)
        {
            q.push(p->left);
        }
        if(p->right!=NULL)
        {
            q.push(p->right);
        }
        if(count==nextcount)
        {
            depth++;
            count=0;
            nextcount=q.size();
        }
	}
	return depth;
}

Answer 2

求其他大神解答

Answer 3

template <class T>
T search(BSTNode<T>* tree, const T& elemt)
{
stack<BSTNode<T>*> travStack;
BSTNode<T> *p = root; //遍历指针
BSTNode<T> *q = root; //层数看守
int num = 1;
If(p != NULL)
travStack.push(p);
while(!travStack.empty())
{
p = travStack.pop();
if(p->data != elemt)
if(p == q)
{
if(q->right != NULL)
{
q = q->right;
}
q = q->left;
num+=1;
}
else
{
cout<<"The number of piles is "<<num<<endl;
break;
}
if(p->left != NULL)
travStack.push(p->left);
if(p->right != NULL)
travStack.push(p->right);
}
}

这个是C++实现的，效率不高。主要运用的是前序遍历的方式,存取方式用的是队列；
思想：设置层数看守,看守始终在该层的最右端；按层次遍历，将该层元素从左向右加入到队列中；找到要求值就停止；

Answer 4

层层遍历咯，只学过单链表，不知道指定节点有什么特征。。。感兴趣的话，咋俩聊聊 说不定就弄出来了