C++程序求二叉树以x为根的子树的深度 最好是能输入二叉树 然后输出树形再输入x
发布网友
发布时间：2023-01-05 08:01
共2个回答
热心网友
时间：2023-10-15 11:37
//
#include <iostream>
#include<stdlib.h>
#include "stdio.h"
template<class T>
struct BTNode
{
T data;
BTNode<T> *lChild,*rChild;
BTNode();
BTNode(const T &val,BTNode<T> *Childl=NULL,BTNode<T> *Childr=NULL)
{
data=val;
lChild=Childl;
rChild=Childr;
}
BTNode<T>* CopyTree()
{
BTNode<T> *nl,*nr,*nn;
if(&data==NULL)
return NULL;
nl=lChild->CopyTree();
nr=rChild->CopyTree();
nn=new BTNode<T>(data,nl,nr);
return nn;
}
};
template<class T>
BTNode<T>::BTNode()
{
lChild=rChild=NULL;
}
template<class T>
class BinaryTree
{
public:
BTNode<T> *root;
BinaryTree();
~BinaryTree();
void Pre_Order();
int TreeDepth(BTNode<T> *r)const;
void DestroyTree();
BTNode<T>* MakeTree(const T &element,BTNode<T> *l,BTNode<T> *r)
{
root=new BTNode<T>(element,l,r);
if(root==NULL)
{
printf("申请存贮地址失败，系统将关闭进程/n");
return NULL ;
}
return root;
}
BinaryTree<T> *cre_tree(char *str,int i,int m);
private:
void Destroy(BTNode<T> *&r);
void PreOrder(BTNode<T> *r);
int Depth(BTNode<T> *r,char x);
int GetDepth(BTNode<T>*bt);
};
template<class T>
BinaryTree<T>::BinaryTree()
{
root=NULL;
}
template<class T>
BinaryTree<T>::~BinaryTree()
{
DestroyTree();
}
template<class T>
void BinaryTree<T>::Pre_Order()
{
PreOrder(root);
}
template<class T>
int BinaryTree<T>::GetDepth(BTNode<T> *bt)
{
int m,n; //记录返回的个数
if(bt) //非空执行
{
m=GetDepth(bt->lChild); //对左子树递归
n=GetDepth(bt->rChild); //对右子树递归
return (m>=n?m+1:n+1); //返回最深的度数
}
else //bt空，返回0
return 0;
}
template<class T>
int BinaryTree<T>::TreeDepth(BTNode<T> *r)const
{
/*
求树的深度的方法有问题,添加一个变量r，表示要求的树的根
*/
if(r==NULL)
return 0;
else
{
int h1=TreeDepth(r->lChild);
int h2=TreeDepth((r->rChild));
int h=(h1>h2 ?h1:h2)+1;
return h;
}
}
template<class T>
void BinaryTree<T>::DestroyTree()
{
Destroy(root);
}
template<class T>
void BinaryTree<T>::PreOrder(BTNode<T> *r)
{
if(r!=NULL)
{
printf("%d",r->data);
printf(" ");
PreOrder(r->lChild);
PreOrder(r->rChild);
}
}
template<class T>
int BinaryTree<T>::Depth(BTNode<T> *r,char x)
{
int m,n;
if(!r) //空，返回0
return 0;
if(r->data==x) //找到r，求r的深度
return GetDepth(r); //返回r的深夜
else
{
if(r->lchild) //向左子树找r
m=Depthx(r->lchild,x);
if(r->rchild) //向右子树找r
n=Depthx(r->rchild,x);
}
return (m>=n?m:n); //返回向下递归的最大深度
}
template<class T>
void BinaryTree<T>::Destroy(BTNode<T> *&r)
{
if(r!=NULL)
{
Destroy(r->lChild);
Destroy(r->rChild);
delete r;
r=NULL;
}
}
/*另外你的maketree貌似也不行，赠上这个建树的,char *里存树节点的字符*/
template<class T>
BinaryTree<T> *BinaryTree<T>::cre_tree(char *str,int i,int m)
{BinaryTree<T> *p;
BinaryNode r;
if(i>=m)
return NULL;
p=(BinaryTree<T> *)malloc(sizeof(bitree)); /生成新节点
r.data=str[i];
p->setRoot(r); //j将第一个节点赋值
p->getRoot()->SetLeft(cre_tree(str,2*i+1,m)); //创建新节点的左子树
p->getRoot()->SetRight(cre_tree(str,2*i+2,m)); //创建新节点右子树
return p;
}
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
char x;
BTNode<char> *b,*c,*d,*e,*f,*g;
BinaryTree<char> a;
b=a.MakeTree('F',NULL,NULL);
c=a.MakeTree('E',NULL,NULL);
d=a.MakeTree('D',NULL,NULL);
e=a.MakeTree('C',b,NULL);
f=a.MakeTree('B',d,c);
g=a.MakeTree('A',f,e);
printf("前序遍历:");
a.Pre_Order();
printf("\n");
printf("x的值是:");
cin>>x;
printf("以x为根的子树的深度是:");
printf("%d",a.TreeDepth(a.root));
cout<<endl;
//如果你不加上using namespace 只能用scanf 和printf
getchar();
getchar();
getchar();
return 0;
}
//这样可以运行了，再有问题再说吧
热心网友
时间：2023-10-15 11:37
