二叉树的实现（c++实现）

先上代码：
头文件

//delete操作暂时还没完全实现 有时间再补上

//
// Created by Hasee on 2021/4/4.
//

#ifndef C__CODE_BASEBINARYTREE_H
#define C__CODE_BASEBINARYTREE_H
using std::cout;
template<class T>
struct BTNode{
    T data;
    BTNode<T>* left;
    BTNode<T>* right;

    BTNode(){
        left= nullptr;
        right= nullptr;
    }

    BTNode(T &item,BTNode<T>*l= nullptr,BTNode<T>*r= nullptr){
        left=l;
        right=r;
        data=item;
    }
};

template<class T>
class Tree{
private:
     BTNode<T>* root;
protected:
    void makeempty(BTNode<T>*ptr);

    BTNode<T>* rlLocate(T node_value,BTNode<T>*ptr);//递归定位要插入的节点

    bool rlDelete(BTNode<T>* ptr,T x=0);

    void rprint(BTNode<T>*ptr);//递归打印

public:
    Tree(){
    root=new BTNode<T>;
}
    Tree(T item){
    root=new BTNode<T>(item);
}
    ~Tree(){
    makeempty(root);
}
    bool Insert(T x,int lr=0,T value=0);
    bool Delete(T del_node_value);

    BTNode<T>* Locate(T value);

    void output();

};

template<class T>
void Tree<T>::makeempty(BTNode<T>*ptr) {
    if(!ptr)return;
    if(ptr->left)makeempty(ptr->left);
    if(ptr->right)makeempty(ptr->right);
    delete ptr;
}

template<class T>
bool Tree<T>::Insert(T x, int lr, T value) {
    if(!Locate(value))return false;
    BTNode<T>* current=rlLocate(value,root);
    if(lr==0){
        if(!current->left)
        {
            current->left=new BTNode<T>(x);return true;
        }
        else  return false;
    } else if(lr==1){
        if(!current->right){
            current->right=new BTNode<T>(x);
            return true;
        } else return false;
    }
    return false;
}

template<class T>
bool Tree<T>::Delete(T del_node_value) {
    if(!rlLocate(del_node_value,root))return false;

    if(rlDelete(root,del_node_value))return true;
    else return false;
}

template<class T>
BTNode<T> *Tree<T>::Locate(T value) {
    return rlLocate(value,root);
}

template<class T>
BTNode<T> *Tree<T>::rlLocate(T node_vaule,BTNode<T> *ptr) {
    if(!ptr)return nullptr;
     if(ptr->data==node_vaule)return ptr;
     BTNode<T>*locate=rlLocate(node_vaule,ptr->left);
     return locate ? locate:rlLocate(node_vaule,ptr->right);
}

template<class T>
bool Tree<T>::rlDelete(BTNode<T> *ptr,T x) {
    if(!ptr)return false;
    if(ptr->data==x) return true;
    if(ptr->left)rlDelete(ptr->left,x);
    if(ptr->right)rlDelete(ptr->right,x);
    return false;
}

template<class T>
void Tree<T>::output() {
    rprint(root);
}

template<class T>
void Tree<T>::rprint(BTNode<T> *ptr) {
    if(!ptr)return;
    if(ptr->left)rprint(ptr->left);
    if(ptr->right)rprint(ptr->right);
    cout<<ptr->data<<"-> "<<" ";
}


#endif //C__CODE_BASEBINARYTREE_H

main函数调用实现插入与输出

#include <iostream>
#include "BaseBinaryTree.h"
int main(){
        Tree<int>test(1);
        test.Insert(2,0,1);
        test.Insert(3,1,1);
        test.Insert(4,0,2);
        test.Insert(5,1,2);
        test.Insert(6,0,3);
        test.Insert(7,1,3);
        test.Insert(7,1,3);//插入不进去

        test.output();
}

实现思想：

使用结构体实现结点的三个基本结构：左右指针域以及数据域；
通过root指针对树进行遍历；
递归的查找节点。

图片显示更直观：

最后

以上就是昏睡糖豆为你收集整理的二叉树的实现（c++实现）的全部内容，希望文章能够帮你解决二叉树的实现（c++实现）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。