分享
 
 
 

从二叉树和iterator看代码结构设计 (关于adapter的运用)

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

前段时间,论坛上几个人很热烈地讨论二叉树里做iterator。还有人专为此给一些C++界的名人写信,俨然很专业的样子。

老实说,我当时看了这个论题,感觉有点无聊,为什么?因为二叉树就是二叉树,它的结构就是:左儿子,右儿子,父节点等。

iterator的结构是线性的前驱,后继。

两者虽然不是风马牛不相及,但也应该是互相独立的概念。

要给二叉树做一个iterator不是不能,只要定义一个遍历规则,把二叉树以iterator的方式来访问完全是可能的。

但是,这种可能就象拿stl可以做Windows programming一样,但stl和Windows programming却又是互相独立的。 谁也不需要依赖谁。你要非在STL里加入windows sdk的东西,然后说:因为windows programming很常用,所以为了方便用户,我把HWND加入stl, 就乱套了。

把iterator和二叉树的实现耦合起来考虑,在我看来,是明显的设计问题。无谓地把简单的东西复杂化。虽然可以做,但是写出来的代码重用性和结构上都有毛病。

好了,毛病挑完了。下面该说说我认为正确的做法:

1。二叉树就是二叉树, 老老实实地把二叉树的功能做好。不要考虑iterator.

2。 如果认为需要iterator, 如前序,中序,后序。别急。可以单独做一个基于二叉树的iterator的adapter. 这个adapter独立于任何的二叉树实现。它做的只是把二叉树映射成线性访问的iterator.

这个adapter自己定义一个二叉树的接口。然后只需要把任何满足这个接口的对象映射成iterator就成了。

3. 对一个二叉树的实现,怎么利用这个iterator的adapter呢?

把这个二叉树先映射到这个adapter要求的接口。然后,把adapter往二叉树上一套,iterator就出来了。这个iterator库就象一个通用转换器,往任何的二叉树上一插,就行了。

这种结构的好处是,iterator不依赖于二叉树的实现,二叉树也不依赖于iterator. 一个二叉树可以选用任何合适的adapter实现。而一个adapter也可以用于任何的一个二叉树的实现。

下面是我刚刚调试的一段两百多行的C++ bidirectional iterator adapter的代码。它可以用在任何的二叉树实现上(当然,你得写一个adapter把那个二叉树映射到我的二叉树接口上来,不要告诉我你不知道怎么做)

