从本节开始我们开始树的学习,这也是数据结构和算法难点的地方,当然如果学好树这个结构,对于我们个人成长是有很大的帮助,首先我们的最开始来学习二叉树,那么介绍来首先介绍下二叉树.
二叉树的概念
关于二叉树的概念是很好理解的,二叉树是一种比较特殊的树结构,其组成有一个根(root)节点,而根节点至多有左右两个子节点,其他们共同组成的一种形式我们称之为二叉树,来看下如图:
如上图就是常见二叉树的形式,我们可以将它类比于生活中一颗倒立的只有二个分支的树,这样可能更容易理解些,了解了什么是二叉树我们来整体介绍下它:
二叉树的介绍
首先我们来看张图,稍微比上述图复杂一点:
简单的对其进行介绍:
- 其中A表示我们这颗树的根节点
- H E F G,我们发现是没有子节点的,因此我们称其为叶子节点
- B C 和 D E 和 F G 称其为兄弟节点,因为他们在同一个级别
- 我们可以发现的是从A -H整个数的深度为4层,也就是图中所示
- 还有图中三角形的部分称其为子树
那么关于树的常见介绍就到这里,其实二叉树还有衍生出来的满二叉和平衡二叉树等,这里就不在说了,大家可以自己去了解下,我们重点来学习二叉树的遍历.
二叉树的遍历
二叉树的遍历一般都是前序遍历 中序遍历和后续遍历,关于二叉树的这三种遍历我们来通过具体的案例来分析,同时也通过代码来实现该过程,首先来看我们的实际需求:
要求: 利用二叉树的遍历对该图的二叉树进行前序和中序以及后序的遍历操作,我们首先来看看前序遍历
- 前序遍历:
前序遍历的规则如下:
- 先输出父节点,然后遍历左子树和有子树的节点
具体操作如下:
- 先输出我们上图中的根节点(也就是宋江)
- 如果左子树不为null,则采用递归继续前序遍历
- 如果右子树不为null,则采用递归继续前序遍历
代码实现过程,我们基于上述的分析,首先确定了我们需要创建一颗二叉树,其次是节点等,来看公共的代码:
- 节点的创建
//创建HeroNode节点
class HeroNode{
private int no; //编号
private String name;
private HeroNode left;//默认为null
private HeroNode right;//默认为null
//构造器
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
上述代码只是公共的节点创立的过程,我们来看前序遍历的代码,将代码写在HeroNode即可:
//编写前序遍历的方法
//前序遍历的规则:
//1先输出根节点
//2.输出左子树的节点
//3. 输出右子树的节点
public void preOrder(){
//1.先输出根节点
System.out.println(this);
//2.输出左子树的节点
if (this.left !=null){
this.left.preOrder();
}
//3. 输出右子树的节点
if (this.right !=null){
this.right.preOrder();
}
}
- 接着我们来完成公共代码也就是二叉树的定义,代码如下:
''''
//二叉树的定义
class BinaryTree{
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
//前序遍历
public void preOrder(){
if (root !=null){
this.root.preOrder();
}else {
System.out.println("二叉树为null");
}
}
为啥这样写了,注意:不管是前序还是中序以及后序遍历,我们所有的出发点都是二叉树的根节点开始的,这点大家要明白,可以看到的是我们在二叉树的定义里面调用了节点(HeroNode)类的前序遍历方法,来看下测试代码:
public static void main(String[] args) {
//测试
BinaryTree binaryTree = new BinaryTree();
//节点的创建
HeroNode root = new HeroNode(1, "宋江");
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊义");
HeroNode node4 = new HeroNode(4, "林冲");
//设置二叉树跟节点
binaryTree.setRoot(root);
//手动创建二叉树
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
System.out.println("前序遍历:");
binaryTree.preOrder();
这里为了方便简单,我采用手动创建节点和设置二叉树和根节点的关系,以后我们可以通过递归的方式来创建的,不过不影响我们的操作,大概我们按照之前的那种分析来猜测下输出的结果: 1 2 3 4,我们来看测试结果吧,如图所示:
从图中的结果来看是按照我们预想的输出结果接着来看中序遍历
中序遍历规则:
- 先遍历左子树,在输出根节点,最后遍历右子树
具体的操作如下:
- 如果左子树不为null,则采用递归继续中序遍历
- 接着是输出我们上图中的根节点(也就是宋江)
- 如果右子树不为null,则采用递归继续中序遍历
来看代码实现,首先来看HeroNode 的实现过程:
//中序遍历
public void midOrder(){
//1.先输出左子树的节点信息
if (this.left !=null){
this.left.midOrder();
}
//2.输出父节点信息
System.out.println(this);
//3.输出右子树的节点信息
if (this.right !=null){
this.right.midOrder();
}
}
上述是HeroNode 的代码实现,接着我们来看看二叉树(BinaryTree )中是如何调用的实现过程:
public void midOrder(){
if (this.root !=null){
this.root.midOrder();
}else {
System.out.println("二叉树为null");
}
}
还是利用上述的公共测试代码,我们直接看测试结果,如图所示:
可以自己分析下,然后跟上述结果进行对比,最后我们来看看后序遍历
后序遍历规则:先遍历左子树,在遍历右子树,最后输出根节点
操作规则如下:
- 如果左子树不为null,则采用递归继续后序遍历
- 如果右子树不为null,则采用递归继续后序遍历
- 最后是输出我们上图中的根节点(也就是宋江)
来看代码实现,首先来看HeroNode 的实现过程:
//后序遍历
public void postOrder(){
//先输出左子树的节点信息
if (this.left !=null){
this.left.postOrder();
}
//2.输出右子树的节点信息
if (this.right !=null){
this.right.postOrder();
}
//3.输出根节点的信息
System.out.println(this);
}
上述是HeroNode 的代码实现,接着我们来看看二叉树(BinaryTree )中是如何调用的实现过程:
public void postOrder(){
if (this.root !=null){
this.root.postOrder();
}else {
System.out.println("二叉树为null");
}
}
还是利用上述的公共测试代码,我们直接看测试结果,如图所示:
上述就是关于二叉树的三种遍历的基本操作实现过程,主要的是大家要理解二叉树这个树结构的特点,代码实现很简单,唯一的区别是root节点的输出位置的变化.
