树
树是很常见而且被广泛利用的数据结构,而且种类繁多,包括一般二叉树、完全二叉树、满二叉树、线索二叉树、二叉排序树、平衡二叉树、红黑树、霍夫曼树、B树,B+Tree等.
概念
树是一种抽象数据类型,或是实现这种抽象数据类型的[数据结构]用来模拟具有树状结构性质的数据**。
它是由n（ngt;0）个有限节点组成一个具有层次关系的。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 树里面没有环路(cycle)
- 每个节点都只有有限个子节点或无子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
术语
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 树的度：一棵树中，最大的节点度称为树的度；
- 叶节点或终端节点：度为零的节点；
- 非终端节点或分支节点：度不为零的节点；
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
-
高度：对于任意节点n,n的高度为从n到一片树
叶的最长路径长，所有树叶的高度为0； - 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（mgt;=0）棵互不相交的树的**称为森林；
树的表示方法
链表,数组
定义节点
public class TreeNode {
E object;
TreeNode left;
TreeNode right;
}
树的基本操作
二叉树
它是一种特殊的结构的 没个节点只有两个分支,而且没有构成环的一种特殊的树.
示例
二叉树的遍历
深度优先 分为三种 分别是前序,中序,后序(这里的前中后指的是根的顺序).
广度优先 是安层来遍历一颗树.
递归的实现 :
import java.util.ArrayList;
import java.util.List;
public class BinaryTree {
/*
Definition for a binary tree node.
* */
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
List<Integer> result = new ArrayList<>();
/**
* 前序遍历
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
if (root !=null){
result.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return result;
}
/**
* 中序遍历
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
if (root !=null){
inorderTraversal(root.left);
result.add(root.val);
inorderTraversal(root.right);
}
return result;
}
/**
* 后序遍历
* @param root
* @return
*/
public List<Integer> postorderTraversal(TreeNode root) {
if (root !=null){
postorderTraversal(root.left);
postorderTraversal(root.right);
result.add(root.val);
}
return result;
}
}
非递归的实现 :
层遍历
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){return levelRead;}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<Integer> level = new ArrayList<>();
TreeNode current = null;
queue.add(root);
while(!queue.isEmpty()){
//出队队头元素并访问
current = queue.poll();
level.add(current.val);
// System.out.print(current.val +"-->");
if(queue.isEmpty()){
levelRead.add(level);
level = new ArrayList<>();
}
//如果当前节点的左节点不为空入队
if(current.left != null){
queue.add(current.left);
}
//如果当前节点的右节点不为空，把右节点入队
if(current.right != null){
queue.add(current.right);
}
}
return levelRead;
}
