c数据结构第四章 树

/*1.1 树的定义树Tree是nn≥0个节点的有限集合T它满足两个条件 有且仅有一个特定的称为根Root的节点其余的节点可以分为mm≥0个互不相交的有限集合T1、T2、……、Tm其中每一个集合又是一棵树并称为其根的子树Subtree。树的定义具有递归性即“树中还有树”。1.2 树的概念结点使⽤树结构存储的每一个数据元素都被称为“结点”。例如图中的A就是一个结点。根结点有一个特殊的结点这个结点没有前驱我们将这种结点称之为根结点。⽗结点双亲结点、子结点和兄弟结点对于ABCD四个结点来说A就是BCD的⽗结点也称之为双亲结点。⽽BCD都是A的子结点也称之为孩子结点。对于BCD来说因为他们都有同一个爹所以它们互相称之为兄弟结点。叶子结点如果一个结点没有任何子结点那么此结点就称之为叶子结点。结点的度结点拥有的子树的个数就称之为结点的度。树的度在各个结点当中度的最⼤值。为树的度。树的深度或者⾼度结点的层次从根结点开始定义起根为第一层根的孩子为第二层。依次类推。*/#include “tree.h”#includeint main(){int n;std::cinn;tree run(n);int x; std::cinx; int xirun.find(x); return 0;}#ifndef TREE_H#define TREE_H#include#includetemplateclass tree //双亲表示法,存每个数据的父亲是谁{private:int sum0;int maxx100;struct node{T data;int fa;};node *t(node *)malloc(100*sizeof(node));public:tree(int n);void test();void insert(T a,T b);int find(T fx);int finffather(T x);};class tree2 //孩子表示法存每个孩子的父亲有谁{private:public:};class tree3//兄弟孩子表示法{private:public:};#includetree.hpp#endif#includetree.htemplatevoid tree::test(){std::cout“test good”;}templateint tree ::find(T fx){int i;for(i0;isum-1;i){if(t[i].datafx){break;}}return i;}templatevoid tree::insert(T a,T b){if(summaxx)std::cout“the contain is full and can’t have more data”;t[sum].dataa;t[sum].fa(*this).find(b);sum;}templatetree::tree(int n){if(nmaxx){std::cout“需扩容”std::endl;return;}T root;std::cinroot;t[0].dataroot;t[0].fa-1;sum;for(int i1;in-1;i){T a,b;std::cinab;(*this).insert(a,b);}}templateint tree::finffather(T x){int xifind(x);int fxit[xi].fa;if(fxi-1)std::cout“是根节点”;else return -1;return}