树结构
树结构概述
什么是树结构
为什么使用树结构
树的基本概念
二叉树:
什么是二叉树
- 满二叉树：所有叶子节点都在最后一层，而且节点的总数为：2^n-1,n是树的高度。
- 完全二叉树：所有叶子节点都在最后一层或倒数第二层，且最后一层的叶子节点在左边连续，倒数第二节的叶子节点在右边连续。
链式存储的二叉树
1. 创建二叉树
2. 添加节点
3. 树的遍历
前序遍历
中序遍历
后序遍历
4. 查找节点
5. 删除节点
顺序存储的二叉树
- 顺序存储的二叉树通常只考虑完全二叉树
- 第n个元素的左子节点是：2*n+1
- 第n个元素的右子节点是：2*n+2
- 第n个元素的父节点是：(n-1)/2
线索二叉树
二叉查找树
二叉排序树概述
BST对于二叉树中的任何一个非叶子节点，要求左子节点比当前节点值小，右子节点比当前节点值大。添加节点、查找节点、删除节点
package demo11;
public class BinarySortTree{
Node root;
/**
*向二叉排序树中添加节点
*@param node
*/
public void add(Node node){
//如果是一颗空树
if(root==null){
root = node;
}else{
root.add(node);
}
}
/**
*中序遍历二叉排序树，从小到大的顺序
*@param root
*/
public void midShow(){
if(root!=null){
root.midShow(root);
}
}
/**
*节点的查找
*@param value
*@return
*/
public Node search(int value){
if(root==null){
return null;
}else{
return root.search(value);
}
}
/**
*节点的查找
*@param value
*/
public void delete(int value){
if(root==null){
return;
}else{
//找到这个节点
Node target = search(value);
//如果没有这个节点
if(target==null){
return;
}
//找到他的父节点
Node parent = searchParent(value);
//要删除的节点是叶子节点
if(target.left==null&&target.right==null){
//要删除的节点是父节点是左子节点
if(parent.left.value==value){
parent.left=null;
//要删除的节点是父节点的右子节点
}else{
parent.right=null;
}
//要删除的节点有两个子节点的情况
}else if(target.left!=null&&target.right!=null){
//删除右子树中值最小的节点，获取到该节点的值
int min = deleteMain(target.right);
//替换目标节点中的值
target.value = min;
//要删除的节点有一个左子节点或右子节点
}else{
//有左子节点
if(target.left!=null){
//要删除的节点是父节点是左子节点
if(parent.left.value==value){
parent.left=target.left;
//要删除的节点是父节点的右子节点
}else{
parent.right=target.left;
}
//有右子节点
}else{
//要删除的节点是父节点是左子节点
if(parent.left.value==value){
parent.left=target.right;
//要删除的节点是父节点的右子节点
}else{
parent.right=target.right;
}
}
}
}
}
/**
*删除一颗树中最小的节点
*@param node
*@return
*/
private int deleteMin(Node node){
Node target = node;
//递归向左找
while(target.left!=null){
target=target.left;
}
//删除最小的这个节点
delete(target.value);
return target.value;
}
/**
*搜索父节点
*@param value
*@return
*/
public Node searchParent(int value){
if(root==null){
return null;
}else{
return root.searchParent(value);
}
}
}
<!-- ============================== -->
package demo11;
public class Node(){
int value;
Node left;
Node right;
public Node(int value){
this.value=value;
}
/**
*向子树中添加节点
*@param node
*/
public void add(Node node){
//如果是一颗空树
if(root==null){
return;
}
//判断传入的节点的值比当前子树的根节点的值大还是小
//添加的节点比当前节点的值更小
if(node.value<this.value){
//如果左节点为空
if(this.left==null){
this.left=node;
//如果不为空
}else{
this.left.add(node);
}
}else{
if(this.right==null){
this.right=node;
}else{
this.right.add(node);
}
}
}
/**
*中序遍历
*@param node
*/
public void midShow(Node node){
if(node==null){
return;
}
midShow(node.left);
midShow(node.right);
}
/**
*节点的查找
*@param value
*@return
*/
public Node search(int value){
if(this.value==value){
return this;
}else if(value<this.value){
if(left==null){
return null;
}
return left.search(value);
}else{
if(right==null){
return null;
}
return right.search(value);
}
}
/**
*搜索父节点
*@param value
*@return
*/
public Node searchParent(int value){
if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
return this;
}else{
if(this.value>value){
return this.left.searchParent(value);
}else{
return this.right.searchParent(value);
}
}
return null;
}
}
<!-- ================================= -->
package demo11;
public class TestBinarySortTree{
public static void main(String[] args){
int[] arr = new int[] {7,3,10,12,5,1,9};
//创建一颗二叉排序树
BinarySortTree bst = new BinarySortTree();
//循环添加
for(int i:arr){
bst.add(new Node(i));
}
//查看树中的值
bst.midShow();
//查找
Node node = bst.search(10);
//System.out.println(node.value);
//删除叶子节点
bst.delete(5);
bst.midShow();
System.out.println("========");
//删除只有一个子节点的节点
bst.delete(3);
bst.midShow();
//删除有两个子节点的节点
bst.delete(3);
bst.midShow();
}
}
