数据结构----二叉树及二叉树排序

原创 lronelove 随笔 浅谈数据结构 80阅读 2018-09-09 01:05:16 举报

1.什么是二叉树

定义:在计算机科学中,二叉树是每个结点最多有两个子树的树结构。

了解二叉树之前,让我们先来做一个小游戏。

首先,我们随机找一串数组,比如:20, 16, 90, 50, 100, 15, 17。

然后,我们用笔把第一个数字20写在纸上,然后比一个数(比如20)小的数字放在该数字的左下角,如果该数字的左下角有数字了,那么继续和该数字的左下角比较;比一个数(比如20)大或者相等的数字放在该数字的右下角。比如,16比20小,16放在20的左下角,90比20大,90放在20的右下角。如图1:

当我们选择50和20比较的时候,发现50大于20,应该放在20的右下角。但是20的右下角已经有90了,所以,50继续和90比较,50小于90,所以50放在90的左下角。
依次类推,我们将得到图2:

这就是一个二叉树。
我们可以发现以下特性:

  1. 每一个结点最多只有一个双亲结点,比如20是16的双亲结点,20是根结点所以没有双亲结点。
  2. 一个非空的二叉树有且只有一个根结点,比如图2的数字20
  3. 一个结点最多有两个子节点,一个是左孩子,一个是右孩子。其中左孩子的值小于双亲结点的值,右孩子的值不小于双亲结点的值

2.二叉树的实现

我们先看一下单个结点的结构:

  1. parent属性,指向双亲结点
  2. left属性,指向左孩子结点
  3. right属性,指向右孩子结点
  4. key属性,存储数据

基于这些属性,我们来构造以下:

好,现在我们有了结点的结构,然后,我们来初始化一个空的二叉树:

根结点root初始化为null, sortedArray待会儿用来存储排序之后的数字。

紧接着我们去实现以下添加结点的append方法:
添加一个结点的时候,如果root为null,那么这个结点就是根结点;

如果根结点,不为空,从根结点开始比较。

当前结点的key值大于新添加结点的key值。如果该结点的左孩子不存在,那么新添加的结点就是当前结点的左孩子;如果存在,继续和当前结点的左孩子比较,以此类推。

当前结点的key值不大于新添加结点的key值。如果该结点的右孩子不存在,那么新添加的结点就是当前结点的右孩子;如果存在,继续和当前结点的右孩子比较,以此类推。

代码实现如下

打印的结果如下:

感兴趣的可以‘运行’下代码,展开看一下,其实就是图2的结构。

3.利用二叉树排序

二叉树有什么用处呢?
其中之一就是排序,排序的实现是利用递归。
代码如下:

打印出来的binaryTree.sortedArray:

它是从小到大排序,代码很简单,递归是核心,得慢慢理解。大家也可以尝试改变以下排序代码的顺序,看看可不可以构造出从大到小的排序。
感兴趣的话,大家可以尝试下,晚安。

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复