树
一、基本概念
-
节点的度 ：节点拥有的
子树数成为节点的度。- 叶子节点：度为0的节点称为叶子节点；
- 分支节点：度不为0的节点称为分支节点；
-
树的度：树内各节点的度的最大值；
度的图解
-
树的层次与深度：树中节点的最大层次称为树的深度（高度）
树的层次与深度注意：根节点为第一层；
二、树的存储
存储方式（存储思想）：利用顺序存储和链式存储共同来实现树的存储；
（一）双亲表示法
- 定义：在每个节点中，附设一个指示器指示其双亲节点在链表中的位置（即孩子节点指向父节点）；（开发中常用做法）
- 优点：从孩子找父节点容易；
- 缺点：从父节点找孩子难；
- 节点的数据模型
模型图解
-
举例：
树存储方式图解
（二）孩子表示法
- 特点：用父节点表示自己
- 优点：找每个节点的孩子容易；
- 缺点：
- 找到每个节点的父节点难；
- 存在数据冗余，内存浪费；
- 数组扩容难；
- 举例
方案一：创建固定长度的数组，使得每个节点都有若干个指针指向自己的每一个孩子
[图片上传失败...(image-21a424-1517935019947)]
方案二：先用一个标记记录每个节点有几个孩子，然后根据这个标记创建数组，减少数据冗余；
[图片上传失败...(image-2dec98-1517935019947)]
（三）孩子双亲表示法
-
做法：把每个节点的孩子节点排列起来，以单链表作为存储结构，则n个节点有n个孩子链表，如果是叶子节点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中；
孩子兄弟表示法
二叉树
一、概念
- 完全二叉树：对一棵有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树；
完全二叉树举例
二、二叉树的链式存储方式
二叉树的链式存储方式
三、二叉树的遍历
一、前序遍历
-
步骤
- 如果二叉树为空，则空操作返回
- 否则先访问
跟节点； - 然后前序遍历
左子树； - 再前序遍历
右子树；
-
代码实现
public void preOrderTraverse(Tree tree){ if(tree == null){ return; } System.out.println(tree.data); preOrderTraverse(tree.leftChild); preOrderTraverse(tree.rightChild); }
二、中序遍历
-
步骤
- 如果二叉树为空，则返回空操作；
- 否则前序遍历
左子树； - 然后访问
跟节点； - 再中序遍历
右子树；
-
代码实现
public void midOrderTraverse(Tree tree){ if(tree==null){ return; } midOrderTraverse(tree.leftChild); System.out.println(tree.data); midOrderTraverse(tree.rightChild); }
三、后序遍历
-
步骤
- 如果二叉树为空，则返回空操作；
- 否则后序遍历
左子树； - 然后后序遍历
右子树； - 再遍历
根节点；
-
代码实现
public void proOrderTraverse(Tree tree){ if(tree==null){ return; } proOderTraverse(tree.leftChild); proOderTraverse(tree.rightChild); System.out.println(tree.data); }
四、二叉树的创建以及遍历
public class BinaryTree<T> {
private TreeNode root;//根节点，这个节点是一定存在的，而且对二叉树的操作就是从这里开始的
public TreeNode getRoot() {
return root;
}
/**
* @param t 根节点的初始值
*/
public BinaryTree(T t) {
root = new TreeNode(1, t);
}
/**
* 通过二叉树的前序序列集合创建二叉树
* @param list 集合必须是二叉树对应的完全二叉树序列，没有节点的地方用<code>#</code>代替
* 算法思想：每次从list中取出一个元素来构建二叉树，同时从集合中移除这个元素，如果list的长度为0，表示构建完成
* 如果遇到<code>#</code>,就不输出，然后递归调用这个方法，得到二叉树序列
* @return
*/
public TreeNode createBinaryTree(int size, List<T> list) {
if (list == null) {
return null;
} else if (list.size() == 0) {
return null;
} else {
//构建节点的准备工作，数据域和角标index
T t = list.get(0);
TreeNode node = null;
int index = size - list.size();
if (t.equals("#")) {
//如果是#，说明这里就没有节点，就不用构建，但是要把这个元素从list中移除
node = null;
list.remove(t);
return node;
}
//如果代码走到这里，就表示有数据，需要构造节点
node = new TreeNode(index, t);
//此外一定要把二叉树的根节点赋值，否则整棵二叉树就没有和root关联起来，会报npe
if (index == 0) {
root = node;
}
list.remove(t);
//以上构造完一个节点，接下来构造该节点的左右子树，
//因为输入的是前序遍历的二叉树集合，所以要先构建左子树，然后是右子树
//由递归的特点可知，这里一定是先构造完左子树，然后再构造右子树
node.leftChild = createBinaryTree(size, list);
node.rightChild = createBinaryTree(size, list);
return node;
}
}
/**
* 这里有两种实现思路：
* <li>
* 有个成员变量<code>size</code>,每次添加一个节点size++，这样就得到了节点的个数
* </li>
* 思路二:通过遍历二叉树来计算节点个数
* @return 二叉树中节点的个数
*/
public int size() {
return getSize(root);
}
/**
* 获取任意节点的子节点个数
* note：在二叉树中，递归（迭代）是很重要的思想
* @param node 指定的节点
* @return
*/
public int getSize(TreeNode node) {
return 1 + getSize(node.leftChild) + getSize(node.rightChild);
}
/**
* 对指定的节点前序遍历
* @param node
*/
public void preOrderTraverse(TreeNode node) {
if (node == null) {
return;
} else {
System.out.print(node.getData() + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
}
/**
* 中序遍历指定二叉树节点
* @param node
*/
public void midOrderTraverse(TreeNode node) {
if (node == null) {
return;
} else {
midOrderTraverse(node.getLeftChild());
System.out.print(node.getData() + " ");
midOrderTraverse(node.getRightChild());
}
}
/**
* 对指定二叉树结点后序遍历
* @param node
*/
public void proOrderTraverse(TreeNode node) {
if (node == null) {
return;
} else {
proOrderTraverse(node.getLeftChild());
proOrderTraverse(node.getRightChild());
System.out.print(node.getData() + " ");
}
}
private static final class TreeNode<T> {
private int index;//每个节点的标记，根节点默认是1
private T data;
private TreeNode leftChild;
private TreeNode rightChild;
private TreeNode parent;//父节点，这样我们就可以找到每个节点的孩子节点和父节点了
/**
* 构造方法，因为在创建节点时候并不知道左右孩子以及父节点信息，
* 所以在构造方法里面无法通过构造方法对这些节点信息赋值，只能在创建对象后进行赋值
* @param index 节点在整个二叉树中的标记，
* @param data
*/
public TreeNode(int index, T data) {
this.index = index;
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
}
}