二叉树最简单实现（c++）

二叉树的实现

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

//树

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

}