在编程提高群的本周作业中，有一项是”自己实现一个二叉树(BinaryTree)“。老师简单的讲解了二叉树大概是什么，并针对这个作业将模板代码写给了我们，让我们自己去实现。虽然完成了，但自己觉得很多地方还是没有很好理解。
于是后面去 https://www.youtube.com/watch?v=M6lYob8STMI 找到了一个老外的不错的视频，内容是关于二叉树的概念以及用Java实现二叉树的节点(Node)，以及节点的增加和查找。
可以科学上网，以及英文无压力的同学建议看一下。该视频还有Part2，讲解比较复杂的如何删除一个二叉树中的节点。
以下是我对这个视频中内容的整理：
- 二叉树是树的子类，特点是左子节点的数据比根节点的数据小，右子节点的数据比根节点小
- 二叉树和数列，链表等一样，是一种数据结构
- 为什么使用二叉树。因为数列在数据的插入、删除时慢，链表在数据的查找时慢，而使用二叉树，任何操作的时间复杂度都是O(logN)。因此二叉树适用于对数据有多种类型的操作的情况
//节点类
class Node {
/*
视频中老外在节点中定义了两个field。
一个是key，类似数据库中的“主键”字段，相当于一个节点的唯一id
一个是data（事实上变量名可随意），相当于实际需要树来存储的数据
*/
int key;
String data;
Node left;
Node right;
//构造函数
Node(int key,String data){
this.key = key;
this.data = data;
}
//用于打印节点信息，方便debug的一个方法
public String toString(){
return this.data + " has a key " + this.key;
}
}
//二叉树类
public class BinaryTree{
//树的根节点
private Node root;
public void addNode(int key, String data){
Node newNode = new Node(key, data);
//创建好一个新节点后，关键在于如何找到增加此节点的位置
//当二叉树为空时，第一次addNode应该加在根节点上
if(root == null){
root = newNode;
return;
}
//创建两个Node变量，一个是当前正在查看的节点（初始化为根节点），一个是父节点
Node focusedNode = root;
Node parent;
while(true){ //使用一个无限循环，在确定可以增加节点时跳出即可
parent = focusedNode;
if(key < parent.key){
//如果新节点的key小于父节点的key，则查看左子节点
focusedNode = focusedNode.left;
if(focusedNode == null){
//如果左子节点有空位，则插入
parent.left = newNode;
return; //跳出循环
}
}else{
//如果新节点的key大于或等于父节点的key，则查看右子节点
//这里把大于和等于的情况放在一起
//这说明如果新节点的key和某一级的父节点的key相同
//那么总会向右查找子节点上的空位
focusedNode = focusedNode.right;
if(focusedNode == null){
//如果右子节点有空位，则插入
parent.right = newNode;
return;//跳出循环
}
}
}
}
//以下三个是遍历树的方法，无返回值，参数为遍历的起点节点。
//三个遍历法区别仅仅在于访问focusedNode的信息的语句和遍历语句的顺序的不同
//遍历树的方法之一：In-order traversal
public void inOrderTraverse(Node focusedNode){
if(focusedNode != null){
//在向下找的过程中，优先寻找左边的节点（遍历的结果会从key最小的开始）
inOrderTraverse(focusedNode.left);
//同时打印上一级节点的信息
System.out.println(focusedNode.toString());
inOrderTraverse(focusedNode.right);
}
}
//遍历树的方法之二：Pre-order traversal
public void preOrderTraverse(Node focusedNode){
if(focusedNode != null){
//在向下找的过程中，首先打印上一级节点的信息
System.out.println(focusedNode.toString());
//再寻找左边的节点
inOrderTraverse(focusedNode.left);
inOrderTraverse(focusedNode.right);
}
}
//遍历树的方法之三：Post-order traversal
public void postOrderTraverse(Node focusedNode){
if(focusedNode != null){
//在向下找的过程中，首先查找两边节点
inOrderTraverse(focusedNode.left);
inOrderTraverse(focusedNode.right);
//最后打印出上一级节点的信息
System.out.println(focusedNode.toString());
}
}
//根据key，在二叉树中寻找指定的节点
public Node findNode(int key){
Node focusedNode = root; //从根节点开始寻找
while(focusedNode.key != key) {
if (key < focusedNode.key) {
focusedNode = focusedNode.left;
} else {
focusedNode = focusedNode.right;
}
//如果找至某处，既无左子节点也无右子节点，则返回空
if (focusedNode == null) {
return null;
}
}
return focusedNode;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.addNode(50, "a");
tree.addNode(25, "i");
tree.addNode(75, "u");
tree.addNode(15, "e");
tree.addNode(30, "o");
tree.postOrderTraverse(tree.root);
}
}- 如何删除二叉树中的一个节点