您现在的位置:首页 > >

c++自定义二叉树

发布时间:

BinNode.h


#ifndef BINNODE_H_MY
#define BINNODE_H_MY

template
struct BinNode{
T data;
BinNode* parent;
BinNode* lChild;
BinNode* rChild;

BinNode()
: parent(NULL),lChild(NULL),rChild(NULL){}
BinNode(T e, BinNode* p = NULL, BinNode* lc = NULL, BinNode* rc = NULL)
: data(e), parent(p), lChild(lc), rChild(rc){}

BinNode* insertASLC(T const&);//作为左孩子插入
BinNode* insertASRC(T const&);//作为右孩子插入

bool operator==(BinNode const &bn){return data==bn.data;}
bool operator<(BinNode const &bn){return data};

template
BinNode* BinNode::insertASLC(T const& e){
return lChild = new BinNode(e,this);
}

template
BinNode* BinNode::insertASRC(T const& e){
return rChild = new BinNode(e,this);
}
#endif // BINNODE_H_MY

BinTree.h


#ifndef BINTREE_H_MY
#define BINTREE_H_MY
#include "BinNode.h"

template
class BinTree{
protected:
int _size;
BinNode* _root;
public:
BinTree():_root(NULL){}
~BinTree(){if (0 < _size) remove(_root);}
int size() const {return _size;}//用const说明是只读函数
bool empty() const {return !_root;}
BinNode* root() const { return _root;}
BinNode* insertASRoot(T const&);
BinNode* insertASLC(BinNode*, T const&);
BinNode* insertASRC(BinNode*, T const&);
int remove(BinNode*);
void display(BinNode*);

bool operator==(BinTree& other){return _root && other._root && (_root==other._root);}
};

template
BinNode* BinTree::insertASRoot(T const& e){
_size = 1;
return _root=new BinNode(e);
}

template
BinNode* BinTree::insertASLC(BinNode* t, T const& e){
++_size;
t->lChild = new BinNode(e);
if(!t->rChild)
t->rChild = NULL;
return t->lChild;
}

template
BinNode* BinTree::insertASRC(BinNode* t, T const& e){
++_size;
t->rChild = new BinNode(e);
if(!t->lChild)
t->lChild = NULL;
return t->rChild;
}

template
int BinTree::remove(BinNode* t){
return removeAt(t);
}
template
static int removeAt(BinNode* t){
if(!t) return 0;
int n = 1 + removeAt(t->lChild) + removeAt(t->rChild);
delete t;
return n;
}

template
void display(BinNode* t){
if (t==NULL) return;
else{
std::cout << "[";
display(t->lChild);
std::cout << "] " << t->data << " [";
display(t->rChild);
std::cout << "]";
}
}
#endif // BINNODE_H_MY

main.cpp


#include
#include "BinNode.h"
#include "BinTree.h"
using namespace std;

main()
{
BinTree tree;
BinNode *root = tree.insertASRoot(1);
tree.insertASLC(root,2);
BinNode *p = tree.insertASRC(root,3);
p = tree.insertASRC(p,4);
p = tree.insertASRC(p,5);
display(root);
}

output


[[] 2 []] 1 [[] 3 [[] 4 [[] 5 []]]]


热文推荐
猜你喜欢
友情链接: