一文掌握二叉树

轻松掌握二叉树

树形结构

树是一种非线性的数据结构，它是由 n 个有限节点组成一个具有层次关系的集合。因为看起来像倒过来的树，所以叫做树形结构。

树形结构当作子树不能有交集，否则就不是树形结构。

节点的度

一个结点含有子树的个数称为该节点的度，如下图 A 的度就是 6 ：

树的度

一棵树中，所有结点度的最大值称为树的度，如下图当中，A 的度最大，所以树的度就是 6 ：

叶子结点或终端结点

度为0的结点称为叶结点； 如下图：B、C、H、I…等节点为叶结点：

双亲结点或父结点

若一个结点含有子结点，则这个结点称为其子结点的父结点； 如下图：A是B的父结点

孩子结点或子结点

一个结点含有的子树的根结点称为该结点的子结点； 如下图：B是A的孩子结点

根节点

一棵树中，没有双亲结点的结点：如下图当中的：A

结点的层次

从根开始定义起，根为第1层，根的子结点为第2层，以此类推，就像下图的 P Q 就是在第四层。

树的高度或深度

树中结点的最大层次； 如下图：树的高度为4

兄弟节点

具有相同父结点的结点互称为兄弟结点； 如下图：B、C是兄弟结点

树的表示形式

树形结构的表示方法有很多：双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等，我们常用的是孩子兄弟表示法。

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

如下图：

二叉树

二叉树是由一个根节点加上两颗分别称为左子树和右子树的二叉树组成的：

1. 二叉树不存在度大于 2 的结点。
2. 二叉树的子树有左右之分，次序不能颠倒，所以二叉树是有序树。

二叉树的组成情况

二叉树的组成情况都是由以下几种复合而成的：

两种特殊的二叉树

1. 满二叉树：一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点
2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)
3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
4. 具有n个结点的完全二叉树的深度k为 上取整
5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从 0 开始编号，则对于序号为 i 的结点有： > 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点> **若2i+1<n，左孩子序号：2i+1，否则无左孩子**> 若2i+2<n，右孩子序号：2i+2，否则无右孩子

二叉树的存储

二叉树的存储有顺序存储和链式存储。这里将链式存储：二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下（孩子表示法）：

