Java数据结构第十二期：走进二叉树的奇妙世界(一)

专栏：数据结构(Java版)

个人主页：手握风云

目录

一、树型结构

1.1. 树的定义

1.2. 树的基本概念

1.3. 树的表示形式

二、二叉树

2.1. 概念

2.2. 两种特殊的二叉树

2.3. 二叉树的性质

2.4. 二叉树的存储

三、二叉树的基本操作

---

一、树型结构

1.1. 树的定义

        树是⼀种⾮线性的数据结构，它是由n（n>=0）个有限结点组成⼀个具有层次关系的集合。把它叫做 树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。它具有以下的特点：

1. 有⼀个特殊的结点，称为根结点，根结点没有前驱结点
2. 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每⼀个集合Ti (1 <= i <= m) ⼜是⼀棵与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有0个或多个后继
3. 树是递归定义的

       注意，在树型结构中，子树与子树之间不能有交集，否则就不是树型结构。

1.2. 树的基本概念

结点的度：⼀个结点含有⼦树的个数称为该结点的度； 如上图，A的度为2

树的度：⼀棵树中，所有结点度的最⼤值称为树的度；如上图，树的度为3

叶子结点或终端结点：度为0的结点称为叶结点；如上图，G、H、I、J都是叶结点

父结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；如上图，A是B的父节点

子结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如上图，B是A的子结点

根结点：⼀棵树中，没有父结点的结点；如上图，A

结点的层次：从根开始定义起，根为第1层，根的⼦结点为第2层，以此类推

树的高度或深度：树中结点的最大层次；如上图，树的高度是4

1.3. 树的表示形式

       树结构相对线性表就比较复杂了，要存储表示起来就⽐较麻烦了，实际中树有很多种表示⽅式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这⾥就简单的了解其中最常用的孩子兄弟表示法。

class Node{int val;//树中储存的数据Node firstChild;//第一个孩子引用Node nextBrother;//下一个兄弟引用
}

二、二叉树

2.1. 概念

        一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的⼆叉树组成。

       从上图中可以看出：⼆叉树不存在度⼤于2的结点；⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树。

       注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的。

2.2. 两种特殊的二叉树

1. 满二叉树：如果一棵二叉树的层数为K，且结点总数是 ，则它就是满⼆叉树。
2. 完全二叉树：完全⼆叉树是由满⼆叉树⽽引出来的。对于深度 为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0⾄n-1的结点一一对应。满二叉树是一种特殊的完全二叉树。

2.3. 二叉树的性质

1. 若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有(i>0)个结点
2. 若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的最⼤结点数是(k>=0)
3. 对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0＝n2＋1
4. 具有n个结点的完全⼆叉树的深度k为上取整

2.4. 二叉树的存储

        二叉树的存储方式分为：顺序结构和类似于链式的结构。我们这里主要介绍链式存储。⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的。

//孩子表示法
class Node{int val;//数据域Node left;//左孩子引用Node right;//右孩子引用
}//孩子双亲表示法
class Node{int val;Node left;Node right;Node parent;//当前节点的根节点
}

三、二叉树的基本操作

我们可以自己创建一个二叉树，我们可以参照之前创建链表、栈、队列的方式来手动创建二叉树。

public class BinaryTree {static class TreeNode{public char val;public TreeNode left;//左孩子结点引用public TreeNode right;//右孩子结点引用public TreeNode(char val) {this.val = val;}}public TreeNode CreateTree(){TreeNode A = new TreeNode('A');TreeNode B = new TreeNode('B');TreeNode C = new TreeNode('C');TreeNode D = new TreeNode('D');TreeNode E = new TreeNode('E');TreeNode F = new TreeNode('F');TreeNode G = new TreeNode('G');TreeNode H = new TreeNode('H');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;E.right = H;return A;}
}

public class Test {public static void main(String[] args) {BinaryTree binaryTree = new BinaryTree();BinaryTree.TreeNode root = binaryTree.CreateTree();//因为是静态内部类System.out.println("========");}
}

        我们在打印这一行大一个断点进行调试。先走完A结点，再通过递归的方法，去遍历左孩子结点B和右孩子结点C，以此类推，再去遍历B的左孩子结点E和右孩子结点F。

       二叉树可以空树也可以是非空树。非空树由根节点的左子树、根节点的右子树组成的。从概念中可以看出，⼆叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。