孟飞阳

# 基础概念

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

1.叶子结点；

2.仅有左子树或右子树的结点

3.左右子树都有结点

# 代码实现

``````package demo3;
public class BinaryTree {
//根节点
private Node root;
/** 树的结点 */
private static class Node{
//数据域
private long data;
//左子结点
private Node leftChild;
//右子结点
private Node rightChild;
Node(long data){
this.data = data;
}
}
public void insert(long data){
Node newNode = new Node(data);
Node currNode = root;
Node parentNode;
//如果是空树
if(root == null){
root = newNode;
return;
}
while(true){
parentNode = currNode;
//向右搜寻
if(data > currNode.data){
currNode = currNode.rightChild;
if(currNode == null){
parentNode.rightChild = newNode;
return;
}
}else{
//向左搜寻
currNode = currNode.leftChild;
if(currNode == null){
parentNode.leftChild = newNode;
return;
}
}
}

}

/**
* 前序遍历
* @param currNode
*/
public void preOrder(Node currNode){
if(currNode == null){
return;
}
System.out.print(currNode.data+" ");
preOrder(currNode.leftChild);
preOrder(currNode.rightChild);
}

/*
* 中序遍历
*/
public void inOrder(Node currNode){
if(currNode == null){
return;
}
inOrder(currNode.leftChild);
System.out.print(currNode.data+" ");
inOrder(currNode.rightChild);
}

/**查找结点*/
public Node find(long data){
Node currNode = root;
while(currNode!=null){
if(data>currNode.data){
currNode = currNode.rightChild;
}else if(data<currNode.data){
currNode = currNode.leftChild;
}else{
return currNode;
}
}
return null;
}
/**
*  后序遍历
* @param currNode
*/
public void postOrder(Node currNode){
if(currNode == null){
return;

}
postOrder(currNode.leftChild);
postOrder(currNode.rightChild);
System.out.print(currNode.data+" ");
}
/** 删除结点
*  分为3种情况
*  1.叶子结点
*  2.该节点有一个子节点
*  3.该节点有二个子节点
*  @param data
*
*/
public boolean delete(long data) throws Exception {
Node curr = root;

//保持一个父节点的引用
Node parent = curr;
//删除为左结点还是右界定啊
boolean isLeft = true;
while(curr != null && curr.data!=data){
parent = curr;
if(data > curr.data){
curr = curr.rightChild;
isLeft = false;
}else{
curr = curr.leftChild;
isLeft = true;
}
}
if(curr==null){
throw new Exception("要删除的结点不存在");
}
//第一种情况,要删除的结点为叶子结点
if(curr.leftChild == null && curr.rightChild == null){
if(curr == root){
root = null;
return true;
}
if(isLeft){
parent.leftChild = null;
}else{
parent.rightChild = null;
}
}else if(curr.leftChild == null){
//第二种情况，要删除的结点有一个子节点且是右子结点
if(curr == root){
root = curr.rightChild;
return true;
}
if(isLeft){
parent.leftChild = curr.rightChild;
}else{
parent.rightChild = curr.rightChild;
}
}else if(curr.rightChild == null){
//第二种情况，要删除的结点有一个子节点且是左子结点
if(curr == root){
root = curr.leftChild;
return true;
}
if(isLeft){
parent.leftChild = curr.leftChild;
}else{
parent.rightChild = curr.leftChild;
}
}else{
//第三种情况，也是最复杂的一种情况，要删除的结点有两个子节点，需要找寻中序后继结点
Node succeeder = getSucceeder(curr);
if(curr == root){
root = succeeder;
return true;
}
if(isLeft){
parent.leftChild = succeeder;
}else{ parent.rightChild = succeeder;
}
//当后继结点为删除结点的右子结点
succeeder.leftChild = curr.leftChild;

}
return true;
}
public Node getSucceeder(Node delNode){
Node succeeder = delNode;
Node parent = delNode;
Node currNode = delNode.rightChild;
//寻找后继结点
while(currNode != null){
parent = succeeder;
succeeder = currNode;
currNode = currNode.leftChild;
}
//如果后继结点不是要删除结点的右子结点
if(succeeder != delNode.rightChild){
parent.leftChild = succeeder.rightChild;
//将后继结点的左右子结点分别指向要删除结点的左右子节点
succeeder.leftChild = delNode.leftChild;
succeeder.rightChild = delNode.rightChild;
}
return succeeder;

}
public static void main(String []args) throws Exception {
BinaryTree binaryTree = new BinaryTree();
//插入操作 217 binaryTree.insert(5);
binaryTree.insert(2);
binaryTree.insert(8);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(6);
binaryTree.insert(10);
//前序遍历
System.out.println("前序遍历：");
binaryTree.preOrder(binaryTree.root);
System.out.println();
//中序遍历
System.out.println("中序遍历：");
binaryTree.inOrder(binaryTree.root);
System.out.println();
//后序遍历
System.out.println("后序遍历：");
binaryTree.postOrder(binaryTree.root);
System.out.println();
//查找结点
Node node = binaryTree.find(10);
System.out.println("找到结点，其值为："+node.data);
//删除结点
binaryTree.delete(8);
System.out.print("删除结点8,中序遍历：");
binaryTree.preOrder(binaryTree.root);
}
}``````

```前序遍历： 5 2 1 3 8 6 10

### 孟飞阳

Java学习资料-Java常用算法-二叉树算法

2015/01/28
0
0

AI科技大本营
09/27
0
0

CSDN资讯
10/02
0
0

2016/05/14
0
0
872. Leaf-Similar Trees - LeetCode

Question 872. Leaf-Similar Trees Solution 题目大意： 如果两个二叉树的叶子节点相同就认为这两个二叉树相似。给两个二叉树判断是否相似。 思路： 用递归把两个二叉树的叶子节点遍历出来，...

yysue
09/05
0
0

1.背景介绍 异常检测可以定义为“基于行动者（人或机器）的行为是否正常作出决策”，这项技术可以应用于非常多的行业中，比如金融场景中做交易检测、贷款检测；工业场景中做生产线预警；安防...

13分钟前
1
0
DecimalFormat 类基本使用

/* * DecimalFormat 类主要靠 # 和 0 两种占位符号来指定数字长度 * 0 表示如果位数不足则以 0 填充 * # 表示只要有可能就把数字拉上这个位置 * */ public static void main(String[] args){...

30分钟前
3
0
This APT has Super Cow Powers.

47分钟前
2
0

56分钟前
6
0

1
0