C++ 二叉树初探

准备面试实习生，也是时候把数据结构与算法拿出来复习了，今天先来个最基础的二叉树创建与遍历。
用的是C＋＋。

先贴出一个二叉树的节点基类

//
// Created by 杰米 on 16/3/14.
//
#ifndef BINODETREE_BINNODE_H
#define BINODETREE_BINNODE_Htemplate 
<typename E> class BinNode {
public:
    virtual  ~BinNode(){}
    virtual  void setElement(const E&)=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 //BINODETREE_BINNODE_H

BSTNode是BinNode的抽象类的简单实现

//
// Created by 杰米 on 16/3/14.
//
#ifndef BINODETREE_BSTNODE_H
#define BINODETREE_BSTNODE_H
#include<iostream>
#include "BinNode.h"
template <typename  Key,typename E>class BSTNode:
 public BinNode<E> {
private:
    Key k;
    E it;
    BSTNode *lc;
    BSTNode *rc;
public:
    BSTNode() {lc = rc = NULL;}
    BSTNode(Key K,E e,BSTNode* l =NULL,BSTNode* r =NULL)    {        k=K;it = e;;lc = l; rc = r;    }
    ~BSTNode(){}
     E & element(){return it;}
     void setElement(const E& e){it = e;}

     Key& key(){ return k;}    void setKey(const Key & K){k=K;}

    inline BSTNode *left() const{ return lc;} 

    void  setLeft(BinNode<E>*b){ lc=(BSTNode*)b;}

    inline BSTNode *right() const{ return rc;}

    void setRight(BinNode<E>*b){ rc = (BSTNode*)b;}

    bool  isLeaf() {return (rc == NULL) && (lc == NULL);}

        };
#endif
 //BINODETREE_BSTNODE_H

下面是main代码，创建二叉树并遍历

#include <iostream>
using namespace std;
#include "BSTNode.h"
//前序遍历
void pre1(BSTNode<int,int >*root){
    if(root==NULL)
    {        return;    }
    else
    {
        cout<<root->key()<<endl;
        pre1(root->left());
        pre1(root->right());
    }}
//中序遍历
void pre2(BSTNode<int,int >*root){
    if(root==NULL)
    {        return;    }
    else
    {        pre2(root->left());
        cout<<root->key()<<endl;
        pre2(root->right());
    }}
//后序遍历
void pre3(BSTNode<int,int >*root)
{    
if(root==NULL)
    {        return;    }
    else
    {
        pre3(root->left());
        pre3(root->right());
        cout<<root->key()<<endl;
    }}
int main() {
    BSTNode<int,int>*root=new BSTNode<int,int>(0,0);
    BSTNode<int,int>*currentNode=root;
//创建一棵二叉树
    for(int i=1;i<5;i++)
    {
        BSTNode<int,int>*left=new BSTNode<int,int>(i,i*10);
        currentNode->setLeft(left);
        BSTNode<int,int>*right=new BSTNode<int,int>(100-i,i*10);
        currentNode->setRight(right);
        currentNode=left;
    }
//遍历
cout<<"前序遍历"<<endl;
pre1(root);
cout<<"中序遍历"<<endl;
pre2(root);
cout<<"后序遍历"<<endl;
pre3(root);
    return 0;
}

创建的二叉树

运行结果