求二叉树中值为x的结点的层号

男娘i 2023-07-15 09:12 18阅读 0赞

## 求二叉树中值为x的结点的层号 ##

【问题描述】

以二叉链表为存储结构，编写算法求二叉树中值为x的结点的层号。

![20200316102740267.png][]

【输入形式】两行，第一行是扩展二叉树的前序遍历序列，第二行是待查询结点x

【输出形式】值为x的结点所在层号。根结点所在层记为第1层。

【样例输入】AB\#D\#\#C\#\#

【样例输出】

#include<iostream>
    using namespace std;
    template<typename DataType>
    
    struct BiNode
    {
        
    	DataType data;
    	BiNode<DataType> *lchild,*rchild;
    };
    
    template <typename DataType>
    class BiTree
    {
        
    	public:
    		BiTree()
    		{
        
    			root=Creat();
    		}
    		int levelnum(DataType x){
        
    			return levelnum(root,1,x);
    		}
    		
    	private:
    		BiNode<DataType> *Creat();
    		BiNode<DataType> *root;
    		int levelnum(BiNode<DataType> *bt,int level,DataType x);
    };
    
    
    
    template<typename DataType>
    BiNode<DataType> *BiTree<DataType>::Creat()
    {
        
    	BiNode<DataType> *bt;
    	char ch;
    	cin>>ch;
    	if(ch=='#')  bt=NULL;
    	else
    	{
        
    		bt=new BiNode<DataType>;
    		bt->data=ch;
    		bt->lchild=Creat();
    		bt->rchild=Creat();
    	}
    	return bt;
    }
    
    template<typename DataType>
    int BiTree<DataType>::levelnum(BiNode<DataType> *bt,int level,DataType x)
    {
        
    	if(bt==NULL)  return 0;
    	if(bt->data==x)  return level;
    	if(bt->lchild!=NULL)
    		  levelnum(bt->lchild,level+1,x);
    	if(bt->rchild!=NULL)
    		  levelnum(bt->rchild,level+1,x);
    }
    
    int main()
    {
        
    	char x;
    	BiTree<char> t;
    	cin>>x;
    	cout<<t.levelnum(x)<<endl;
    }

[20200316102740267.png]: /images/20230528/fc0fc5645a9d48718beb727bcb076762.png