BJFU_数据结构习题_290基于非递归的二叉排序树的结点的查找和插入

柔情只为你懂 2023-06-16 12:57 3阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 290基于非递归的二叉排序树的结点的查找和插入 ###

**描述**  
已知二叉树T的结点形式为(llink,data,count,rlink)，在树中查找值为x的结点，若找到，则计数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树。请写出其非递归算法。  
**输入**  
多组数据，每组数据3行。第一行为二叉排序树的结点数n，第二行为空格分隔的n个数字，对应二叉排序树中的n个结点，第三行为查找的值x。n=0时输入结束。  
**输出**  
每组数据输出两行。第一行为二叉排序树的中序序列（空格分隔），第二行为其对应的计数count。  
**输入样例 1**  
5  
1 2 3 4 5  
3  
6  
1 3 4 5 6 7  
2  
0  
**输出样例 1**  
1 2 3 4 5  
0 0 1 0 0  
1 2 3 4 5 6 7  
0 0 0 0 0 0 0

OJ对于输出很严格，除了最后一个数据后面是回车，其他都是空格，这就是为什么我代码中需要用number来计数

#include<iostream>
    using namespace std;
    int number;									//设一个全局变量是为了帮我判断该数据是否为输出的最后一个数
    typedef struct BiTNode
    {
        
    	int data;
    	int count;
    	struct BiTNode *llink;
    	struct BiTNode *rlink;
    }BiTNode,*BiTree;
    void aInOrderTraverse(BiTree T,int &N)		//输出所有结点的data
    {
        
    	if(T)
    	{
        
    		aInOrderTraverse(T->llink,N);
    		cout<<T->data;
    		if(++number<N)						//不是最后一个数据，则数据后面输出空格
    			cout<<" ";
    		else								//是最后一个数据，则数据后面输出回车
    			cout<<endl;
    		aInOrderTraverse(T->rlink,N);
    	}
    }
    void bInOrderTraverse(BiTree T,int &N)		//输出所有结点的count
    {
        
    	if(T)
    	{
        
    		bInOrderTraverse(T->llink,N);
    		cout<<T->count;
    		if(++number<N)						//不是最后一个数据，则数据后面输出空格
    			cout<<" ";
    		else
    			cout<<endl;						//是最后一个数据，则数据后面输出回车
    		bInOrderTraverse(T->rlink,N);
    	}
    }
    void SearchBST(BiTree &T,int key,int &N)
    {
        
    	BiTree s=new BiTNode;					//生成新结点
    	s->data=key;
    	s->count=0;
    	s->llink=NULL;
    	s->rlink=NULL;
    	if(!T)									//树为空则该结点就是根节点
    	{
        
    		T=s;
    		return;
    	}
    	BiTree q=T,p;						
    	while(q)								//从根节点开始比较，直到结点为空
    	{
        
    		if(q->data==key)					//若查找的结点存在
    		{
        
    			q->count++;
    			return;							//函数直接结束
    		}
    		p=q;								//如果没有找到，用p结点保留q结点，q最后一个非NULL结点是key的父结点（而q为NULL才能跳出循环，所以用p保留q非NULL的结点）
    		if(q->data>key)						//结点data大于key，则key再跟左子结点比较
    			q=q->llink;
    		else 								//结点data小于key，则key再跟右子结点比较
    			q=q->rlink;
    	}
    	if(p->data>key)							//p是父结点
    	{
        
    		N++;								
    		p->llink=s;	
    	}
    	else
    	{
        
    		N++;
    		p->rlink=s;
    	}
    }
    int main()
    {
        
    	int n;
    	while(cin>>n&&n!=0)
    	{
        
    		int N=1,S[100];
    	  	BiTree T=NULL;	
    		for(int j=0;j<n;j++)
    		{
        	
    			cin>>S[j];
    			SearchBST(T,S[j],N);
    		}
    		int key;
    		cin>>key;
    		SearchBST(T,key,N);
    		number=0;				//从0开始计数
    		aInOrderTraverse(T,N);
    		number=0;				//从0开始计数
    		bInOrderTraverse(T,N);
    	}
    	return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com