文档介绍：深入Java编程
专业教程
理论讲解部分
第025课算法及数据结构
概述:
二叉树的相关概念
二叉树的实现
重点:
难点:
二叉树的实现
二叉树的实现
6 二叉树
第025课算法及数据结构
二叉树综合了有序数组与链表得优点.
有序数组具有较快得查找速度,链表具有非常好得插入删除效率.
树结合了两者得有点,使得它具有很高得插入删除及查找得效率.
它得实现与其结构密切相关,下面我们来看看它的结构.
第025课算法及数据结构
1
2
3
4
5
6
7
8
这是一棵很简单的树.
树主要是由结点及结点之间得关系组成的
下面给出一些相关得概念
6 二叉树
第025课算法及数据结构
二叉树或者是一棵空树,或者是一棵由一个根结点和两棵互不相交的分别称根的左子树和右子树所组成的非空树,左子树和右子树又同样都是一棵二叉树. 右图为一棵二叉树
树的相关概念
二叉树:
1
2
3
4
5
6
6 二叉树
第025课算法及数据结构
路径:
顺着连接节点的边从一个节点走到另一个节点,所经过的节点的顺序排列就称为“路径”。
1
2
3
4
5
6
其中橙色得线就代表一条路径
树的相关概念
6 二叉树
第025课算法及数据结构
根:
.
1
2
3
4
5
6
右图中 1 为根
父结点与子结点:
除根结点外,.
右图中3为6的父结点,6为3的子结点
树的相关概念
6 二叉树
第025课算法及数据结构
1
2
3
4
5
6
叶结点:
没有子结点的结点称为叶结点.
图中4,5,6均为叶结点.
子树:
图中2,4,5可以看作是一棵子树.
树的相关概念
6 二叉树
第025课算法及数据结构
1
2
3
4
5
6
遍历:
根据某种规则,对树中所有的结点全部访问一次称作一次遍历.
例如:1,2,3,4,5,6 .
层:
树中从根开始计算的“辈分”.
0
1
2
树的相关概念
6 二叉树
第025课算法及数据结构
二叉树的建立
实现二叉树首先就要实现它的结点.
它的每一个结点除了要保存相应的数据之外,还要保存其子结点的引用.
其数据需要两个域,一个保存键值,另一个保存该键值所对应的数据.
private class Node{
int key;
int value;
Node left;
Node right;
}
6 二叉树