6 二叉树
第025课 算法及数据结构
这是一棵很简单的树.
树主要是由结点及结点之间得关系组 成的
1
2
3
下面给出一些相关得概念
4
5
6
7
8
第025课 算法及数据结构
6 二叉树
6.1 树的相关概念
二叉树: 二叉树或者是一棵 空树 ，或者 是一棵由一个 根结 点和两棵互 不相交的分别称根的 左子树 和 右子树 所组成的 非空树 ，左子 树和右子树又同样都是一棵二叉 树. 右图为一棵二叉树
public MyTree() { super(); root = null;
}
第025课 算法及数据结构 6 二叉树
6.3 二叉树的插入
二叉树的插入是保证起有序性的重要环节.如果随意的插入则无法保证其 有序性.
二叉树的顺序 一棵有序的二叉树叫搜索二叉树.其定义是根要大于左子树所有结点,小于右 子树所有结点.其子树仍然遵循这个规律.
2
1 3
于是将7加入5的右子树中
1
5
1 6
7
第025课 算法及数据结构
6 二叉树
6.3 二叉树的插入
这是插入结点代 码的实现
其中 subtreeRoot是 要查询子树的根
新结点在当前 结点的左子树
新结点在当前 结点的右子树
newNode是要 插入的结点
private void insertNode(
专业教程
理论讲解部分
Ver3.1
第025课 算法及数据结构 概述：
➢ 二叉树的相关概念 ➢ 二叉树的实现
• 重点：
➢ 二叉树的实现
• 难点：
➢ 二叉树的实现
6 二叉树
第025课 算法及数据结构
二叉树综合了有序数组与链表得优点. 有序数组具有较快得查找速度,链表具有非常好得插入删除效率. 树结合了两者得有点,使得它具有很高得插入 删除及查找得效率. 它得实现与其结构密切相关,下面我们来看看它的结构.
下节课介绍树的删除 查询 及遍历
第025课 算法及数据结构
• 小结：
➢ 树的相关概念 ➢ 树的建立 ➢ 插入结点
第025课 算法及数据结构
小测验（单选题）：
1、树集成了哪两种结构的优点() A) 队列 B)有序数组 C)栈 D)链表
2、搜索树的规则是() A)左子树>右子树>根 B)左子树<右子树<根 C)左子树<根<右子树 D)左子树<根>右子树
private class Node{ int key; int value; Node left; Node right;
}
第025课 算法及数据结构 6 二叉树
6.2 二叉树的建立
当我们拥有了结点以后,就可以着手创建我们的树了.
一颗数最特殊的结点就是它的根结点,当拥有了根结点就意味着你拥有 了整棵树. 所以我们要用一个变量来保存这个非常重要的根.
左结点 非空继 续查询
}
}else{
右结点
if(current.right == null){
空加入
current.right = newNode; return; }else{ current = current.right;
右结点 非空继 续查询
}}}}
6 二叉树
第025课 算法及数据结构
此时,我们可以通过使用结点Node来建立一棵树. 并且,可以按照搜索树的要求调用插入insertNode()函数来使树成长.
我们要建立的便是一棵这样的搜索二叉树.
第025课 算法及数据结构6 二树6.3 二叉树的插入
如图,该树便是一棵搜索二叉树. 下面我们要讨论如何将7插入该树.
1 0
2
1 3
首先我们要访问根结点,判断这个7应
1
该放在其左子树还是右子树.
7<10 ,所以 7 应该放在左子树中.
5
1 6
第025课 算法及数据结构
Node subtreeRoot,Node newNode){
Node current = subtreeRoot;
while(true){
if(newNode.key<current.key){ 左结点
if(current.left == null){
空加入
current.left = newNode; return; }else{ current = current.left;
6 二叉树
6.3 二叉树的插入
1 0
然后,对根的左子树进行检查.判断 该子树是否为空,若空则将7加入.非 空则继续判断在该子树中的位置.
根的左子树非空且值为2,后判断 2<7,则7应该在该子树的右子树中.
2
1 3
1
5
1 6
第025课 算法及数据结构
6 二叉树
6.3 二叉树的插入
1 0
以次继续,直到判断到5后,7应该在5 的右子树中,且5的右子树为空.
按照由高到低的顺序遍历的.或者称为
广度优先遍历.
24
层: 树中从根开始计算的 “辈分”.
1
2
3
5
6
第025课 算法及数据结构 6 二叉树
6.2 二叉树的建立
实现二叉树首先就要实现它的 结点.
它的每一个结点除了要保存相 应的数据之外,还要保存其子 结点的引用.
其数据需要两个域,一个保存键 值,另一个保存该键值所对应的 数据.
3、在树的插入中,我们使用的是非递归方法.考虑如何使用非递归 方法实现
第025课 算法及数据结构 • 课后作业：
将树的建立 插入重新实现一次. 注意插入操作的操作顺序.
2
3
子树: 每一个结点都可以看作是其子
孙结点的根.这样将其与其子孙
4
5
6
结点的集合称为子树
图中2,4,5可以看作是一棵子树.
第025课 算法及数据结构
6 二叉树
6.1 树的相关概念 0
遍历: 根据某种规则,对树中所有的结点
全部访问一次称作一次遍历.
1
例如:1,2,3,4,5,6 就是一次遍历.它是
3、在树的插入中,我们使用的是非递归方法.考虑如何使用非递归 方法实现
第025课 算法及数据结构
小测验（单选题答案）：
1、树集成了哪两种结构的优点(BD) A) 队列 B)有序数组 C)栈 D)链表
2、搜索树的规则是(c) A)左子树>右子树>根 B)左子树<右子树<根 C)左子树<根<右子树 D)左子树<根>右子树
4
1
2
3
5
6
第025课 算法及数据结构
6 二叉树
6.1 树的相关概念
路径: 顺着连接节点的边从一个节 点走到另一个节点，所经过 的节点的顺序排列就称为 “路径”。
1
2
3
其中橙色得线就代表一条路径
4
5
6
第025课 算法及数据结构
6 二叉树
6.1 树的相关概念
根: 树得顶端称为根.每棵树只有 一个根. 右图中 1 为根
private Node root;
第025课 算法及数据结构 6 二叉树
6.2 二叉树的建立
二叉树的初始化非常的简单.只需要有个根就可以了,而且树是空的.所以 甚至连根的初始化都可以省略.
这里唯一的一句root = null;都可 以省略.因为对象在初始化时,其 成员变量自动是空.为了清晰,还 是把它加上.
父结点与子结点: 除根结点外,其余结点都有另外一个 结点指向它.那么指向其它结点的结 点称为父结点.被指向的结点称为子 结点.
右图中3为6的父结点,6为3的子结点
1
2
3
4
5
6
第025课 算法及数据结构
6 二叉树
6.1 树的相关概念
1
叶结点: 没有子结点的结点称为叶结点. 图中4,5,6均为叶结点.