在二叉树中判断是否存在值为x的结点

ゝ一世哀愁。 2023-05-28 15:51 89阅读 0赞

## 在二叉树中判断是否存在值为x的结点 ##

【问题描述】

以二叉链表为存储结构，编写算法判断二叉树中是否存在值为x的结点。

![2020031610300423.png][]

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

【输出形式】如果结点x存在，则输出"YES"；否则输出“NO”。

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

【样例输出】

YES

#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();
    		}
    		void InOrder()
    		{
        
    			InOrder(root);
        	}
        	bool existx(DataType x)
        	{
        
        		return existx(root,x);
    		}
    	private:
    		BiNode<DataType> *Creat();
    		void InOrder(BiNode<DataType> *bt);
    		BiNode<DataType> *root;
    		bool existx(BiNode<DataType> *bt,DataType x);
    };
    
    template<typename DataType>
    bool BiTree<DataType>::existx(BiNode<DataType> *bt,DataType x)
    {
        
    	 if(bt==NULL)  return false;
    	 if(bt->data==x)  return true;
    	 if(existx(bt->lchild,x)) return true;
    	 if(existx(bt->rchild,x)) return true; 
    	 else return false;
    }
    
    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>
    void BiTree<DataType>::InOrder(BiNode<DataType> *bt)
    {
        
    	if(bt)
    	{
        
    		InOrder(bt->lchild);
    		cout<<bt->data;
    		InOrder(bt->rchild);
    	}
    }
    
    int main()
    {
        
    	char x;
    	BiTree<char>  t;
    	cin>>x;
    	if(t.existx(x))  cout<<"YES"<<endl;
    	if(!(t.existx(x)))  cout<<"NO"<<endl;
    }

[2020031610300423.png]: /images/20230528/666a17e046184b649ba8dbc2cd9baf96.png