一、为什么需要树这种数据结构

  1. 数组存储方式的分析
    • 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
    • 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低
  2. 链式存储方式的分析
    • 优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。
    • 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)
  3. 树存储方式的分析
    能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

二、树示意图

二叉树 - 图1

树的常用术语(结合示意图理解):

  1. 节点
  2. 根节点
  3. 父节点
  4. 子节点
  5. 叶子节点 (没有子节点的节点)
  6. 节点的权(节点值)
  7. 路径(从 root 节点找到该节点的路线)
  8. 层
  9. 子树
  10. 树的高度(最大层数)
  11. 森林 :多颗子树构成森

三、二叉树的概念

  1. 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
  2. 二叉树的子节点分为左节点和右节点

二叉树 - 图2

  1. 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树 二叉树 - 图3
  2. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二 层的叶子节点在右边连续，我们称为完全二叉树 二叉树 - 图4

四、二叉树遍历的说明

使用前序，中序和后序对下面的二叉树进行遍历.

  1. 前序遍历: 先输出父节点，再遍历左子树和右子树
  2. 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
  3. 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

小结: 看输出父节点的顺序，就确定是前序，中序还是后序

五、二叉树遍历应用实例(前序,中序,后序)

代码实现：

  1. public class BinaryTreeDemo {
  3.     public static void main(String[] args) {
  4.         //先需要创建一颗二叉树
  5.         BinaryTree binaryTree = new BinaryTree();
  6.         //创建需要的结点
  7.         HeroNode root = new HeroNode(1, "宋江");
  8.         HeroNode node2 = new HeroNode(2, "吴用");
  9.         HeroNode node3 = new HeroNode(3, "卢俊义");
  10.         HeroNode node4 = new HeroNode(4, "林冲");
  11.         HeroNode node5 = new HeroNode(5, "关胜");
  12.         //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
  13.         root.setLeft(node2);
  14.         root.setRight(node3);
  15.         node3.setRight(node4);
  16.         node3.setLeft(node5);
  17.         binaryTree.setRoot(root);
  18.         //测试
  19.         System.out.println("前序遍历"); // 1,2,3,5,4
  20.         binaryTree.preOrder();
  21.         //测试
  22.         System.out.println("中序遍历");
  23.         binaryTree.infixOrder(); // 2,1,5,3,4
  24.         //
  25.         System.out.println("后序遍历");
  26.         binaryTree.postOrder(); // 2,5,4,3,1
  27.     }
  28. }
  30. //定义 BinaryTree 二叉树
  31. class BinaryTree {
  32.     private HeroNode root;
  33.     public void setRoot(HeroNode root) {
  34.         this.root = root;
  35.     }
  36.     //前序遍历
  37.     public void preOrder() {
  38.         if(this.root != null) {
  39.             this.root.preOrder();
  40.         }else {
  41.             System.out.println("二叉树为空，无法遍历");
  42.         }
  43.     }
  44.     //中序遍历
  45.     public void infixOrder() {
  46.         if(this.root != null) {
  47.             this.root.infixOrder();
  48.         }else {
  49.             System.out.println("二叉树为空，无法遍历");
  50.         }
  51.     }
  52.     //后序遍历
  53.     public void postOrder() {
  54.         if(this.root != null) {
  55.             this.root.postOrder();
  56.         }else {
  57.             System.out.println("二叉树为空，无法遍历");
  58.         }
  59.     }
  60. }
  62. //先创建 HeroNode 结点
  63. class HeroNode {
  64.     private int no;
  65.     private String name;
  66.     private HeroNode left; //默认 null
  67.     private HeroNode right; //默认 null
  68.     public HeroNode(int no, String name) {
  69.         this.no = no;
  70.         this.name = name;
  71.     }
  72.     public int getNo() {
  73.         return no;
  74.     }
  75.     public void setNo(int no) {
  76.         this.no = no;
  77.     }
  78.     public String getName() {
  79.         return name;
  80.     }
  81.     public void setName(String name) {
  82.         this.name = name;
  83.     }
  84.     public HeroNode getLeft() {
  85.         return left;
  86.     }
  87.     public void setLeft(HeroNode left) {
  88.         this.left = left;
  89.     }
  90.     public HeroNode getRight() {
  91.         return right;
  92.     }
  93.     public void setRight(HeroNode right) {
  94.         this.right = right;
  95.     }
  96.     @Override
  97.     public String toString() {
  98.         return "HeroNode [no=" + no + ", name=" + name + "]";
  99.     }
  100.     //编写前序遍历的方法
  101.     public void preOrder() {
  102.         System.out.println(this); //先输出父结点
  103.         //递归向左子树前序遍历
  104.         if(this.left != null) {
  105.             this.left.preOrder();
  106.         }
  107.         //递归向右子树前序遍历
  108.         if(this.right != null) {
  109.             this.right.preOrder();
  110.         }
  111.     }
  112.     //中序遍历
  113.     public void infixOrder() {
  114.         //递归向左子树中序遍历
  115.         if(this.left != null) {
  116.             this.left.infixOrder();
  117.         }
  118.         //输出父结点
  119.         System.out.println(this);
  120.         //递归向右子树中序遍历
  121.         if(this.right != null) {
  122.             this.right.infixOrder();
  123.         }
  124.     }
  125.     //后序遍历
  126.     public void postOrder() {
  127.         if(this.left != null) {
  128.             this.left.postOrder();
  129.         }
  130.         if(this.right != null) {
  131.             this.right.postOrder();
  132.         }
  133.         System.out.println(this);
  134.     }
  135. }