数据构架与算法—二叉排序树(java)

前言

前面介绍学习的大多是线性表相关的内容，把指针搞懂后显然也没有什么难度。规则相对是简单的。

再数据结构中树、图才是数据结构标志性产物，(线性表大多都现成api可以使用),因为树的难度相比线性表大一些甚至树的拓展性很强，你所明白的树、二叉树、二叉排序树，AVL树，线索二叉树、红黑树、B数、线段树等等高级数据结构。然而二叉排序树是所有的基础，所以彻底搞懂二叉排序树也是比较重要的。

树

参考王道数据结构

二叉树也是树的一种，而二叉排序树又是二叉树的一种。

树是递归的，将树的任何一个节点或者节点下的节点都能组合成一个新的树。并且这些操作基于递归完成。

根节点： 最前面的哪个节点(root)，根节点没有前驱节点，只有子节点(0个或多个都可以)

层数： 一般觉得根节点是第1层(有的也说第0层)。而树的高度就是层数最高(上图层数开始为1)节点的层数

节点关系: 父节点：就是链接该节点的上一层节点,孩子节点:和父节点对应，上下关系。而后人节点是父节点的父节点(或者祖先)节点。兄弟节点：拥有同一个父节点的节点们!

度： 节点的度就是节点拥有孩子节点的个数(是父母不是子孙).而树的度(最大)节点的度。同时，如果度高于0就变成分支节点,度等于0就变成叶子节点(没有子孙)。

相关性质：

树的节点数=所有节点度数+1.

度为m的树第i层最多有mi-1个节点。(i>=1)

高度而h的m叉树最多(mh-1)/(m-1)个节点(等比数列求和)

n个结点的m叉树最小高度[logm(n(m-1)+1)]

二叉树

二叉树是一树的一种，但应用非常多，所以必须深入学习。二叉树的每个结点最多只有两个节点。

二叉树与度为2的树的区别：

一：度为2的的树需要有三个节点以下，二叉树可以为空。

二：二叉树的度不一定为2：比如说斜树。

三：二叉树有左右节点区分，而度为2的树没有左右节点的区分。

几种特殊二叉树：

满二叉树。高度为n的满二叉树有2n-1个节点

完全二叉树：上面一层全部满，最下一层从左到右排序排列

二叉排序树：树根据一定规则插入顺序(本文详解)。

平衡二叉树：树上任意结点左子树和右子树深度差距不低于1.

二叉树性质：

相比树，二叉树的性质就是树的性质非常具体化。

非空二叉树叶子结点数=度为2的节点树+1.本来一个节点一旦度为1.那么经常延续就一个叶子，但即使发生一个度为2不仅再现其实的一个节点，会多出一个节点必须维系。所以到最终会多出一个叶子。

非空第i层最多有2i-1个节点。

高为h的树最多有2h-1个节点(等比求和)。

完全二叉树若从左向右，从上到下编号如图：

二叉排序(搜索)树

概念

前面铺垫那么多，咱们言归正传二叉排序树 数据结构，详细实现一个二叉排序树。首先要知道二叉排序树的规则：

从任意节点开始，节点右边节点值总比节点右侧值要小。

例如。一个二叉排序树依次插入15，6，23，7，4，71，5，50会产生下图顺序

构造

首先二叉排序树是由若干节点组成。

对于node需要很多属性：left，right，和value。其中left和right是左右指针，而value是存储的数据，这里用int 类型。

node类构造为：

class node {//结点

public int value;

public node left;

public node right;

public node()

{

}

public node(int value)

{

this.value=value;

this.left=null;

this.right=null;

}

public node(int value,node l,node r)

{

this.value=value;

this.left=l;

this.right=r;

}

}

既然节点构造好了，那么就应该节点等其它信息构造成树。有了链表构造经验，很容易得知一棵树最主要的抑或root根节点。

所以树的构造为：

public class BinarySortTree {

node root;//根

public BinarySortTree()

{root=null;}

public void makeEmpty()//变空

{root=null;}

public boolean isEmpty()//查看是否为空

{return root==null;}

//各种方法

}

主要手段

既然早已构造号一棵树，那么就应该实现主要的方式。因为二叉排序树中每个结点都能看作一棵树。所以我们建立方式的是之后加上节点参数(也就是函数对每一个节点都能有效)

findmax(),findmin()

findmin()找到最小节点：

因为所有节点的最小都是往左插入，所以只应该找到最右边的返回就能。

findmax()找到最大节点：

因为所有节点大的都是往右边插入，所以只应该找到最右边的返回就能。

代码使用递归函数

public node findmin(node t)//查找最小返回值是node，调用查看结果时应该.value

