树的概述
为什么需要树这种数据结构
我们之前学过数组和链表
数组的查找快,但是对于增加值的时候要整体移动到新数组上,效率低。
链表这种数据结构插入的时候十分快,但是在检索的时候就比较慢了。
虽然我们在插入和检索的时候要根据需求来选择数据结构。
但是我们还是在想,有没有一种数据结构插入又快,检索又快。其实是有的,这就是我们的树。
树这种数据结构可以提高数据的存储和查找的效率,比如利用二叉排序树,既可以保证数据的检索,同时可以保证数据的插入、删除、修改的速度。
树的基本术语
树的基本术语
概念 |
意义 |
节点 |
节点就是对象,其中A、B、C、D、E、F、G、H都是节点 |
父节点 |
D就是H的父节点、B是D的父节点、A是B的父节点。 也就是说,节点的上一级叫做父节点 |
子节点 |
和父节点的概念对应,父节点的下一级叫做子节点。 B是A的子节点、D是B的子节点、H是D的子节点。 |
根节点 |
没有父节点的节点就叫做根节点 |
叶子节点 |
没有子节点的节点就叫做叶子节点 |
节点的权 |
就是节点的值 |
路径 |
从根节点到该节点的路线。比如找到D应该A–>B–>D |
层 |
比如A就是第一层,B和C位于第二层,DEFG位于第三层,H位于第四层 |
子树 |
我们看到,在虚线的三角形中,D和E两者也可以叫做子树。 可以叫做A的子树,可以叫做B的子树。在这颗子树中,D为根节点。 |
树的高度 |
一颗树有多少层 |
森林 |
多颗子树构成森林 |
二叉树
二叉树的概念
二叉树的意思就是,一个节点只能有两个子节点,并且子节点要明确分为左子节点和右子节点
假如二叉树的所有叶子节点都==在最后一层或者倒数第二层==,并且==最后一层的叶子节点在左边连续==,==倒数第二层的叶子节点在右边连续==,我们称为==完全二叉树==
连续这个概念很容易让人懵逼,连续的意思就是说每一个叶子节点都挨着,比如71挨着61、61挨着15。
但是假如把61这个节点删除,那么71不挨着15。假如把71去掉,剩下61和15,那也不叫连续。
假如我去掉81,那也不叫连续。
假如二叉树的所有叶子节点==都在最后一层==,并且节点的总数为2^n^-1(n为层数),则我们称为==满二叉树==
满二叉树是一种特殊的完全二叉树
对于完全二叉树也可以这样想:完全二叉树去掉倒数第一层的叶子节点,剩下的也是一颗满二叉树
前序遍历、中序遍历、后序遍历
前序遍历
先遍历父节点,再遍历左子树,再遍历右子树
中序遍历
先遍历左子树,再遍历父节点,再遍历右子树
后序遍历
先遍历左子树,再遍历右子树,再遍历父节点
总而言之,只需要看父节点的输出位置就可以判断是哪种遍历了,而左边肯定先遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
|
class HeroNode {
private Integer id; private String name;
private HeroNode left; private HeroNode right;
public HeroNode() { }
public HeroNode(Integer id, String name) { this.id = id; this.name = name; }
public void preOrder() {
System.out.println(this);
if (this.left != null) { this.left.preOrder(); }
if (this.right != null) { this.right.preOrder(); } }
public void infixOrder() { if (this.left != null) { this.left.preOrder(); }
System.out.println(this);
if (this.right != null) { this.right.preOrder(); } }
public void postOrder() { if (this.left != null) { this.left.preOrder(); }
if (this.right != null) { this.right.preOrder(); }
System.out.println(this); }
}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| class BinaryTree {
private HeroNode root;
public BinaryTree() { }
public BinaryTree(HeroNode root) { this.root = root; }
public void preOrder() { if (this.root != null) { this.root.preOrder(); return; } System.out.println("二叉树为空,不可遍历"); }
public void infixOrder() { if (this.root != null) { this.root.infixOrder(); return; } System.out.println("二叉树为空,不可遍历"); }
public void postOrder() { if (this.root != null) { this.root.postOrder(); return; } System.out.println("二叉树为空,不可遍历"); }
}
|
二叉树的前序查找、中序查找、后序查找
查找其实和遍历一模一样,只不过查找是找到之后就结束查找
现在我们搞这样一个关系:
假如我现在要查询编号为5的节点,也就是关胜,那么以前序查找为例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| public class BinaryTreeDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree();
HeroNode one = new HeroNode(1, "宋江"); HeroNode two = new HeroNode(2, "吴用"); HeroNode three = new HeroNode(3, "卢俊义");
one.setLeft(two); one.setRight(three);
HeroNode four = new HeroNode(4, "林冲"); HeroNode five = new HeroNode(5, "关胜");
three.setLeft(five); three.setRight(four);
binaryTree.setRoot(one);
HeroNode heroNode = binaryTree.preOrderSearch(5);
if (heroNode != null) { System.out.println(heroNode.toString()); } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class BinaryTree {
private HeroNode root;
public BinaryTree() { }
public BinaryTree(HeroNode root) { this.root = root; }
public HeroNode preOrderSearch(Integer id) {
return this.root.preOrderSearch(id); }
}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
|
class HeroNode {
private Integer id; private String name;
private HeroNode left; private HeroNode right;
public HeroNode() { }
public HeroNode(Integer id, String name) { this.id = id; this.name = name; }
public HeroNode preOrderSearch(Integer id) {
if (this.id.equals(id)) { return this; }
HeroNode mid = null;
if (this.left != null) { mid = this.left.preOrderSearch(id); } if (mid != null) { return mid; }
if (this.right != null) { mid = this.right.preOrderSearch(id); }
return mid; } }
|
二叉树的删除
我们现在规定:
1、假如删除的节点是一个叶子节点,那么直接删除
2、假如删除的节点是一个非叶子节点,那么删除该节点和它所代表的子树
现在我们先来一个比较简单的,等到后面讲其他树的时候,我们再具体来讲应该如何删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| class BinaryTree {
private HeroNode root;
public BinaryTree() { }
public BinaryTree(HeroNode root) { this.root = root; }
public void preOrder() { if (this.root != null) { this.root.preOrder(); return; } System.out.println("二叉树为空,不可遍历"); }
public boolean delNode(Integer id) {
if (this.root == null) { System.out.println("二叉树为null"); }
if (this.root.getId().equals(id)) { this.root = null; return true; }
return this.root.delNode(id); }
}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
|
class HeroNode {
private Integer id; private String name;
private HeroNode left; private HeroNode right;
public HeroNode() { }
public HeroNode(Integer id, String name) { this.id = id; this.name = name; }
public void preOrder() {
System.out.println(this);
if (this.left != null) { this.left.preOrder(); }
if (this.right != null) { this.right.preOrder(); } }
public boolean delNode(Integer id) {
if (this.left != null && this.left.id.equals(id)) { this.left = null; return true; }
if (this.right != null && this.right.id.equals(id)) { this.right = null; return true; }
boolean flag = false;
if (this.left != null) { flag = this.left.delNode(id); }
if (flag) { return true; }
if (this.right != null) { return this.right.delNode(id); }
return false; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| public class BinaryTreeDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree();
HeroNode one = new HeroNode(1, "宋江"); HeroNode two = new HeroNode(2, "吴用"); HeroNode three = new HeroNode(3, "卢俊义");
one.setLeft(two); one.setRight(three);
HeroNode four = new HeroNode(4, "林冲"); HeroNode five = new HeroNode(5, "关胜");
three.setLeft(five); three.setRight(four);
binaryTree.setRoot(one);
binaryTree.preOrder();
System.out.println("----------------删除----------------"); binaryTree.delNode(5);
binaryTree.preOrder();
} }
|
顺序存储二叉树
概念
什么是顺序存储二叉树
我们的树其实可以转换为数组,而数组也可以转换为树
上图中是树转换为数组的形式,也可以叫做数组转换为树的形式
现在有一个需求:我将树转换为数组,仍然可以依照某几种规则来进行前序遍历,中序遍历和后序遍历
那么能够实现上面这种需求的,就是顺序存储二叉树
顺序存储二叉树的特点
1、顺序二叉树通常只考虑完全二叉树
2、第n个元素的左子节点的下标为 2 * n + 1
(n在这里指的是转换为数组之后的下标,也就是从0开始的数组节点)
3、第n个元素的右子节点的下标为2 * n + 2
4、第n个元素的父节点的下标为 (n - 1) / 2
举个例子,还是我们刚才的图
在图中,树的下标为0-6,那么我们举一个例子,就以下标为1,值为2的树节点为例子:
第1个元素(也就是下标为1的节点)
左子节点为 2 * 1 + 1 = 3
,也就是下标为3,值为4的节点
右子节点为 2 * 1 + 2 = 4
,也就是下标为4,值为5的节点
父节点为( 2 - 1 ) / 2 = 0
,也就是根节点
代码实现
需求:现在有一个数组:int[] arr = {1,2,3,4,5,6,7}
,要求以二叉树前序遍历的方式进行遍历
结果应该是:1、2、4、5、3、6、7
上代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class ArrayBinaryTree {
int[] arr;
public ArrayBinaryTree(int[] arr) { this.arr = arr; }
public void preOrder(int index) { if (arr == null || arr.length <= 0) { System.out.println("数组中必须有值!"); return; }
int left = 2 * index + 1;
System.out.print(arr[index] + " ");
if (left <= arr.length - 1) { preOrder(left); }
int right = 2 * index + 2; if (right <= arr.length - 1) { preOrder(right); } }
}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| package com.howling;
public class ArrayBinaryTreeDemo { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrayBinaryTree tree = new ArrayBinaryTree(arr);
tree.preOrder(0); } }
|
线索化二叉树
线索化二叉树概述
问题描述
我们先来看一个数列:{1,3,6,8,10,14}
,我们将这个数列构建成一个线索化二叉树,如图:
我们当我们使用中序遍历的时候,发现它的输出是这样的:8、3、10、1、14、6
我们发现对于6、8、10、14
这几个节点的左右指针并没有完全利用上,这在一定程度上就造成了一种资源的浪费
假如我们想要充分地利用各个节点的左右指针,让各个节点可以指向自己的前后节点怎么办?
这就是线索二叉树的作用
线索二叉树
1、现在有一个完全二叉树,一共有n个节点,那么对于这棵树来讲,它的空指针域为n+1
比如上面这个树,它的节点一共有六个,但是它的空指针域有7个
2、一个节点的前一个节点称为前驱结点
,一个节点的后一个节点称为后继结点
3、假如我们可以利用这些空指针域,存放当前节点在某种遍历顺序下的前驱结点和后继结点的指针,那么这种附加的指针就叫做线索
,这种行为我们称之为线索化
我们可以看到,在上图中,假如我们以中序遍历的方式去遍历这个树,那么对于节点8、3、10,它们遍历的顺序应当是8、3、10,那么节点8的右子节点(后继结点)指向3,而节点10的左子节点(前驱结点)指向3,那么这种前驱节点和后继结点就叫做线索,这种行为叫做线索化
4、附加上了线索的二叉链表我们称为线索链表
,对应的二叉树我们称为线索二叉树
。根据线索性质的不同,我们可分为前序线索二叉树
,中序线索二叉树
,后序线索二叉树
线索化二叉树应用
现在有一棵树,要求我们进行中序线索化
首先我们要明白一件事情:这棵树的中序遍历之后应当是什么样子,它的中序遍历应该是:8、3、10、1、14、6
那么我们按照前面讲到的知识,进行线索化,将它变为中序线索二叉树
1、对于8来讲,它没有前驱节点,后继结点是3
2、对于10来讲,它的前驱节点就是3,后继结点就是1
3、对于14来讲,它的前驱节点是1,后继结点是6
4、对于6来讲,它的前驱节点是14,没有后继结点
那么它的中序线索化应当是这样子的:
我们发现一个问题:
当线索化二叉树之后,节点的left和right,有可能是前驱和后继节点,也有可能是左右子节点
线索化二叉树应用
因为线索化二叉树可能有些难以理解,所以我们根据上图来走一遍基本的代码实现
还是之前的图片
1、准备三个指针:
- 一个指针是pre,指向当前节点的上一个指针
- 一个指针是leftType,用于标识当前节点的left节点是前驱节点还是左子树
- 一个指针是rightType,用于标识当前节点的right节点是后继结点还是右子树
2、在一开始pre为null,当前指针为8
3、pre为8,当前节点为3
- left和right都不为null–>不进行处理
- pre指向当前节点,当前节点指向下一个节点
4、pre为3,当前节点为10
- 判断pre是否为null–>pre不为null–>判断pre的right是否为null–>不为null,不进行处理(不能形成pre的后继结点,因为)
- 判断当前节点的left是否为null–>left为null,指向pre
- pre指向当前节点,当前节点指向下一个节点
5、……
思路有了就行,文字太多不讲了,直接上代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class HeroNode { private Integer id;
private Integer leftType = 0; private Integer rightType = 0;
private HeroNode left; private HeroNode right;
public HeroNode(Integer id) { this.id = id; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| class ThreadedBinaryTree {
private HeroNode root;
private HeroNode pre;
public ThreadedBinaryTree(HeroNode root) { this.root = root; }
public void threadNodes(HeroNode node) {
if (node == null) { return; }
threadNodes(node.getLeft());
if (pre != null && pre.getRight() == null) { pre.setRight(node); pre.setRightType(1); }
if (node.getLeft() == null) { node.setLeft(pre); node.setLeftType(1); }
pre = node; threadNodes(node.getRight()); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| public class ThreadedBinaryTreeDemo { public static void main(String[] args) { HeroNode root = new HeroNode(1);
HeroNode three = new HeroNode(3); HeroNode six = new HeroNode(6);
HeroNode eight = new HeroNode(8); HeroNode ten = new HeroNode(10); HeroNode fourteen = new HeroNode(14);
root.setLeft(three); root.setRight(six);
three.setLeft(eight); three.setRight(ten);
six.setLeft(fourteen);
ThreadedBinaryTree tree = new ThreadedBinaryTree(root); tree.threadNodes(root);
System.out.println(eight.getRightType() + "--" + eight.getRight());
System.out.println(ten.getLeftType() + "--" + ten.getLeft());
System.out.println(ten.getRightType() + "--" + ten.getRight()); } }
|
遍历线索化二叉树
线索化二叉树因为重新排列了我们节点的左右指针,所以按照以前的方法遍历肯定是不行的,所以我们需要来一个新的遍历方式,并且遍历之后的结果应当是你线索化之前的结果,举个例子:我们中序线索化的二叉树,那么我们遍历之后的结果应该和中序遍历二叉树的结果一模一样
还是以这张图为例子:
中序遍历的结果应当为:8、3、10、1、14、6
,那么我们进行线索化二叉树的遍历之后,应当和这个结果完全一致
还是先说一下基本的思路:
1、在这颗二叉树上向左寻找(因为是中序遍历),找到一个当前节点的左节点的leftType==1的节点
2、打印该节点,向右寻找节点,只要rightType==1,那么就打印,然后继续重复步骤2
3、到达第三步说明当前所在节点的rightType==0,那么令当前节点为右节点,回到第一步
4、进入第四步说明我们的线索二叉树全部都遍历完成了
对于线索二叉树我只能说一句鬼才设计,这玩意儿可比递归的效率高多了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class HeroNode { private Integer id;
private Integer leftType = 0; private Integer rightType = 0;
private HeroNode left; private HeroNode right;
public HeroNode(Integer id) { this.id = id; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| class ThreadedBinaryTree {
private HeroNode root;
private HeroNode pre;
public ThreadedBinaryTree(HeroNode root) { this.root = root; }
public void threadOrder(HeroNode node) {
if (node == null) { return; }
HeroNode mid = node;
while (mid != null) { while (mid.getLeftType() != 1) { mid = mid.getLeft(); }
System.out.println(mid);
while (mid.getRightType() == 1) { mid = mid.getRight(); System.out.println(mid); }
mid = mid.getRight(); } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| public class ThreadedBinaryTreeDemo { public static void main(String[] args) { HeroNode root = new HeroNode(1);
HeroNode three = new HeroNode(3); HeroNode six = new HeroNode(6);
HeroNode eight = new HeroNode(8); HeroNode ten = new HeroNode(10); HeroNode fourteen = new HeroNode(14);
root.setLeft(three); root.setRight(six);
three.setLeft(eight); three.setRight(ten);
six.setLeft(fourteen);
ThreadedBinaryTree tree = new ThreadedBinaryTree(root); tree.threadNodes(root);
tree.threadOrder(root); } }
|