C++二叉查找树实现及转化为双向链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++二叉查找树实现及转化为双向链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5929字，纯文字阅读大概需要9分钟。

内容图文

二叉树首先要有树节点

template<class T>
class BinaryNode
{
public:
    T element;
    BinaryNode *left;
    BinaryNode *right;

public:
    BinaryNode(T passelement);
    ~BinaryNode();
};

template<class T>
BinaryNode<T>::BinaryNode(T passelement)
{
    this->element=passelement;
    this->left=NULL;
    this->right=NULL;
}

template<class T>
BinaryNode<T>::~BinaryNode()
{
}

二叉树对象则比较复杂

 template<class T>
class BinarySearchTree
{
private:
    BinaryNode<T> *m_proot;
public:
    const T findMin() const;//获取最小值const T findMax() const;//获取最大值bool contains(const T& xele) const;//判断是否包含void makeEmpty();//清空二叉树void insert(const T& xele);//插入void remove(const T& xele);//删除void inordertrav();//中序遍历void toDoublelist();//转化为双向链表void printDoublelist();//打印双向链表public://构造与析构函数    BinarySearchTree();
    BinarySearchTree(const BinarySearchTree& bst);
    ~BinarySearchTree();
private://全部用于递归调用void makeEmpty(BinaryNode<T>* &t);
    const T findMin(BinaryNode<T>* &t);
    void remove(const T& xele, BinaryNode<T>* &t);
    void insert(const T& xele, BinaryNode<T>* &t);
    void inordertrav(BinaryNode<T>* &t);
    void toDoublelist(BinaryNode<T>* &t);
    BinaryNode<T>* getlLeftTail(BinaryNode<T>* &t);//获取左子树的最大节点
    BinaryNode<T>* getlRightHead(BinaryNode<T>* &t);//获取右子树的最小节点
};

具体函数实现如下：

1.判断是否包含：

template<class T>
bool BinarySearchTree<T>::contains(const T& xele) const
{
    BinaryNode<T>* pcurrent = m_proot;
    while (true)
    {
        if (pcurrent == NULL)//指针为空        {
            returnfalse;
        }
        elseif (xele < pcurrent->element)
            pcurrent = pcurrent->left;
        elseif (xele > pcurrent->element)
            pcurrent = pcurrent->right;
        else
        {
            pcurrent = NULL;
            returntrue;
        }
    }

}

2.返回最小值：

template<class T>
const T BinarySearchTree<T>::findMin() const
{
    BinaryNode<T>* m_pcurrent = m_proot;
    while (m_pcurrent->left != NULL)
    {
        m_pcurrent = m_pcurrent->left;
    }
    return m_pcurrent->element;
}

或：

template<class T>
const T BinarySearchTree<T>::findMin(BinaryNode<T>* &t)
{
    if (t == NULL)
        return NULL;
    if (t->left == NULL)
        return t->element;
    elsereturn findMin(t->left);

}
template<class T>
const T BinarySearchTree<T>::findMin()
{
       findMin(m_proot);
}

3.返回最大值：

template<class T>
const T BinarySearchTree<T>::findMax() const
{
    BinaryNode<T>* m_pcurrent = m_proot;
    while (m_pcurrent->right != NULL)
    {
        m_pcurrent = m_pcurrent->right;
    }
    return m_pcurrent->element;
}

4.清空：

template<class T>
void  BinarySearchTree<T>::makeEmpty(BinaryNode<T>* &t)
{
    if (t!=NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t = NULL;
}
template<class T>
void BinarySearchTree<T>::makeEmpty()
{
    makeEmpty(m_proot);
}

5.插入：

template<class T>
void BinarySearchTree<T>::insert(const T& xele, BinaryNode<T>* &t)
{
    if (t == NULL)
        t = new BinaryNode<T>(xele);
    elseif (xele < t->element)
        return insert(xele, t->left);
    elseif (xele > t->element)
        return insert(xele, t->right);
    else
        ;
}
template<class T>
void BinarySearchTree<T>::insert(const T& xele)
{
    insert(xele, m_proot);
}

6.删除:

template<class T>
void BinarySearchTree<T>::remove(const T& xele, BinaryNode<T>* &t)
{
    if (t == NULL)
        return;
    elseif (xele < t->element)
        remove(xele, t->left);
    elseif (xele > t->element)
        remove(xele, t->right);
    else
    {
        if (t->left != NULL&&t->right != NULL)
        {
            t->element = findMin(t->right);
            remove(t->element, t->right);
        }
        else
        {
            BinaryNode<T>* oldNode = t;
            t = (t->left != NULL) ? t->left : t->right;
            delete oldNode;
        }
    }
}
template<class T>
void BinarySearchTree<T>::remove(const T& xele)
{
    remove(xele, m_proot);
}

7.中序遍历：

template<class T>
void BinarySearchTree<T>::inordertrav()
{
    inordertrav(m_proot);
}
template<class T>
void BinarySearchTree<T>::inordertrav(BinaryNode<T>* &t)//参数是根节点{
    if (NULL == t)
        return;
    if (NULL != t->left)
        inordertrav(t->left);
    cout << t->element << "," << endl;
    if (NULL != t->right)
        inordertrav(t->right);
}

