二叉排序树
二叉树基本概念
二叉树：是n(n>=0)个结点的有限集。该集合或为空或由一个根节点和两个互不相交的的节点
满二叉树：在一棵二叉树中，果所有分支结点都存在左子树和右子树
完全二叉树：n个结点的二叉树按层次序编号，编号为i（1<=i<=n）的结点与同样深度的满二叉树编号为i的结点在二叉树中的位置完全相同
完全二叉树官方定义：二叉树的深度为h,那么除了h层以外，其他的层的节结点数都达到最大值，并h层的所有结点都连续集中在最左边
二叉排序树的基本概念和生成
二叉排序树：一棵空树或者具有如下性质的二叉树，又称二叉查找树、二叉搜索树
1.若左子树不为空，那么左子树上面的所有结点的关键字都比根结点的关键字小
2.若右子树不为空，那么右子树上面的所有结点的关键字都比根结点的关键字大
1.左右子树都为二叉树
image
我们现在按照二叉排序树的规则，生成一个二叉排序树来存储一组数据
1.首先判断有无根结点，没有就创建根结点
2.往下遍历，小的放左边，大的放右边。
下面开始手撕代码
结点结构图
static class TreeNode{
TreeNode parent; //父结点
TreeNode leftChild; // 左子结点
TreeNode rightChild; //右子结点
int data;//存储数据
public TreeNode(int data){
this.data=data;
}
}
相信这里应该很好理解，对于一个节点来说，他需要存储本身的数据外，还要存储父结点、左子树和右子树的地址。
2.添加数据
这边既然生成二叉树，肯定事将一组数据一个一个插入，依次生成一个一个结点来储存
// 循环添加
for (int i : datas) {
put(i);
}
/**
* 添加一个数据
* */
public static TreeNode put(int data) {
// 如果根结点为空
if (root == null) {
TreeNode node = new TreeNode(data);
root = node;
return node;
}
TreeNode parent = null;
TreeNode node = root;
// 从根结点开始往下遍历 ，比当前结点小 查找左边 ，比当前结点大 查找右边 ，直到找出的空结点
for(; node != null;) {
parent = node;
if (data < node.data) {
node = node.leftChild;
} else if(data > node.data) {
node = node.rightChild;
} else {
return node;
}
}
//创建存储当前数据的结点
TreeNode newNode = new TreeNode(data);
// 判断是加载左边还是右边
if (data < parent.data) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
// 赋值新结点的父结点
newNode.parent = parent;
return newNode;
}
我们来分析一下上面的流程
1.这个树是否是空的 是 创建结点存储数据 返回结点
2.根据上述生成规则轮询结点直到null，此时得到了父结点
3.再判断添加左右子树
上面就是一个结点的添加过程。
至此 我们就能对一组数据生成一个二叉排序树。
下面我们接着说一下对二叉排序树的遍历吧。现在我们有个二叉排序树，我们改怎么样遍历出所有的节点数据呢？
我们对一段数据进行测试
private static int[] datas ={10,2,6,15,23,5,9,11}; //待存储的数据
image.png
1.先序遍历 ---- 根结点 > 左子树 > 右子树
image.png
/**
* 前序遍历
* */
public void preOrderTraverse(TreeNode root){
if(root==null){
return;
}
System.out.println("前序:" + root.data);
preOrderTraverse(root.leftChild);
preOrderTraverse(root.rightChild);
}
结果-->
前序:10
前序:2
前序:6
前序:5
前序:9
前序:15
前序:11
前序:23
image.png
/**
* 中序
* */
public static void midOrderTraverse(TreeNode root){
if(root==null){
return;
}
midOrderTraverse(root.leftChild);
System.out.println("中序" + root.data);
midOrderTraverse(root.rightChild);
}
结果-->
中序2
中序5
中序6
中序9
中序10
中序11
中序15
中序23
image.png
/**
* 后序
* */
public static void postOrderTraverse(TreeNode root){
if(root==null){
return;
}
postOrderTraverse(root.leftChild);
postOrderTraverse(root.rightChild);
System.out.println("post :" + root.data);
}
结果-->
post:5
post:9
post:6
post:2
post:11
post:23
post:15
post:10
在此运用了递归算法实现了下二叉排序树的三种遍历
在理解遍历的时候 ，我们可以根据图来理解，下面画一下具体理解步骤
image.png
