当前位置:首页 > 开发 > 编程语言 > C/C++ > 正文

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

发表于: 2015-03-18   作者:香煎马鲛鱼   来源:转载   浏览:
摘要: 二叉树的实现 这是我复习的第三部分,二叉树的实现,这次需要的代码比较少,所以把主函数贴出来了,注释也很清晰,所以大家直接看代码吧: //树 #ifndef BINNODE_H #define BINNODE_H template<class Elem> class BinNode{ public: virtual Ele

二叉树的实现

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

//树

#ifndef BINNODE_H

#define BINNODE_H

template<class Elem>

class BinNode{

public:

virtual Elemval() = 0;

virtual void setVal(const Elem&) = 0;

virtual void setValBinNode<Elem>* b) = 0;

virtual BinNodeleft() const = 0;

virtual void setLeft(BinNode*) = 0;

virtual BinNoderight() 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,BinNodePtrl = NULL,BinNodePtrr = NULL){

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

}

~BinNodePtr(){}

Elemval(){

return it;

}

void setVal(const Eleme){

it = e;

}

void setValBinNode<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 == NULLreturn;

visit(subroot);//根

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

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

}

template <class Elem>

//中序

void inorder(BinNode<Elem>* subroot){

if(subroot == NULLreturn;

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

visit(subroot);//根

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

 

}

//后序遍历

template <class Elem>

void backorder(BinNode<Elem>* subroot){

if (subroot == NULLreturn;

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

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

visit(subroot);//根

 

}

template <class Elem>

//左右孩子互换

//我们仍然举一个例子

//          a

//         / \

//        b   c

//       / \   \

//      d   e   f

void swithOrder(BinNode<Elem>* subroot){

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

if(subroot==NULLreturn;

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");

}

 

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

推荐文章
编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号