8.转换为双向链表，需要注意的是：不能使用中序遍历的方法去实现转换，这样会引起指针异常；转换后以前操作二叉树的函数全部失效

template<class T>
BinaryNode<T>* BinarySearchTree<T>::getlLeftTail(BinaryNode<T>* &t)
{
    BinaryNode<T>* pC = t;
    while (true)
        if (NULL != pC->right)
            pC = pC->right;
        elsebreak;
    return pC;
}
template<class T>
BinaryNode<T>* BinarySearchTree<T>::getlRightHead(BinaryNode<T>* &t)
{
    BinaryNode<T>* pC = t;
    while (true)
        if (NULL != pC->left)
            pC = pC->left;
        elsebreak;
    return pC;
}
template<class T>
void BinarySearchTree<T>::toDoublelist()
{
    toDoublelist(m_proot);
}
template<class T>
void BinarySearchTree<T>::toDoublelist(BinaryNode<T>* &t)
{
    
    if (NULL == t)
        return;
    if (NULL != t->left)
    {
        BinaryNode<T>* listtail = getlLeftTail(t->left);//先记录下来要与根节点的左指针相连的。
        toDoublelist(t->left);
        listtail->right = t;
        t->left = listtail;
    }

    /*这个方法会出现问题
    //不为空
    if (NULL != m_plist)
    {
        t->left = m_plist;
        m_plist->right = t;
    }
    else//为空表示使双向链表的头
    {
        m_phead = t;
    }
    //为下一次连接做准备
    m_plist = t;

    cout << m_plist->element << ",";*/if (NULL != t->right)
    {
        BinaryNode<T>* listhead = getlRightHead(t->right);
        toDoublelist(t->right);
        listhead->left = t;
        t->right = listhead;
        
    }
        
}

9.打印链表：

template<class T>
void BinarySearchTree<T>::printDoublelist()
{
    BinaryNode<T>* phead = m_proot;
    while (true)
    {
        if (phead->left != NULL)
            phead = phead->left;
        elsebreak;
    }
    while (phead->right!=NULL)
    {
        cout << phead->element << ",";
        phead = phead->right;
    }
    cout << phead->element;
}

原文：http://www.cnblogs.com/WonderHow/p/4431369.html

内容总结

以上是互联网集市为您收集整理的C++二叉查找树实现及转化为双向链表全部内容，希望文章能够帮你解决C++二叉查找树实现及转化为双向链表所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1269036.html

来源：【匿名】

【上一篇】C++02 【下一篇】c++有个库什么的吗?

更多 ►

【C++二叉查找树实现及转化为双向链表】教程文章相关的互联网学习教程文章

二叉树首先要有树节点template<class T> class BinaryNode { public:T element;BinaryNode *left;BinaryNode *right;public:BinaryNode(T passelement);~BinaryNode(); };template<class T> BinaryNode<T>::BinaryNode(T passelement) {this->element=passelement;this->left=NULL;this->right=NULL; }template<class T> BinaryNode<T>::~BinaryNode() { }二叉树对象则比较复杂 template<class T> class BinarySearchTree { privat...

[C++]LeetCode: 117 Simplify Path （简化Unix路径 list双向链表)【代码】

题目： Given an absolute path for a file (Unix-style), simplify it. For example,path = "/home/", => "/home"path = "/a/./b/../../c/", => "/c"click to show corner cases.Corner Cases:Did you consider the case where path = "/../"? In this case, you should return "/".Another corner case is the path might contain multiple slashes ‘/‘ together,such as "/home//foo/". In this case, you should ignore redu...

c++ 实现双向链表【代码】

双向链表：#include<iostream> using namespace std;typedef struct list {int data;struct list *front;struct list *next; }List;List *head; //头结点 List *tail; //尾结点 int sum = 0;void push(int e) {List *p = new List;p->data = e;if(sum == 0){head = p;tail = p;p->front = NULL;p->next = NULL;}else{tail->next = p;p->front = tail;tail = p;p->next = NULL;}sum++; }void pop_back() {List *p = tail->front;p...

双向链表的基础操作（C++实现）【代码】

★C++实现双向链表的基础操作（类的实现）#include<iostream> #include<cassert> using namespace std;typedef int DataType; class double_link_list { //定义双向链表类，包括了双向的前驱和后继指针，以及对象的初始化 public: friend class ListNode; double_link_list(DataType x = 0) :_data(x) ,_next(NULL) ,_prev(NULL) {} private: double_link_list* _prev; double_link_list* _next; DataType ...

【C++/STL】list的实现（没有采用迭代器和空间配置器所实现的双向链表的基本功能）

<span style="font-size:18px;">#include <iostream> using namespace std;//没有采用迭代器和空间配置器所实现的双向链表的基本功能 template<class _Ty> //定义模板类 class list //list类 { public: typedef size_t size_type; //类型重定义 protected:struct _Node; //结构体_Nodefri...

【C++】双向链表

