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

本文后面主要采用孩子表示法创建二叉树。 

3.5二叉树的遍历方式

3.5.1创建二叉树

public class BinaryTree {     public class TreeNode {         TreeNode left;         TreeNode right;         int val;          public TreeNode(int val) {             this.val = val;         }     }       public TreeNode createTree() {         TreeNode node1 = new TreeNode(1);         TreeNode node2 = new TreeNode(2);         TreeNode node3 = new TreeNode(3);         TreeNode node4 = new TreeNode(4);         TreeNode node5 = new TreeNode(5);         TreeNode node6 = new TreeNode(6);          node1.left = node2;         node1.right = node3;         node2.left = node4;         node2.right = node5;         node3.left = node6;         return node1;     } }

3.5.2二叉树的遍历

前序遍历：访问根结点——>根的左子树——>根的右子树。中序遍历：根的左子树——>根节点——>根的右子树。 后序遍历：根的左子树——>根的右子树——>根节点。

• 前序遍历

代码实现如下：

    //前序遍历     public void preOrder(TreeNode root) {         //如果是空树则不需要遍历         if (root == null) {             return;         }         System.out.print(root.val + " ");//访问根节点         preOrder(root.leftNode);//前序遍历左子树         preOrder(root.rightNode);//前序遍历右子树     }

• 中序遍历 

代码实现如下：

    //中序遍历     public void inOrder(TreeNode root) {         //如果是空树则不需要遍历         if (root == null) {             return;         }         inOrder(root.leftNode);//中序遍历左子树         System.out.print(root.val + " ");//访问根节点         inOrder(root.rightNode);//中序遍历右子树     }

•  后序遍历

代码实现如下：

    //后序遍历     public void postOrder(TreeNode root) {         //如果是空树则不需要遍历         if (root == null) {             return;         }         postOrder(root.leftNode);//后序遍历左子树         postOrder(root.rightNode);//后序遍历右子树         System.out.print(root.val + " ");//访问根节点     }

下面简单举个例子：

public class Test {     public static void main(String[] args) {         BinaryTree binaryTree = new BinaryTree();         BinaryTree.TreeNode root =binaryTree.createTree();         System.out.println("前序遍历：");//前序遍历结果：1 2 4 5 3 6         binaryTree.preOrder(root);         System.out.println();         System.out.println("中序遍历：");//中序遍历结果：4 2 5 1 6 3         binaryTree.inOrder(root);         System.out.println();         System.out.println("后序遍历：");//后序遍历结果：4 5 2 6 3 1         binaryTree.postOrder(root);     } }

运行结果如下：

 上面所创建出来的二叉树画出来就是下面这样子。

2.层序遍历

public void levelOrder(TreeNode root) {         Queue queue = new LinkedList<>();         if (root == null) {             return;         }         queue.offer(root);         while (!queue.isEmpty()) {             TreeNode cur = queue.poll();             System.out.print(cur.val + " ");             if (cur.left != null) {                 queue.offer(cur.left);             }             if (cur.right != null) {                 queue.offer(cur.right);             }         }         System.out.println();     }

我们通过队列实现层序遍历的功能，只要队列不为空，就把获取到的队头元素给cur，并且同时将这个元素打印出来，在把cur的左右两边代进去，如果左右两边为空的则不能代进去，只有非空才能代入里面。

1.某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的前序序列为()A: ABDHECFG   B: ABCDEFGH   C: HDBEAFCG   D: HDEBFGCA2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为()A: E     B: F     C: G     D: H3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为()A: adbce   B: decab    C: debac    D: abcde4.某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出(同一层从左到右)的序列为()A: FEDCBA  B: CBAFED  C: DEFCBA  D: ABCDEF答案：1.A    2.A    3.D    4.A 

3.6二叉树的基本操作

1.获取树中节点的个数

//获取树的节点个数     //方法1：递归     public int size(TreeNode root) {         if (root == null) {             return 0;         }         int ret = size(root.left) + size(root.right) + 1;         return ret;     }      //方法2：遍历     public static int nodeSize;      public void size1(TreeNode root) {         if (root == null) {             return;         }         nodeSize++;         size1(root.left);         size1(root.right);     }

public class Test {     //二叉树的基本操作     public static void main(String[] args) {         BinaryTree binaryTree = new BinaryTree();         BinaryTree.TreeNode root = binaryTree.createNode();         binaryTree.preOrder(root);          System.out.println();         binaryTree.inOrder(root);          System.out.println();         binaryTree.postOrder(root);         System.out.println();         System.out.print("树的节点个数：");         System.out.println(binaryTree.size(root));     } }

运行结果如下：

2.获取叶子节点的个数

//获取叶子节点的个数     //方法1     public int getLeafNodeCount(TreeNode root) {         if (root == null) {             return 0;         }         if (root.left == null && root.right == null) {             return 1;         }         return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);     }      //方法2：遍历     public int leafSize;      public void getLeafNodeCount1(TreeNode root) {         if (root == null) {             return;         }         if (root.left == null && root.right == null) {             leafSize++;         }         getLeafNodeCount1(root.left);         getLeafNodeCount1(root.right);     }

3. 获取第K层节点的个数

    //第K层有多少个结点     public int getKLeaveNodeCount(TreeNode root, int k) {         if (root == null) {             return 0;         }         if (k == 1) {             return 1;         }         return getKLeaveNodeCount(root.left, k - 1)                 + getKLeaveNodeCount(root.right, k - 1);     }

4.获取二叉树的高度

//求二叉树的高度     //时间复杂度：O(N)     public int getHeight(TreeNode root) {         if (root == null) {             return 0;         }         int leafHeight = getHeight(root.left);         int rightHeight = getHeight(root.right);         return leafHeight > rightHeight ?                 leafHeight + 1 : rightHeight + 1;     }

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

 // 检测值为value的元素是否存在     public TreeNode find(TreeNode root, int val) {         if (root == null) {             return null;         }         if (root.val == val) {             return root;         }         TreeNode ret = find(root.left, val);         if (ret != null) {             return ret;         }         ret = find(root.right, val);         if (ret != null) {             return ret;         }         return null;     }

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

//判断一棵树是不是完全二叉树     public boolean isCompleteTree(TreeNode root) {         Queue queue = new LinkedList<>();         if (root == null) {             return true;         }         queue.offer(root);         while (!queue.isEmpty()) {             TreeNode cur = queue.poll();             if (cur == null) {                 break;             }             queue.offer(cur.left);             queue.offer(cur.right);         }         while (!queue.isEmpty()) {             TreeNode node = queue.peek();             if (node != null) {                 return false;             } else {                 queue.poll();             }         }         return true;     }

4.总结

本文的重点是树中的重要概念和二叉树的性质、遍历方式以及基本操作，小伙伴们在学习有关二叉树的内容，一定要画出二叉树，能够帮助我们更好地理解，再去编写代码。