判断两棵树是相等 最好能用递归算!! 非二叉树!!!! 15
注意不是二叉树!!!!!!不是二叉树!!!!!!不是二叉树!!!!!!我自己想出来了!贴出来public:boolIsEqual(Tree<T>&tree);privat...
注意不是二叉树!!!!!!不是二叉树!!!!!!不是二叉树!!!!!!
我自己想出来了!
贴出来
public:
bool IsEqual(Tree<T> &tree);
private:
bool IsEqual(TreeNode<T> *p,TreeNode<T> *q);
/********************************************************************************************/
template<class T>
bool Tree<T>::IsEqual(Tree<T>& tree)
{
return IsEqual(root,tree.root);
}
template<class T>
bool Tree<T>::IsEqual(TreeNode<T> *p, TreeNode<T> *q)
{
return (p==NULL&&q==NULL)||(p!=NULL&&q!=NULL)&&(p->data==q->data)&&IsEqual(p->child,q->child)&&IsEqual(p->sibling,q->sibling);
}
其他零碎的就不贴了!!!!!!! 展开
我自己想出来了!
贴出来
public:
bool IsEqual(Tree<T> &tree);
private:
bool IsEqual(TreeNode<T> *p,TreeNode<T> *q);
/********************************************************************************************/
template<class T>
bool Tree<T>::IsEqual(Tree<T>& tree)
{
return IsEqual(root,tree.root);
}
template<class T>
bool Tree<T>::IsEqual(TreeNode<T> *p, TreeNode<T> *q)
{
return (p==NULL&&q==NULL)||(p!=NULL&&q!=NULL)&&(p->data==q->data)&&IsEqual(p->child,q->child)&&IsEqual(p->sibling,q->sibling);
}
其他零碎的就不贴了!!!!!!! 展开
2个回答
2011-05-11
展开全部
因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等,而为了研究这类问题,必须能够将树储存,而如何储存将取决于所需要的操作。这里有个问题,是否允许存在空树。有些书认为树都是非空的,因为树表示的是一种现实结构,而0不是自然数;我用过的教科书都是说可以有空树,当然是为了和二叉树统一。这个没有什么原则上的差别,反正就是一种习惯。
二叉树
二叉树可以说是人们假想的一个模型,因此,允许有空的二叉树是无争议的。二叉树是有序的,左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定,是因为人们赋予了左孩子和右孩子不同的意义,在二叉树的各种应用中,你将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书,你会发现一个有趣的现象:在二叉树这里,基本操作有计算树高、各种遍历,就是没有插入、删除——那树是怎么建立起来的?其实这很好理解,对于非线性的树结构,插入删除操作不在一定的法则规定下,是毫无意义的。因此,只有在具体的应用中,才会有插入删除操作。
节点结构
数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲,或者是资源紧张,建议附加一个双亲指针,这将会给很多算法带来方便,尤其是在这个“空间换时间”的时代。
template class T>
struct BTNode
{
BTNode(T data = T(), BTNodeT>* left = NULL, BTNodeT>* right = NULL, BTNodeT>* parent = NULL)
: data(data), left(left), right(right), parent(parent) {}
BTNodeT> *left, *right, *parent;
T data;
};
基本的二叉树类
template class T>
class BTree
{
public:
BTree(BTNodeT> *root = NULL) : root(root) {}
~BTree() { MakeEmpty(); }
void MakeEmpty() { destroy(root); root = NULL; }
protected:
BTNodeT> *root;
private:
void destroy(BTNodeT>* p)
{
if (p)
{
destroy(p->left);
destroy(p->right);
delete p;
}
}
}
二叉树的遍历
基本上有4种遍历方法,先、中、后根,逐层。当初我对这个很迷惑,搞这么多干什么?到了后面才明白,这是不同的应用需要的。例如,判断两个二叉树是否相等,只要子树根节点不同,那么就不等,显然这时要用先序遍历;而删除二叉树,必须先删除左右子树,然后才能删除根节点,这时就要用后序遍历。
实际上,搞这么多遍历方法,根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树,这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性,这些遍历方法能很清晰的表达。
1. 前序遍历......
追问
- -!拷也拷点有用的呀!!!你这是二叉链表 存储结构,我要的是树,应该用孩子兄弟链表的存储结构!!这个问题 我前几天已经想出来了!!!!
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询