classNode{int val;// 数据域Node left;// 左孩子的引用，常常代表左孩子为根的整棵左子树Node right;// 右孩子的引用，常常代表右孩子为根的整棵右子树}

实现二叉树

这里要实现的时候，是用穷举的方式创建，并不是用真正的方式创建二叉树，在之后会讲，这里是为了讲解功能：

实现类

二叉树有值、左孩子、右孩子。定义在类里实现：

classBTNode{publicchar val;publicBTNode left;//左孩子的引用publicBTNode right;//右孩子的引用publicBTNode(char val){this.val = val;}}

创建树

定义一个二叉树的根节点，然后通过穷举的方式创建：

publicBTNode root;//二叉树的根节点publicBTNodecreatTree(){BTNodeA=newBTNode('A');BTNodeB=newBTNode('B');BTNodeC=newBTNode('C');BTNodeD=newBTNode('D');BTNodeE=newBTNode('E');BTNodeF=newBTNode('F');BTNodeG=newBTNode('G');BTNodeH=newBTNode('H');A.left =B;A.right =C;B.left =D;B.right =E;C.left =F;C.right =G;E.right =H;returnA;}

这里就是将 A 作为根节点，然后修改左右指向。创建这样的一颗二叉树：

前序遍历

前序遍历（又叫前根遍历）就是在遍历二叉树的时候，先遍历根，然后是左子树，最后是右子树。如下图：

这颗二叉树的前序遍历就是：A B D E H C F G 。所以遍历的时候就按照这种方式去递归遍历。递归遍历的终止条件就是：当前结点为空的时候，就返回。代码如下：

voidpreOrder(BTNode root){if(root ==null){return;}System.out.print(root.val+" ");preOrder(root.left);preOrder(root.right);}

中序遍历

中序遍历（又叫中根遍历）是先左子树，然后是根，最后是右子树。如下图的中序遍历结果就是：D B E H A F C G

代码如下：

voidinOrder(BTNode root){if(root ==null){return;}inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}

后序遍历

后序遍历（又叫后根遍历）则是先左子树，然后是右子树，最后是根，如下图的后序遍历结果就是：D H E B F G C A

代码如下：

voidpostOrder(BTNode root){if(root ==null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+" ");}

获取二叉树当中结点的个数

获取二叉树当中结点的个数有两种方法：1、遍历方法，2、子问题方法（左树的结点的个数+右树的结点的个数。

遍历方法

通过一种遍历方式去遍历即可，然后定义一个计数器，用来计算个数。代码如下：

int count =0;intsize(BTNode root){if(root ==null){return0;}
    count++;size(root.left);size(root.right);return count;}

子问题方法

通过判断左子树和右子树的个数即可。代码如下：

intsize1(BTNode root){if(root ==null){return0;}returnsize1(root.left)+size1(root.right)+1;}

获取叶子结点的个数

这里获取的方法也有两个：1、遍历思路 2、子问题思路

遍历方法

如果遍历到叶子结点，计数器就++，叶子节点就是 left 和 right 都为空。代码如下：

int num =0;intgetLeafNodeCount(BTNode root){if(root ==null){return0;}if(root.left ==null&& root.right ==null){
        num++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return num;}

子问题方法

这里的子问题方法就是左树的叶子 + 右树的叶子，如果是叶子的话，就返回 1 代码如下：

intgetLeafNodeCount1(BTNode root){if(root ==null){return0;}if(root.left ==null&& root.right ==null){return1;}returngetLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);}

求第 k 层结点的个数

求第 k 层，那么也就是每往下一层，让 k - 1 当 k == 1 的时候，就到了 k 层了，如图所示：

所以当递归到 k == 1 的时候，返回 1 就可以了。代码如下：

intgetKLevelNodeCount(BTNode root,int k){if(root ==null){return0;}if(k ==1){return1;}returngetKLevelNodeCount(root.left, k -1)+getKLevelNodeCount(root.right, k -1);}

获取二叉树的高度

同样是通过递归比较左树的高度和右树的高度取最大值，然后返回的时候 + 1 。如下图：

代码如下：

intgetHeight(BTNode root){if(root ==null){return0;}if(root.left ==null&& root.right ==null){return1;}returnMath.max(getHeight(root.left),getHeight(root.right))+1;}

检测值为 value 的元素是否存在

要检测是否有此元素，那么直接遍历结点是否有 value 数据就可以了。如果没有找到就返回空，代码如下：

BTNodefind(BTNode root,char val){if(root ==null){returnnull;}if(root.val == val){return root;}BTNode ret =find(root.left, val);if(ret !=null){return ret;}returnfind(root.right, val);}

判断一棵树是不是完全二叉树

可以用队列来做，把每一个结点都放入队列，就算是 null 也要放入。放入之后，弹出队头元素，然后把弹出的队头元素的左和右也放入。如果出到 null 的时候，剩下的全是 null ，那么就是完全二叉树。代码如下：

booleanisCompleteTree(BTNode root){if(root ==null){returntrue;}Queue<BTNode> queue =newLinkedList<>();
    queue.offer(root);while(!queue.isEmpty()){BTNode cur = queue.poll();if(cur !=null){
            queue.offer(cur.left);
            queue.offer(cur.right);}else{break;}}while(!queue.isEmpty()){BTNode top = queue.peek();if(top !=null){returnfalse;}
        queue.poll();}returntrue;}

层序遍历

这里的层序遍历也是用队列来实现，和上面的判断是不是完全二叉树相差无几，只不过是出队的时候，判断结点不为空，然后左右节点也不为空即可入队，直到最后队列为空。代码如下：

publicvoidlevelOrder(BTNode root){Queue<BTNode> queue =newLinkedList<>();if(root ==null){return;}
    queue.offer(root);while(!queue.isEmpty()){BTNode cur = queue.poll();System.out.print(cur.val+" ");if(cur !=null){if(cur.left !=null){
                queue.offer(cur.left);}if(cur.right !=null){
                queue.offer(cur.right);}}}}

查找最近的公共祖先

查找两个结点的公共祖先，假设是一颗二叉搜索树。二叉搜索树的中序遍历的大小是有序的。根节点的左数，都比根小。根节点的右树，都比根大。所以就会出现下图的这种情况：

所以，我们只要按照这个模式去做就可以了，如果左边和右边都不为空的话，就说明这两个结点在根节点的两侧，直接返回根节点就可以了。然后就是如果左边不为空，就返回左边。右边不为空，就返回右边。代码如下：

publicBTNodelowestCommonAncestor(BTNode root,TreeNode p,TreeNode q){if(root ==null){returnnull;}if(root == p || root == q){return root;}BTNode left =lowestCommonAncestor(root.left, p, q);BTNode right =lowestCommonAncestor(root.right, p, q);if(left !=null&& right !=null){return root;}elseif(left !=null){return left;}else{return right;}}

代码测试

代码如下：

publicstaticvoidmain(String[] args){MyBinaryTree myBinaryTree =newMyBinaryTree();BTNode root = myBinaryTree.creatTree();System.out.println("前序遍历");
    myBinaryTree.preOrder(root);System.out.println();System.out.println("中序遍历");
    myBinaryTree.inOrder(root);System.out.println();System.out.println("后序遍历");
    myBinaryTree.postOrder(root);System.out.println();System.out.println("二叉树当中结点的个数");System.out.println(myBinaryTree.size1(root));System.out.println("二叉树当中叶子结点的个数");System.out.println(myBinaryTree.getLeafNodeCount1(root));System.out.println("二叉树当中第 k 层结点的个数");System.out.println(myBinaryTree.getKLevelNodeCount(root,3));System.out.println("数的高度");System.out.println(myBinaryTree.getHeight(root));System.out.println("是否包含此节点，包含的话，输出此节点");try{System.out.println(myBinaryTree.find(root,'G').val);}catch(NullPointerException e){
        e.printStackTrace();System.out.println("没有这个节点");}System.out.println("是不是完全二叉树");System.out.println(myBinaryTree.isCompleteTree(root));System.out.println("层序遍历");
    myBinaryTree.levelOrder(root);}

运行结果如下：