博客介绍了C语言，以及C++的单向链表。那么我们今天介绍的双向链表，顾名思义，就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表，主要有下面几个特点：（1）在数据结构中具有双向指针（2）插入数据的时候需要考虑前后的方向的操作（3）同样，删除数据的是有也需要考虑前后方向的操作那么，一个非循环的双向链表操作应该是怎么样的呢？我们可以自己尝试一下：源代码：#include <iostream> usi...

C++实现双向链表【代码】

双向链表#include<iostream>using namespace std; typedef int DataType;struct Node {Node(const DataType&d):_data(d), _next(NULL), _prev(NULL){}Node*_next;Node*_prev;DataType _data; }; class DList {friend ostream&operator<<(ostream&os, DList& d); public:DList():_head(NULL), _tail(NULL){}~DList(){Node*cur=_head;while (cur){Node*del = cur;cur = cur->_next;delete del;}} public:void PushBack(const DataTyp...

循环双向链表的C++实现【代码】

循环双向链表的增删查改等基本操作#include<iostream> #include<assert.h> using namespace std; typedef int DataType; struct ListNode {DataType _data;ListNode* _prev;ListNode* _next;ListNode(const DataType& x):_data(x),_prev(NULL),_next(NULL){}ListNode():_data(0),_prev(NULL),_next(NULL){} }; class List { private:ListNode _head; public:List(){_head._prev=&_head;_head._next=&_head;}~List(){clear();}void ...

单链表，循环链表，双向链表（C++实现）【代码】【图】

首先是单链表（带附加表头），实现类代码如下： 1 template<class T>2struct LinkNode{//链表节点 3 T data;4 LinkNode *link;5 LinkNode(const T& args,LinkNode<T> *ptr=NULL){6 data=args;7 link=ptr;8 }9};10 11 template<class T>12class List{//带附加头节点的单链表 13protected:14 LinkNode<T> *first;//链表头指针 15public:16 List(){17 first=new LinkN...

C++标准模版库（STL）双向链表（list）的使用【代码】

双向链表是一个常用的数据结构。它并不复杂，如果我们要自己实现也不是太困难的事情。但既然STL已经给我们提供了一个，不妨直接用。这样做，不但省时省力，而且代码的复用性也好。头文件与模板类要想使用STL提供的双向链表，需要包含头文件#include <list>这样，便可以使用模板类list<T>。初始化初始化一个list很简单，用std::list<T> L;便可以初始化一个空的链表。用std::list<T> L{ t1, t2, t3 };便可以初始化一个有三个元素的链...

剑指 Offer-36 二叉搜索树与双向链表c++【代码】【图】

题目描述解法 dfs 很容易发现这题就是考察二叉搜素树的中序遍历是递增序列的性质。我们先写出中序遍历的代码 void dfs(Node* root) {if(root == NULL) return;dfs(root -> left);cout << root -> val;dfs(root -> right); }可以发现只要对中间的主体做出改动，使遍历过程中的结点指针指向对应位置就能形成双向链表。但题目还要求是循环链表，所以我们需要记录头结点和尾结点的位置。思路：连接部分：设置pre结点，初始值为空，...

C++二叉搜索树与双向链表（剑指Offer精简版）【代码】【图】

题目：输入一棵二叉搜索树，将该二叉搜素树转换成一个排序的双向链表。二叉树节点定义如下： struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} }; 解题思路：由于通过中序排序可以转化为双向链表，因此，通过中序遍历的方法（左根右）的递归方法可以解决问题，解决完之后，pList节点指向双向链表的尾结点，pList节点需要通过遍历，返回到头节点，同样...

C++ - 技术教程分类

C++ 教程 C++ 简介 C++ 基本语法 C++ 注释 C++ 数据类型 C++ 变量类型 C++ 变量作用域 C++ 常量 C++ 修饰符类型 C++ 存储类 C++ 运算符 C++ 循环 C++ 判断 C++ 函数 C++ 数字 C++ 数组 C++ 字符串 C++ 指针 C++ 引用 C++ 日期 & 时间 C++ 基本的输入输出 C++ 数据结构 C++ 类 & 对象 C++ 继承 C++ 重载运算符和重载函数 C++ 多态 C++ 数据抽象 C++ 数据封装 C++ 接口（抽象类） C++ 文件和流 C++ 异常处理 C++ 动态内存 C++ 命名空间 C++ 模板 C++ 预处理器 C++ 信号处理 C++ 多线程 C++ Web 编程 C++ 标准库 C++ 有用的资源 C++ 实例 c++ 全部

C++ - 最热教程

C++通过共享内存实现进程间通信（windo...C++基于EasyX制作贪吃蛇游戏（一）文档 C++中的分治算法及常见题目汇总【C++】stringstream的str() 和 string...c++中内置函数qsort（快速排序）和bsea...VS2019 C++创建一个简单项目demo [C++]VS2015用动态链接(MD/MDd)方式编译...C/C++编程学习 - 第15周 ⑥ 药房管理万维考试系统检测不到VC++ 6.0环境解决...C/C++ QT自定义对话框与MID窗体