{

if(t==null) {return null;}

else if(t.left==null) {return t;}

else return(findmin(t.left));

}

public node findmax(node t)//查找最大

{

if(t==null) {return null;}

else if(t.right==null) {return t;}

else return(findmax(t.right));

}

isContains(int x)

这里的含义是查找二叉查找树中能否存在x。

假设我们我们插入x，那么即使存在x我们必定会在查找插入模式的过程中碰到x。因为你可以即使尚未存在的点，再它的前方会走一次和它相似的方法。也就是说前面固定，我来1w次x，那么x都会到达这个位置。那么我们直接进行查找非常即可!

public boolean isContains(int x)//是否存在

{

node current=root;

if(root==null) {return false;}

while(current.value!=x&¤t!=null)

{

if(x

if(x>current.value) {current=current.right;}

if(current==null) {return false;}//在上面判断即使超直接返回

}

//如果在这个位置判定是否为空会导致current.value不存在报错

if(current.value==x) {return true;}

return false;

}

insert(int x)

插入的思想和上面isContains类似。找到自己的位置(空位置)插入。但是又不太一样。你可能会疑问为什么不直接找到最后一个空，然后将current赋值过去current=new node(x)。这样的化current就相当于指向一个new node(x)节点。和树就摆脱关系，所以要提早判断能否为空，若为空将它的left或者right赋值即可。

public node insert(int x)// 插入 t是root的引用

{

node current = root;

if (root == null) {

root = new node(x);

return root;

}

while (current != null) {

if (x < current.value) {

if (current.left == null) {

return current.left = new node(x);}

else current = current.left;}

else if (x > current.value) {

if (current.right == null) {

return current.right = new node(x);}

else current = current.right;

}

}

return current;//其中用不到

}

比如说上面结构插入51

delete(int x)

删除操作算是一个相对较难理解的操作了。

删除节点规则：

先找到这个点。这个点用这个点的子树可以补上的点填充该点，然后在以这个点为头删除替代的子结点(调用数组)然后在添加到最终情况(只有一个分支，等等)。

首先要找到移除的位置，然后移除的哪个点分类探讨二叉排序树 数据结构，如果有两个儿子，就选左边孩子的最右边那种点代替，然后再子树删除替代的哪个点。如果是一个节点，判断是左空还是右空，将这个点指向不空的哪个。不空的那种就代替了这个节点。入股左右都是空，那么他自己变空null就删除了。

删除的节点没有子孙:

这种状况不需要考虑，直接删除就能。(途中红色点)。另节点=null即可。

左节点为空、右节点为空：

此种情况也很容易，直接将删除点的子节点放在被删除位置即可。

左右节点均不空

这种状况相对是复杂的。因为这涉及到一个策略问题。

如果拿19或者71节点填补。虽然可以确保部分侧大于小于该节点，但是会引起合并的混乱.比如你若用71替代23节点。那么你应该考虑三个节点(19,50,75)之间怎样处理，还要考量他们能否满，是否有孩子。这是个非常复杂的过程。

首先，我们要探讨我们要的这个点的属性：能够继承被删除点的所有属性。如果取左侧节点(例如17)那么首先能满足所有右侧节点都比他大(右侧比右边大)。那么还要再这儿选一个最大的点让左半枝都比它小。我们预测左支最大的点必定是子树最右侧!

如果这个节点是最底层我们很高考虑，可以直接更换值，然后将最底层的点删除就能。但是一旦这个节点有左枝。我们该如何办?

这个分析出来也不难，用递归的观念啊。我们删除这个节点，用可以满足的节点更换了。会造成什么样的后果?

多出个用过的19节点，转化一下，在左子树中删除19的点!那么这个难题又转换为删除结点的问题，查找左子树中有没有能够代替19这个点的。

所以整个删除算法流程为：

代码为

public node remove(int x, node t)// 删除节点

{

if (t == null) {

return null;

}

if (x < t.value) {

t.left = remove(x, t.left);

} else if (x > t.value) {

t.right = remove(x, t.right);

} else if (t.left != null && t.right != null)// 左右节点均不空

{

t.value = findmin(t.right).value;// 找到右侧最小值替代

t.right = remove(t.value, t.right);

} else // 左右单空甚至左右都空

{

if (t.left == null && t.right == null) {

t = null;

} else if (t.right != null) {

t = t.right;

} else if (t.left != null) {

t = t.left;

}

return t;

}

return t;

}

完整代码

二叉排序树完整代码为：

package 二叉树;

import java.util.ArrayDeque;

import java.util.Queue;

import java.util.Stack;

public class BinarySortTree {

class node {// 结点

public int value;

public node left;

public node right;

public node() {

}

public node(int value) {

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-121391-1.html