二叉树最简单实现(c++)_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 二叉树最简单实现(c++)

二叉树最简单实现(c++)

 2015/3/19 4:55:27  香煎马鲛鱼  程序员俱乐部  我要评论(0)
  • 摘要:二叉树的实现这是我复习的第三部分,二叉树的实现,这次需要的代码比较少,所以把主函数贴出来了,注释也很清晰,所以大家直接看代码吧://树#ifndefBINNODE_H#defineBINNODE_Htemplate<classElem>classBinNode{public:virtualElem&val()=0;virtualvoidsetVal(constElem&)=0;virtualvoidsetVal(BinNode<Elem>*b)=0
  • 标签:实现 c++ 二叉树

class="MsoNormal">hashu.html" target="_blank">二叉树的实现

这是我复习的第三部分,二叉树的实现,这次需要的代码比较少,所以把主函数贴出来了,注释也很清晰,所以大家直接看代码吧:

//树

#ifndef?BINNODE_H

#define?BINNODE_H

template<class?Elem>

class?BinNode{

public:

virtual?Elem&?val()?=?0;

virtual?void?setVal(const?Elem&)?=?0;

virtual?void?setVal(?BinNode<Elem>*?b)?=?0;

virtual?BinNode*?left()?const?=?0;

virtual?void?setLeft(BinNode*)?=?0;

virtual?BinNode*?right()?const?=?0;

virtual?void?setRight(BinNode*)?=?0;

virtual?bool?isLeaf()?=?0;

};

#endif

?

//建树操作

#ifndef?BINNODEPTR_H

#define?BINNODEPTR_H

#include?"BinNode.h"

template?<class?Elem>

class?BinNodePtr:public?BinNode<Elem>{

private:

Elem?it;

BinNodePtr*?lc;

BinNodePtr*?rc;

public:

BinNodePtr(){lc?=?rc?=?NULL;}

BinNodePtr(Elem?e,BinNodePtr*?l?=?NULL,BinNodePtr*?r?=?NULL){

it?=?e;?lc?=?l;?rc?=?r;

}

~BinNodePtr(){}

Elem&?val(){

return?it;

}

void?setVal(const?Elem&?e){

it?=?e;

}

void?setVal(?BinNode<Elem>*?b){

?

}

inline?BinNode<Elem>*?left()const{return?lc;}

void?setLeft(BinNode<Elem>*?b){lc?=?(BinNodePtr*)b;}

????inline?BinNode<Elem>*?right()const{return?rc;}

void?setRight(BinNode<Elem>*?b){rc?=?(BinNodePtr*)b;}

bool?isLeaf(){

return?(lc==NULL)&&(rc==NULL);

}

};

#endif?BINNODEPTR_H

?

?

//树,这里实现了树的几种方法

//

//(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根?-?左?-?右。

//

//(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左?-?根?-?右。

//

//(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左?-?右?-?根。

#include<iostream>

using?namespace?std;

#include"BinNode.h"

#include"BinNodePtr.h"

template?<class?Elem>

//建树

//??????????a

//?????????/?\

//????????b???c

//???????/?\???\

//??????d???e???f

//建立此二叉树的方法为:(abd??e??c?f??)

BinNode<Elem>*?CreateBinTree(){

BinNode<Elem>*?t;

char?ch;

if?((ch?=?getchar())?==?'?')

{

//如果是空格表示空,后面没有节点了;

return?NULL;

}

else

{

//输入值

t?=?new?BinNodePtr<Elem>(ch);

//左孩子

t->setLeft(CreateBinTree<Elem>());

//右孩子

t->setRight(CreateBinTree<Elem>());

}

return?t;

}

template?<class?Elem>

//复制该树

BinNode<Elem>*?CopyBinTree(BinNode<Elem>*?p){

BinNode<Elem>*?t;

t=?new?BinNodePtr();

t->setVal(p->val());

if?(t->val()==NULL)return?NULL;

else

{

t->setLeft(CopyBinTree<Elem>(p->left()));

t->setRight(CopyBinTree<Elem>(p->right()));

}

return?t;

}

template?<class?Elem>

//输出单个节点

void?visit(BinNode<Elem>*?subroot){

cout<<subroot->val();

}

template?<class?Elem>

//前序

void?preorder(BinNode<Elem>*?subroot){

if(subroot?==?NULL)?return;

visit(subroot);//根

preorder(subroot->left());//左

preorder(subroot->right());//右

}

template?<class?Elem>

//中序

void?inorder(BinNode<Elem>*?subroot){

if(subroot?==?NULL)?return;

inorder(subroot->left());//左

visit(subroot);//根

inorder(subroot->right());//右

?

}

//后序遍历

template?<class?Elem>

void?backorder(BinNode<Elem>*?subroot){

if?(subroot?==?NULL)?return;

backorder(subroot->left());//左

backorder(subroot->right());//右

visit(subroot);//根

?

}

template?<class?Elem>

//左右孩子互换

//我们仍然举一个例子

//??????????a

//?????????/?\

//????????b???c

//???????/?\???\

//??????d???e???f

void?swithOrder(BinNode<Elem>*?subroot){

//如果要置换的树是空的,结束

if(subroot==NULL)?return;

visit(subroot);

//声明一个空间,用来临时存放节点

BinNode<Elem>*?t;

char?ch='?';

t?=?new?BinNodePtr<Elem>(ch);

//t临时存放右边节点

//??????????a

//?????????/?\

//????????b???c

//???????/?\???\

//??????d???e???f

//t?=?b{d?e}

t=subroot->left();

//用右边的节点覆盖左边节点

//??????????a

//?????????/?\

//????????c???c

//?????????\???\

//??????????f???f

//t?=?b{d?e}

subroot->setLeft(subroot->right());

//把t付给右边节点

//??????????a

//????????/???\

//???????c?????b

//????????\????/\

//?????????f??d??e?

subroot->setRight(t);

//递归,最终结果为

//??????????a

//????????/???\

//???????c?????b

//??????/??????/\

//?????f??????e??d?

swithOrder(subroot->left());

swithOrder(subroot->right());

}

int?main(){

cout?<<?"请输入:abd(空格)(空格)e(空格)(空格)c(空格)f(空格)(空格)(回车)"?<<?endl;

BinNode<char>*?tree;

tree?=?CreateBinTree<char>();

inorder<char>(tree);

cout<<endl;

swithOrder<char>(tree);

????cout<<endl;

inorder<char>(tree);

cout?<<?endl;

backorder<char>(tree);

????cout<<endl;

system("pause");

}

?

  • TREES-1.rar (1.8 KB)
  • 下载次数: 0
上一篇: ReSharper 文件注释 下一篇: 没有下一篇了!
发表评论
用户名: 匿名