雅乐网

计算机技术、学习成长

计算机 » 数据结构 » 常用数据结构C++实现(3):二叉树和二叉搜索树

常用数据结构C++实现(3):二叉树和二叉搜索树

最新版完整代码:https://github.com/yalewoo/cpp-data-structure

二叉树

bintree.h

bintree.cpp

本文中的二叉树结点包含父指针,左右孩子指针,结点高度信息,具体数据结构为

二叉树的数据结构

下面简单介绍一些重要接口的实现思路

高度

二叉树结点自身含有height成员变量,用于记录结点的高度信息,该信息在插入和删除时进行实时维护,主要通过updateHeightAbove函数来进行更新,该函数从下到上依次调用updateHeight函数对每个结点的高度进行更新。

在插入或者删除元素后,只会影响操作元素的祖先元素的高度,其余元素高度不受影响。采用从下到上的顺序,可以保证更新x结点高度时,x的孩子的高度已经得到更新。

 结点个数

结点个数并不是直接记录在变量中,而是每次进行计算。计算采用递归的方法,结点个数 = 左子树结点个数 + 右孩子结点个数 + 1 ,递归基是叶子结点个数为1

树的结点操作

有插入左孩子,右孩子,左子树,右子树,分离子树,删除子树。

分离子树secede把子树从二叉树中分离,并返回子树的指针。

删除子树直接删除子树,并释放空间,返回的是删除的结点个数。

遍历操作

见源代码

显示接口 display

该函数可以在命令行界面下显示一棵二叉树。效果如图

scrn20160112152917

显示时,结点的水平顺序就是中序遍历时结点的顺序,而垂直高度通过层次遍历得到。思路很简单,具体实现有点繁琐。见 二叉树的图形化显示

二叉搜索树

BST.h

BST.cpp

从二叉树派送而来,重写或增加 search 、insert和remove接口

search

二叉搜索树查找算法,该函数同时记录了查找结果的父节点,记录在hot成员变量中。这样可以用于insert时调用。

BST.cpp

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/data_structure_cpp_3_binary_tree_and_binary_search_tree.html

上一篇:

下一篇:

我要评论

验证码*: 6 + 6 =