跟着动画学 Go 数据结构之二叉树
树可以有许多不同的形状,并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同。 而在其中最常用的树之一是二叉树。 二叉树是一棵树,其中每个节点最多可以有两个孩子。 一个孩子被识别为左孩子,另一个孩子被识别为右孩子。
二叉树是一种数据结构,在每个节点下面最多存在两个其他节点。即一个节点要么连接至一个、两个节点或不连接其他节点。
树形结构的深度(也被称作高度)则被定义为根节点为根节点至某个节点间的最长路径,而节点的深度则表示当当前节点至树根节点间的边数。二叉树有许多不同的形状和大小。 形状取决于节点的数量和节点的链接方式。 下图说明了由九个节点组成的二叉树的三种不同形状:
Go 语言实现二叉树
定义二叉树的结构
复制代码
二叉树遍历
复制代码
traverse()
函数通过递归方式访问二叉树的全部节点。
创建二叉树
利用 create()
函数利用随机整数填写二叉树:
复制代码
插入值
insert
函数:
第一个 if 语句在插入时如果是空树,就把插入的节点设置为根节点,并创建为
&Tree{nil, v, nil}
第二个 if 语句确定插入值是否已在二叉树中存在。若存在,函数将直接返回且不执行任何操作
第三个 if 语句检查插入的值位于当前节点的左孩子节点还是右孩子节点,并插入到相应的位置。
复制代码
测试
复制代码
运行结果:
复制代码
版权声明: 本文为 InfoQ 作者【宇宙之一粟】的原创文章。
原文链接:【http://xie.infoq.cn/article/a15be07a0f7e369ff2c9d4c77】。文章转载请联系作者。
评论