namespace trit{

/*

自己定义的协议语法,二叉树的接口就是这样:

template<typename NODE_PTR>

protocol Tree{

NODE_PTR getLeft();

NODE_PTR getRight();

NODE_PTR getParent();

}

这个是生成的iterator接口:

template<typename NODE_PTR>

protocol Iterator{

operator bool();

NODE_PTR deref();

Self next();

Self prev();

}

*/

template<typename NODE_PTR>

class Iterator{

protected:

typedef Iterator<NODE_PTR> It;

public:

NODE_PTR deref()const{

return node;

}

operator bool()const{

return node!=NODE_PTR(0);

}

Iterator(NODE_PTR const n):node(n){}

friend bool operator==(const It& a, const It& b){

return a.deref()==b.deref();

}

friend bool operator!=(const It& a, const It& b){

return !(a==b);

}

It& operator=(const It& other){

this->node = other.node;

return *this;

}

It end(){

return NODE_PTR(0);

}

static NODE_PTR getRoot(NODE_PTR node){

NODE_PTR ret(node);

NODE_PTR tmp(ret->getParent());

for(;tmp!=NODE_PTR(0);ret=tmp, tmp=ret->getParent());

return ret;

}

static NODE_PTR getLeftmost(NODE_PTR node){

NODE_PTR ret(node);

NODE_PTR tmp(ret->getLeft());

for(;!isNull(tmp);ret=tmp, tmp=ret->getLeft());

return ret;

}

static NODE_PTR getLeftDeep(NODE_PTR node){

NODE_PTR ret(node);

for(;;){

NODE_PTR tmpl(ret->getLeft());

if(isNull(tmpl)){

NODE_PTR tmpr(ret->getRight());

if(isNull(tmpr)){

return ret;

}

else{

ret = tmpr;

}

}

else{

ret = tmpl;

}

}

}

static bool isNull(NODE_PTR ptr){

return ptr==NODE_PTR(0);

}

private:

NODE_PTR node;

};

template<typename NODE_PTR>

class Preorder;

template<typename NODE_PTR>

class Postorder;

template<typename NODE_PTR>

class Inorder;

template<typename NODE_PTR>

class Preorder /*supports Iterator<NODE_PTR>*/: public Iterator<NODE_PTR>{

typedef Preorder<NODE_PTR> Self;

public:

Self next()const{

return goLeft(deref());

}

Self prev()const{

typedef RevTree<NODE_PTR> Adapter;

Adapter rt(deref());

Postorder<Adapter> it(rt);

return Self(it.next().deref().getAdaptee());

}

Self begin()const{

return Self(getRoot(deref()));

}

private:

static Self ret(NODE_PTR me, NODE_PTR from){

if(isNull(me)){

return Self(NODE_PTR(0));

}

else if(from==me->getLeft()){

return goRight(me);

}

else{

return goParent(me);

}

}

static Self goLeft(NODE_PTR const node){

NODE_PTR const left(node->getLeft());

if(isNull(left)){

return goRight(node);

}

else{

return Self(left);

}

}

static Self goRight(NODE_PTR const node){

NODE_PTR const right(node->getRight());

if(isNull(right)){

return goParent(node);

}

else{

return Self(right);

}

}

static Self goParent(NODE_PTR const node){

return ret(node->getParent(), node);

}

public:

Preorder(NODE_PTR const n):It(n){}

Self& operator=(const It& other){

return (Self&) It::operator=(other);

}

};

template<typename NODE_PTR>

class Inorder: public Iterator<NODE_PTR>{

typedef Inorder<NODE_PTR> Self;

public:

Self next()const{

return goRight(deref());

}

Self prev()const{

typedef RevTree<NODE_PTR> Adapter;

Adapter rt(deref());

Inorder<Adapter> it(rt);

return Self(it.next().deref().getAdaptee());

}

Self begin()const{

return Self(getLeftmost(deref()));

}

private:

static Self ret(NODE_PTR const me, NODE_PTR const from){

if(isNull(me)){

return Self(NODE_PTR(0));

}

else if(me->getLeft()==from){

return Self(me);

}

else{

return goParent(me);

}

}

static Self goRight(NODE_PTR const node){

NODE_PTR const right(node->getRight());

if(isNull(right)){

return goParent(node);

}

else{

return Self(getLeftmost(right));

}

}

static Self goParent(NODE_PTR const node){

return ret(node->getParent(), node);

}

public:

Inorder(NODE_PTR const n):It(n){}

Self& operator=(const It& other){

return (Self&) It::operator=(other);

}

};

template<typename NODE_PTR>

class Postorder: public Iterator<NODE_PTR>{

typedef Postorder<NODE_PTR> Self;

public:

Self next(){

return goParent(deref());

}

Self prev(){

typedef RevTree<NODE_PTR> Adapter;

Adapter rt(deref());

Preorder<Adapter> it(rt);

return Self(it.next().deref().getAdaptee());

}

Self begin(){

return Self(getLeftDeep(deref()));

}

static Self ret(NODE_PTR const me, NODE_PTR const from){

if(isNull(me)){

return Self(NODE_PTR(0));

}

if(me->getLeft()==from){

return goRight(me);

}

else{

return Self(me);

}

}

private:

static Self goRight(NODE_PTR const node){

NODE_PTR const right(node->getRight());

if(isNull(right)){

return Self(node);

}

else{

return Self(getLeftDeep(right));

}

}

static Self goParent(NODE_PTR const node){

return ret(node->getParent(), node);

}

public:

Postorder(NODE_PTR const n):It(n){}

Self& operator=(const It& other){

return (Self&) It::operator=(other);

}

};

template<typename NODE_PTR>

class RevTree/*supports Tree<NODE_PTR>*/{

typedef RevTree<NODE_PTR> Self;

public:

RevTree(NODE_PTR const t):tr(t){}

Self getLeft()const{

return Self(tr->getRight());

}

Self getRight()const{

return Self(tr->getLeft());

}

Self getParent()const{

return Self(tr->getParent());

}

const Self* operator->()const {return this;}

bool operator == (const Self& b)const{

return this->tr==b.tr;

}

bool operator== (const NODE_PTR b){

return this->tr==b;

}

friend bool operator== (const NODE_PTR a, const Self& b){

return a==b.tr;

}

Self& operator=(const Self& other){

tr = other.tr;

return *this;

}

NODE_PTR getAdaptee()const{return tr;}

private:

NODE_PTR tr;

};

}

下面是测试代码,因为这里的重点不是如何实现二叉树, 它使用了一个非常简易的二叉树。只是为了表示你怎么样给一个任意的二叉树提供iterator服务。

#include <iostream.h>

#include "trit.h"

using namespace trit;

class TreeCons{

public:

TreeCons* getLeft()const{return left;}

TreeCons* getRight()const{return right;}

TreeCons* getParent()const{return parent;}

void setParent(TreeCons* p){this->parent = p;}

const char* get(){return val;}

TreeCons(TreeCons* l, TreeCons* r, const char* v)

:left(l), right(r), parent(0), val(v){}

private:

TreeCons* left;

TreeCons* right;

TreeCons* parent;

const char* val;

};

typedef Preorder<TreeCons*> Pre;

typedef Inorder<TreeCons*> In;

typedef Postorder<TreeCons*> Post;

template<typename IT>

void printIt(IT it){

for(;it; it=it.next()){

cout << it.deref()->get();

}

cout <<endl;

}

template<typename IT>

void printRev(IT it){

for(;it; it=it.prev()){

cout << it.deref()->get();

}

cout <<endl;

}

int main(){

TreeCons* d = new TreeCons(0, 0, "D");

TreeCons* e = new TreeCons(0, 0, "E");

TreeCons* b = new TreeCons(d, e, "B");

d->setParent(b);

e->setParent(b);

TreeCons* f = new TreeCons(0, 0, "F");

TreeCons* c = new TreeCons(0, f, "C");

f->setParent(c);

TreeCons* a = new TreeCons(b, c, "A");

b->setParent(a);

c->setParent(a);

printIt(Pre(a));

printIt(Pre(c).begin());

printIt(In(a));

printIt(In(a).begin());

printIt(Post(a));

printIt(Post(a).begin());

printRev(Post(a));

printRev(In(a));

printRev(Pre(a));

delete a;

delete b;

delete c;

delete d;

delete e;

return 1;

}

也许你会觉得,这个iterator和stl的iterator的接口不大一致。呵呵,这个实现本着最小功能原则,其它的如operator++什么的,自己写个小adapter把接口转换一下应该不难吧?

:〉

另外,我还写了一个Java版本的binary tree -- iterator 的adapter. 利用java的gc功能, 它不需要节点有父指针。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有