【数据结构与算法】【数据结构】详解二叉树
一、什么是二叉树
树是由许多节点使用使用一条条边连接而成的，一个节点可以由许多子节点，如果一个节点只有两个子节点，那么这种树就叫做二叉树，二叉树是树中最简单的一种数据结构存在。
二、为什么需要二叉树
除了二叉树这种数据结构，我们最先熟悉的数据结构有：数组和链表，这两个数据结构是我们经常使用的；但是在我们使用的过程中，会发现数组和链表的优缺点：
- 数组：有序数组查找某个元素会很快（使用二分查找法，其时间复杂度为O(logN)），但插入和删除某个元素很慢；无序数组除了插入某个元素很快之外，其余操作都很慢。
- 链表：插入和删除都很快（其时间复杂度为O(1)），只需变化某个元素的引用即可，但查找效率很慢。
从上面可以看到数组和链表的优缺点若是能互补，那么这种数据结构就能应对各种场景而不用考虑效率问题；二叉树就是集合数组和链表这两种数据结构的优点：
二叉树的一个节点的左节点的数据值比父节点的数据值小，右节点比父节点的数据值大（类似有序数组），这样搜索就快；插入和删除也只需要改变边引用即可，也很快。
三、二叉树的特征
二叉树是树结构中的一种特例，二叉树的特征也是树的特征，二叉树是由根、路径、父节点、子节点、叶节点、层和子树等特征构成。
根：树的顶端节点就称为根
路径：连接两个节点的边就叫做路径
父节点：除了根节点外，还存在其他节点，并且这些节点还存在子节点，那么这些节点就称之为父节点。
子节点：每个节点都可以向下有一个或者两个节点，那么这些节点就称之为子节点。
叶节点：没有子节点的节点就称之为叶节点
层：层的划分是根据节点下面还有没有子节点，有子节点，那么子节点就划分为一层，以此类推。
子树：有根就可以看成一棵树，每个节点都可以看做是子树的根，该节点根它下面的节点共同构成一棵树。
特别说明：上面的特征概念都是相对而言的，只需要理解即可。重点是节点概念，节点就是接下来我们需要用来存储数据的，保存的数据可以是基本数据类型也可以是对象引用类型等等。我们根据二叉树的每个节点最多只有两个子节点（称之为左节点和右节点）的特征去操作二叉树。
重要特征：二叉树的一个节点的左节点的数据值比父节点的数据值小，右节点比父节点的数据值大
四、二叉树的如何实现
实现一颗二叉树，首先需要定义一个Node对象，用来表示一个个节点。
class Node { // 节点对象
public int value;
public Node leftNode;
public Node rightNode;
}
public class Tree {// 二叉树对象
private Node root;//根节点
public Tree(Node root) {
this.root = root;
}
}还有二叉树还需要具备基本操作：查找节点、插入节点和删除节点基本操作
插入节点：
插入一个节点数据需要分配保存位置，从根节点开始，分别比较现有节点的数据值，如果比该节点小就往左节点继续比较，如果比该节点大就往右节点继续比较，直到比较的节点是叶节点，那下面就是插入的位置了。
public void insert(int value) {
Node newNode = new Node();
newNode.value = value;
if (root == null) {
root = newNode;
return;
}
Node currentNode = root;
Node parentNode;
while (true) {
parentNode = currentNode;
if (value < currentNode.value) {
currentNode = currentNode.leftNode;
if (currentNode == null) {
parentNode.leftNode = newNode;
return;
}
} else {
currentNode = currentNode.rightNode;
if (currentNode == null) {
parentNode.rightNode = newNode;
return;
}
}
}
}
查找节点：
从根节点开始分别左右节点搜索值，如果相等则返回，否则返回null
public Node find(int value) {
Node currentNode = root;
while (currentNode.value != value) {
if (value < currentNode.value) {
currentNode = currentNode.leftNode;
} else {
currentNode = currentNode.rightNode;
}
if (currentNode == null) {
return null;
}
}
return currentNode;
}删除节点：
删除节点比较复杂，涉及到三种情况：
- 删除的节点是叶节点，直接删除引用即可
- 删除的节点只有一个子节点，将删除后的位置用子节点代替即可
- 删除的节点有两个子节点，需要寻找后继节点代替删除节点的位置
删除节点的操作很复杂，如果我们没必要的话就不要真正的删除节点，只是在每个节点上放置一个delete的标志位，如果删除某个节点，就直接find到这个节点，将这个标志位置为true即可，完成删除的操作。真正删除节点的话需要花费的代价有点大，例如公司的员工离职，需要删除这个员工，只需要将delete标记为true即可，还可以保留员工档案，这样比较划算。
public boolean delete(int value) {
Node currentNode = root;
Node parentNode = root;
boolean isLeftNode= true;
while (currentNode.value != value) {
parentNode = currentNode;
if ( value < currentNode.value) {
isLeftNode = true;
currentNode = currentNode.leftNode;
} else {
isLeftNode = false;
currentNode = currentNode.rightNode;
}
if (currentNode == null) {
return false;
}
// 第一种情况：删除的节点为叶节点
if (currentNode.leftNode == null && currentNode.rightNode == null) {
if (currentNode== root) {
root = null;
return true;
}
if (isLeftNode) {
parentNode.leftNode = null;
return true;
}
parentNode.rightNode = null;
return true;
}
// 第二种情况：删除的节点只有一个节点。
if (currentNode.rightNode == null) {//只有左节点
if (currentNode == root) {
root = currentNode.leftNode;
return true;
}
if (isLeftNode) {
parentNode.leftNode =currentNode.leftNode;
return true;
}
parentNode.rightNode = currentNode.leftNode;
return true;
}
if (currentNode.leftNode == null) {//只有右节点
if (currentNode == root) {
root = currentNode.rightNode;
return true;
}
if (isLeftNode) {
parentNode.leftNode =currentNode.rightNode;
return true;
}
parentNode.rightNode = currentNode.rightNode;
return true;
}
//第三种情况：删除的节点两个节点
Node next = getNextNode(currentNode);
if (currentNode == root) {
root = next;
return true;
}
if (isLeftNode) {
parentNode.leftNode = next;
return true;
}
parentNode.rightNode = next;
next.leftNode = currentNode.leftNode;
return true;
}
return false;
}
// 获取后继节点
public Node getNextNode(Node delNode){
Node parent = delNode;
Node next = delNode;
Node current = delNode.rightNode;
while (current != null) {
parent = next;
next = current;
current = current.leftNode;
}
if (next != delNode.rightNode) {
parent.leftNode = next.rightNode;
next.rightNode = delNode.rightNode;
}
return next;
}
遍历节点：
有三种简单的方法遍历树，基本方法就是采用递归思想去遍历
前序遍历
-
- 访问该节点
- 调用自身遍历节点的左子树
- 调用自身遍历节点的右子树
public void preOrder(Node localNode) {
if (localNode != null) {
System.out.println(localNode.value);
preOrder(localNode.leftNode);
preOrder(localNode.rightNode);
}
}中序遍历
-
- 调用自身遍历节点的左子树
- 访问该节点
- 调用自身遍历节点的右子树
public void inOrder(Node localNode) {
if (localNode != null) {
inOrder(localNode.leftNode);
System.out.println(localNode.value);
inOrder(localNode.rightNode);
}
}后序遍历
-
- 调用自身遍历节点的左子树
- 调用自身遍历节点的右子树
- 访问该节点
public void afterOrder(Node localNode) {
if (localNode != null) {
afterOrder(localNode.leftNode);
afterOrder(localNode.rightNode);
System.out.println(localNode.value);
}
}五、二叉树的优缺点
优点就是：二叉树查找、插入、删除的效率都是O(logN);
缺点的话就是比较复杂。其他一切还好，想要好用的数据结构那必须是需要付出代价的。
- 点赞
- 收藏
- 关注作者
评论（0）