一、树型结构
在认识二叉树之前,我们可以先了解一下什么叫树。
数据结构中的树,和我们生活中的树是有类似之处的。其实是一种非线性的数据结构。它具有以下的特点:每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树。
如图,就是一个普通的树形结构,这里我们一定要区分开树和图的区别。
二、二叉树
1、概念:
二叉树也是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点:每个节点的度最多是2。二叉树的子树是有左右之分的,并且次序不可以颠倒。
上图就是一个二叉树的结构。
2、特殊的二叉树
满二叉树:一个二叉树,每一层的节点树都达到了最大值,就是满二叉树。如果一个树有k层,节点数就为(2^k)-1个。
完全二叉树:是由满二叉树引出来的,相比于满二叉树,完全二叉树是树结构的右小角缺少节点。
3、二叉树的遍历:
(下面的遍历结果都以这棵树为例)
(1)先序遍历:
先访问(打印)根节点,递归遍历左子树,递归遍历右子树。
遍历过程:
访问A(打印),再遍历左子树B。
B作为D的根节点,访问B(打印),遍历B的左子树D。D作为H的根节点,访问D(打印),遍历D的左子树H。H的左右子树都为空,访问H(打印)。此时B的左子树遍历完,接着遍历B的右子树EB作为E的根节点,访问E(打印),遍历E的左子树(空),遍历E的右子树I。I的左右子树都为空,访问I(打印),此时B的右子树遍历完,A的左子树遍历完。
A作为C的根节点,访问C(打印),遍历C的左子树
C作为F的根节点,访问F(打印),F的左右子树都为空。此时C的左子树遍历完,接着遍历C的右子树GC作为G的根节点,访问G(打印),G的左右子树都为空。
最后遍历的结果就为:A B D H E I C F G
(2)、中序遍历
先递归遍历左子树,访问根节点,再递归遍历右子树。
遍历过程:
遍历根节点A,A的左子树为B。B的左子树为D。D的左子树为H。H的左子树为空,访问(打印)H。
H的根节点为D,访问(打印)D。D的右子树为空。
D的根节点为B,访问(打印)B。
B的右子树为E。E的左子树为空,访问(打印)E。E的右子树为I,访问(打印)I。
A的左子树访问完,访问(打印)A。
A的右子树为C,C的左子树又为F。
F的左右子树都为空,访问(打印)F。C的左子树访问完,访问(打印)C。C的右子树为G,访问(打印)G。
最后的遍历结果为:H D B E I A F C G
(3)、后序遍历
先递归遍历左子树,再递归遍历右子树,访问根节点。
递归过程:
A的左子树为B,B的左子树为D,D的左子树为H,H的左右子树为空,访问(打印)H。D的左子树访问完,右子树为空,访问(打印)D。B的左子树访问完,B的右子树为E。E的左子树为空,右子树为I,访问(打印)I。E的左右子树访问完,访问(打印)E。B的左右子树访问完,访问(打印)B。A的左子树访问完,A的右子树为C,C的左子树为F,F的左右子树为空,访问(打印)F。C的左子树访问完,右子树为G,访问(打印)G。C的左右子树访问完,访问(打印)C。A的左右子树访问完,访问(打印)A。
最后的遍历结果为:H D I E B F G C A
(4)、层序遍历:
一层一层向下遍历,每一层从左到右访问。
遍历结果为:A B C D E F G H I
4、二叉树的表示:
class Node{public char val;//值public Node left;//左子树public Node right;//右子树}
三、代码实现(递归):
1、先序遍历:
public static void prevOrder(Node root) {if(root == null) {return;}System.out.print(root.val + " ");prevOrder(root.left);prevOrder(root.right);}
2、中序遍历
public static void inOrder(Node root) {if(root == null) {return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}
3、后续遍历:
public static void postOrder(Node root) {if(root == null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+ " ");}
4、层序遍历:
public void levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode cur = queue.poll();System.out.print(cur.val + " ");if(cur.left != null) {queue.offer(root.left);}if(cur.right != null) {queue.offer(root.right);}}}