递归求解二叉树任意一结点的深度

心已赠人 2022-08-14 02:45 56阅读 0赞

这个事最后一道大题的第一小题

让写个递归算法求解二叉树任意一结点的深度

首先应该去递归找到这个x结点，找到后然后再递归求解以x为根结点的子树的深度，所以我就很规矩(当然我觉得这样写比较明了)写了两个递归函数

当然首先还是得建立二叉排序树

另外注明：是用vs2010写的，没有在vc++6.0上面测试，如果朋友们发现在vc++上有bug，欢迎指出，供后来者看看

贴下自己的代码

//功能：递归算法，求二叉树中以元素值为x的结点为根的子树的深度
    //时间：2014-11-23
    
    #include <iostream>
    using namespace std;
    
    //二叉链表数据结构定义
    #define TElemType int
    typedef struct BiTNode{
    	TElemType data;
    	struct BiTNode *lchild, *rchild;
    }*BiTree;
    
    //定义树的根节点
    BiTree root=NULL;
    
    //根据输入的序列建立一颗二叉排序树(Binary Sort Tree)，它的中序遍历是有序的
    void CreatBST(const int &a)
    {
    	BiTree p,q,s;
    	//分配结点s的内存空间
    	s=(BiTree)malloc(sizeof(BiTNode));
    	//将插入的值a赋值给s结点,并初始化左右孩子
    	s->data=a;
    	s->lchild=NULL;
    	s->rchild=NULL;
    	//判断根节点是否为空
    	if(root==NULL)
    	{//为空
    		root=s;
    		return;
    	}else{
    		//不为空
    		p=root;
    		while(p)
    		{
    			//保存p指针
    			q=p;
    			if(p->data==a)
    			{
    				cout << "该结点已经存在，请重新输入"<<endl;
    				return;
    			}else if(p->data>a){
    				//指向左孩子
    				p=p->lchild;
    			}else{
    				//指向右孩子
    				p=p->rchild;
    			}
    		}
    		//插入s结点
    		if(s->data>q->data)
    			q->rchild=s;
    		else
    			q->lchild=s;
    	}
    }
    //求以T为根节点二叉树的深度
    int GetDepth(const BiTree &T)
    {
    	//定义以T为根节点的左子树和右子树的深度
    	int rHeight,lHeight;
    	//判断T是否为空
    	if(T)
    	{
    		//递归获取左子树的深度
    		lHeight=GetDepth(T->lchild);
    		//递归获取右子树的深度
    		rHeight=GetDepth(T->rchild);
    		return (lHeight>rHeight? lHeight:rHeight)+1;
    	}else{
    		return 0;
    	}
    
    }
    //以元素值为x的节点为根的子树深度
    int GetSubDepth(const BiTree &T , const TElemType &x)
    {
    	//判断T是否为空
    	if(T)
    	{
    		//当节点的值为x时，直接返回求以x为根节点的深度
    		if(T->data==x)
    		{
    			//输出以x为根结点的深度
    			cout<< "以元素值为"<< x << "的结点为根的子树的深度为： " << GetDepth(T) << endl;
    			//退出函数
    			exit(0);
    		}else{
    			//递归遍历左子树找x结点
    			if(T->lchild)
    				GetSubDepth(T->lchild,x);
    			//递归遍历右子树找x结点
    			if(T->rchild)
    				GetSubDepth(T->rchild,x);
    		}
    	}else{
    		return 0;
    	}
    }
    //主函数
    int main()
    {
    	int x;
    	//输入要建立二叉树的序列
    	while(1)
    	{
    		cout << "请输入要建立二叉树的结点数据(不要重复，以-1结束):  ";
    		cin >> x;
    		if(x==-1)
    			break;
    		//插入二叉树
    		CreatBST(x);
    	}
    	cout <<"请输入所求深度的根结点值x:  ";
    	cin >> x;
    	//获取以x为根节点的子树深度
    	GetSubDepth(root,x);
    	return 0;
    }