树的基本概念及二叉树
目录
一、树的基本概念
（1）树的结点
（2）度
（3）结点层次
（4）树的高度
树的特点：
二、二叉树
（1）满二叉树
（2）完全二叉树
三、二叉树的存储
（1）顺序存储
(2)链式存储
四、二叉树的遍历
（1）前序遍历
（2）中序遍历
（3）后序遍历
（4）层序遍历
树是一种非线性的数据结构，存储具有“一对多”关系特点元素的一种数据结构。例如：组织架构、图书目录、商品种类、热点搜索词等。
如图所示就是一个 树 ，对数据A来说，和数据C、F有关系；对于数据F来说，和数据H、G有关系。这就是“一对多”的关系。
将具有“一对多”关系的集合中的数据元素按照树的形式进行存储，整个存储形状在逻辑结构上看，类似于实际生活中倒着的树，所以称这种数据的存储结构称为“树”。
一、树的基本概念
树是一种非线性的数据结构，包含n个结点的有限集合，结点之间具备一对多的逻辑关系，当树的结点n=0时，该树被称为空树。
（1）树的结点
树结构中，存储的每一个数据元素都被称为树的“结点”。
结点又被细分为：根节点、子节点、叶子结点
如图所示：叶子结点即树的末端结点，属于没有子结点的结点，统一称为叶子结点。
子树：由某个子结点作为根结点组成的树被称为子树。上图中红色部分就是一个子树。
（2）度
对于一个结点，拥有的子树个数（结点有多少分支）称为结点的度。
树的度：一颗树的度是树内各结点的度的最大值。
（3）结点层次
从一棵树的根结点开始，根结点所在层为第一层，根结点的子结点所在层为第二层，依次类推
（4）树的高度
一棵树的高度是树中结点所在的最大层次。树的高度，也被称为树的深度。
树的特点：
在任意一个非空树中，有以下特点：
1.有且仅有一个根结点
2.一棵树中的任意两个结点，有且仅有唯一的一条路径连通，不存在回路。
3.一棵树如果有n个结点，那么它一定有n-1条边
二、二叉树
二叉树是一种结点的度不大于2的有序树，子结点通常被称为“左孩子结点”和“右孩子结点”。
如图所示就是一个二叉树
这个图中树的度为3，所以此树就不是一个二叉树
二叉树又被分为满二叉树和完全二叉树
（1）满二叉树
满二叉树是一种特殊的二叉树，它的所有非叶子节点都存在左右子结点，并且所有的叶子结点都在同一层级
满二叉树的特点：
（2）完全二叉树
如果二叉树中，从根结点到倒数第二层，符合满二叉树要求，其叶子结点可以不完全填充，但必须靠从左到右连续分布，这样的二叉树被称为完全二叉树。
三、二叉树的存储
（1）顺序存储
顺序存储指的是使用顺序表（数组）存储二叉树。但是顺序存储只适用于完全二叉树。满二叉树也是完全二叉树，所以同样适用。
在顺序存储中，顺序表中的每一个位置仅存储结点的data，不需要存储左右子结点的指针，子结点的索引通过计算父结点下标完成。
如果一个父结点的下标为parentIndex它的左结点下标为：2parentIndex, 右子结点下标为：2parentIndex+1
如果完全二叉树，使用数组顺序存储，可以完全利用数组空间
如果是普通二叉树，使用数组顺序存储，在数组中就会出现空隙，导致内存利用率降低
//基于数组（顺序存储）的二叉树
public class BinaryTree1<E> {
// 创建一个新的空数组用来存储二叉树private Object[] elementData=null;
// 进行初始化操作public BinaryTree1(E[] elements) {
// 新数组的长度要比放入数据的数组长度大一个，因为新数组中从下标为1开始存储elementData=new Object[elements.length+1];for(int i=0,index=1;i<elements.length;i++,index++) {elementData[index]=elements[i];}}
// 获取指定下标处的元素public E get(int index) {return (E) elementData[index];}// 获取指定下标的左孩子public E left(int index) throws Exception {
// index<<1 即2倍的index，一个子节点的下标的二倍是他的左孩子结点，如果2倍的index大于等于数组长度则没有左子孩子if((index<<1)>=elementData.length) {throw new Exception("没有左孩子");}return (E) elementData[index<<1];}// 获取指定下标的右孩子public E right(int index) throws Exception {if((index<<1)+1>=elementData.length) {throw new Exception("没有右孩子");}return (E) elementData[(index<<1)+1];}}
(2)链式存储
二叉树的链式存储依靠指针将各个结点串联起来，不需要连续的存储空间。
每个结点包括3个属性：
- 数据 Data
- 左孩子结点指针 Left
- 右孩子结点 Right
//二叉树的链式存储
public class BinaryTree<E> {
// 根节点TreeNode<E> root;public BinaryTree(E val) {root=new TreeNode<E>(val);}
// 结点类static class TreeNode<E>{E data;TreeNode<E> left;TreeNode<E> right;public TreeNode() {}public TreeNode(E val) {this.data=val;}}public TreeNode<E> left(TreeNode<E> parent,E val){TreeNode<E> newNode=new TreeNode<E>(val);parent.left=newNode;return newNode;}public TreeNode<E> right(TreeNode<E> parent,E val){TreeNode<E> newNode=new TreeNode<E>(val);parent.right=newNode;return newNode;}}四、二叉树的遍历
| 前序遍历 | 根结点->左子树->右子树 |
| 中序遍历 | 左子树->根结点->右子树 |
| 后序遍历 | 左子树->右子树->根结点 |
（1）前序遍历
public static void preOrder(TreeNode root) {if(root==null) {return;}System.out.print(root.data);preOrder(root.left);preOrder(root.right);}（2）中序遍历
public static void inOrder(TreeNode root) {if(root==null) {return;}inOrder(root.left);System.out.print(root.data);inOrder(root.right);}（3）后序遍历
public static void postOrder(TreeNode root) {if(root==null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.data);}（4）层序遍历
层序遍历，就是按二叉树从上到下，从左到右，依次打印每层中每个结点存储的数据
public static void levelOrder(TreeNode root) {if(root==null) {return;}Queue<TreeNode> queue=new LinkedList<TreeNode>();queue.offer(root);while(true) {TreeNode t=queue.poll();if(t==null) {break;}
//访问当前节点，就用打印表示访问即可System.out.print(t.data);if(t.left!=null) {queue.offer(t.left);}if(t.right!=null) {queue.offer(t.right);}}}