【知识点】
- 为什么要学习二叉树
- 二叉树的概念和特点
- 二叉树的定义和创建
- 二叉树的基本操作
- 二叉树的遍历方式
1、为什么要学习二叉树
二叉树的知识更倾向于理论，我们在实际应用开发过程中直接使用得并不多,但是二叉树作为数据结构的一个重要的组成部分，在我们的面试过程中，会经常遇到二叉树知识相关问题，而且底层很多东西都是基于二叉树实现的，比如TreeMap、TreeSet、Linux的虚拟内存管理、数据库系统等，所以掌握二叉树的基本操作是相当有必要的。
2、树的概念和特点
我们这里来学习我们数据结构中的树，而不是现实生活中的树。但是它和现实生活中的树有着很多的相似之处，或者可以说数据结构的树是对现实生活中树的抽象。那么我们先来看看现实生活中树的样子，如下图：
看完了现实生活中树的样子后，就来看看数据结构中树的样子了，如下图：
树的定义
树是由n（n>=1）个有限节点组成的一个具有层次关系的集合。
树的特点：
- 每个节点有零个或多个子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树。
3、二叉树的概念和特点
二叉树是一种特殊的树，在树的基础上添加约束条件：每个节点下最多只有两棵子树。它具有特点：
- 每个节点最多有两颗子树。
- 左子树和右子树是有顺序的，次序不能颠倒。
- 即使某节点只有一个子树，也要区分左右子树。
二叉树图
4、二叉树实现分析
1、一个二叉树节点有三个部分，一个是指向左子树的部分，一个是指向右子树的部分，另外一个是数据部分。可以把这个节点抽象成一个节点对象，节点对象有两个节点对象属性和一个数据属性。如下图：
2、一个二叉树有且只有一个根节点，其余的都是根节点的直接或间接子节点。所以可以把二叉树抽象成一个对象，该对象有一个节点类型的数据，用来保存根节点。如下图：
5、节点类和二叉树类的定义
1、通过刚刚的分析，首先要定义一个类：节点类，代码实现如下
/**
* 节点类
* @author pkxing
*
*/
public class Node {
// 节点内容
int value;
// 左节点
Node leftChild;
// 右节点
Node rightChild;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return String.valueOf(value);
}
}2、然后定义二叉树类，代码实现如下
/**
* 二叉树类
* @author pkxing
*
*/
public class BinaryTree {
// 根节点
private Node root = null;
// 构造方法
// 有参数
public BinaryTree(int value) {
root = new Node(value);
root.leftChild = null;
root.rightChild = null;
}
// 无参数
public BinaryTree(){}
}6、二叉树的基本操作
需求：现有数组int a [ ] = {3,1,0,2,7,5,8,9}，要求如下:
1.将数组中元素存储到二叉树中。
2.效果图如下：
二叉排序树的本质就是一颗二叉树,它具有如下特点:
- 所有左节点的元素值小于其父节点的元素值.
- 所有右节点的元素值大于其父节点的元素值.
添加节点
- 添加元素流程图
- 在二叉树类BinaryTree中定义成员方法，方法声明如下：
public boolean add(int value)
参数解析
value：节点的内容
返回值解析
true：表示添加成功
false：表示添加失败
- 代码实现
/**
* 插入节点
* @param value 节点的值
* @return 插入成功返回true，否则返回false
*/
public boolean add(int value) {
// 定义变量用来标识是否插入成功，默认值表示插入成功
boolean success = true;
// 根据内容创建节点对象
Node node = new Node(value);
// 判断根节点是否为null，如果为null，则将node对象作为根节点对象
if (root == null) { // 没有根节点
// 将node对象作为根节点对象
root = node;
// 设置左右节点为null
root.leftChild = null;
root.rightChild = null;
} else { // 有根据节点
// 定义变量记录当前遍历的节点对象：默认从根节点对象开始遍历
Node current = root;
// 遍历树上的所有节点对象
while (true) {
if (value < current.value) {
// 来到这里说明node对象应该添加到current节点对象的左边
if (current.leftChild == null) {
current.leftChild = node;
break;
}
// 获得current节点的左子节点对象，并赋值给current变量
current = current.leftChild;
} else if (value > current.value) {
// 来到这里说明node对象应该添加到current节点对象的右边
if (current.rightChild == null) {
current.rightChild = node;
break;
}
// 获得current节点的右子节点对象，并赋值给current变量
current = current.rightChild;
} else { // value值已经存在了，则直接返回false
success = false;
break;
}
}
}
// 插入成功
return success;
}查询节点
- 查询思路
先查找其根节点，如果根节点的元素值和要查找的元素值相等，则返回该根节点对象。否则，比较根节点的元素和要查找的元素，
如果元素值大于根节点元素值，则查询其右子树。
如果元素值小于根节点元素值，则查询其左子树。
- 在二叉树类BinaryTree中定义一个查询的成员方法，方法声明如下：
public Node get(int value)
参数解析：value：要查找节点内容。
返回值解析：查询到的节点对象
- 代码实现
/**
* 根据节点内容查找节点对象
* @param value 内容
* @return 查找到的节点对象，如果没有则返回null
*/
public Node get(int value) {
// 定义变量记录当前遍历的节点对象，默认从根节点开始遍历
Node current = root;
while (true) {
// 判断value和current节点对象的value是否相同
if (value == current.value) {
// 来到这里则说明current节点对象就是要查找的对象，直接返回即可
return current;
} else if (value < current.value) {
// 来到这里说明要查找的节点对象是在current节点的左子树上
current = current.leftChild;
} else if (value > current.value) {
// 来到这里说明要查找的节点对象是在current节点的右子树上
current = current.rightChild;
}
// 如果current节点对象为null，则说明没有找到对应的节点对象
if (current == null) {
return null;
}
}
} 二叉树的遍历方式
遍历流程:先遍历左子树，再访问根节点，最后遍历右子树.
代码实现如下
/**
* 先遍历左子树，再访问根节点，最后遍历右子树；
*
* @param node
*/
public void inOrder(Node node) {
if (node != null) {
inOrder(node.getLeftChild());
System.out.println(node);
inOrder(node.getRightChild());
}
}重写toString方法
/**
* 将指定节点下的所有子节点的内容按顺序输出
* @param node
*/
public void order2(Node node,List<Integer> list){
if(node == null) return;
// 先遍历node的左节点
order2(node.getLeftChild(),list);
// 将节点内容添加集合中
list.add(node.getValue());
// 遍历node的右节点
order2(node.getRightChild(),list);
}
@Override
public String toString() {
// 创建集合对象
List<Integer> list = new ArrayList<>();
order2(root,list);
return list.toString();
}学废了吗？