学习目标
- 理解树抽象数据类型
- 会用树解决问题
- 掌握树的遍历方法
- 掌握二叉树的实现(数组，链表)
- 会用二叉树表示决策树
树的基本知识
1.树
- 每棵树至多只有一个根节点
- 根节点生出多个孩子节点，每个孩子节点只有一个父节点每个孩子又生出多个孩子
- 父亲节点 (parent) 和孩子节点 (child) 是相对的
- 没有孩子节点的节点成为叶子节点 (leaf)
节点的度:
一个节点直接含有的子树个数，叫做节点的度。
树的度:
一棵树中 最大节点的度，即哪个节点的子节点最多，它的度就是 树的度。
节点的层次:
从根节点开始算起，根节点算第一层，往后至底层。
树的高度和深度
树的高度是从叶子节点开始，自底向上增加。与高度相反，树的深度从根节点开始，自顶向下增加。
2.树的遍历
根据不同的场景中，根节点，左右子树遍历的顺序，二叉树的遍历分为三种。
- 先序遍历
- 中序遍历
- 后序遍历
先序遍历：
- 先访问根节点
- 再先序遍历左子树
- 再先序遍历右子树
- 退出
代码
public voic preorder(BinaryTreeNode node){
if(node == null){
return;
}
//(1)打印出node的data
//(2)
preorder(node.getLeft());
//(3)
preorder(node.getRight());
}
中序遍历
- 先中序遍历左子树
- 再访问根节点
- 再中序遍历右子树
- 退出
代码
public void inorder(BinaryTreeNode node){
if(node == null){
return;
}
//(1)
inorder(node.getLeft());
//(2)打印出node
//(3)
inorder(node.getRight());
}
后序遍历
- 先后序遍历左子树
- 再后序遍历右子树
- 最后访问根节点
- 退出
代码
public void postorder(BinatyTreeNode node){
if(node == null){
return;
}
//(1)
postorder(node.getLeft());
//(2)
postorder(node.getRight());
//(3)打印出node的data
}
树的实现
1.树的数组表示（1）
-
关键概念：使用数组实现二叉树时，位于位置n的元素的左孩子在（2n+1）的位置，其右孩子在（2（n+1））的位置。
-
代码【目前未完成】
2.树的数组表示（2）
-
关键概念：树的基于数组的储存链实现方式可以占据数组中的连续位置，不管树是不是完全树。这是模仿操作系统内存管理的方法。数组的每个元素是一个对象，他保存指向树中元素的引用及每个子节点所在的数组下标。
-
代码【目前未完成】
3.输的链式实现
-
关键概念：使用一个单独的类来定义树节点，每个节点都包含一个指向节点可能有的子节点的引用，这样做的好处是有助于递归的方式处理树的许多操作。
-
书中给出的代码LinkedBinaryTree类未实现的方法有：getRigth() , contains() , isEmpty() , toString() , preorder() , postorder() .
getRight()方法的实现跟getLeft()方法的实现大体一致，都是返回整棵左或右子树，返回值是新构建的LinkedBinaryTree对象。
public LinkedBinaryTree<T> getRight() {
if (root==null)
throw new EmptyCollectionException("Get right operation"+"failed.The tree is empty.");
LinkedBinaryTree<T> result = new LinkedBinaryTree<>();
result.root=root.getRight();
return result;
}
contains方法调用find方法，返回boolean类型的值，判断是否存在目标元素
public boolean contains(T target) {
BTNode<T> node = null;
if (root!=null)
node = root.find(target);
if (node==null)
return false;
else return true;
}
preorder方法是将树进行先序遍历；postorder方法是将树进行后续遍历。