企业官网建设流程全解析

二叉树

• 树的概念
  树是⼀种非线性的数据结构，它是由n（n>=0）个有限结点组成⼀个具有层次关系的集合

  • 树的特点
    • 有⼀个特殊的结点，称为根结点，根结点没有前驱结点
    • 除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、…、Tm，其中每⼀个集合Ti(1 <= i <=m)⼜是⼀棵与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有0个或多个后继
    • 树是递归定义的
    • 【注意】：树形结构中，⼦树之间不能有交集，否则就不是树形结构

• 相关概念
  

  • 结点的度：一个结点含有子树的个数称为该结点的度；如上图：A的度为6
  • 树的度：一棵树中，所有结点度的最大值称为树的度；如上图：树的度为6
  • 叶子结点或终端结点：度为0的结点称为叶结点；如上图：B、C、H、I.等节点为叶结点
  • 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点
  • 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
  • 根结点：一棵树中，没有双亲结点的结点；如上图：A
  • 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
  • 树的高度或深度：树中结点的最大层次；如上图：树的高度为4

  ---

  • 非终端结点或分支结点：度不为0的结点；如上图：D、E、F、G.等节点为分支结点
  • 兄弟结点：具有相同父结点的结点互称为兄弟结点；如上图：B、C是兄弟结点
  • 堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
  • 结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
  • 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
  • 森林：由m（m>=0）棵互不相交的树组成的集合称为森林

• 二叉树

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

• 二叉树的模拟实现

  • 二叉树接口

    packageDataStructure.DS_BinaryTree;publicinterfaceITree{/** * 判断是否为完全二叉树 * @param root 根节点 * @return true 完全二叉树 */booleanisCompleteBinaryTree(TreeNoderoot);/** * 根据值查找节点 * @param root 根 * @param val 待查找值 * @return 找到的TreeNode，null未找到 */TreeNodefind(TreeNoderoot,intval);/** * 获取树高度 * @param root 根 * @return 高度 */intgetHeight(TreeNoderoot);/** * 获取第k层节点数量 * @param root 根 * @param k 层数，从1开始 * @return 节点数 */intgetKLevelNodeCount(TreeNoderoot,intk);/** * 获取叶子结点个数 * @param root 根 * @return 叶子数量 */intgetLeafNodeCount(TreeNoderoot);/** * 二叉树总节点个数 * @param root 根 * @return 总节点数 */intsize(TreeNoderoot);/** * 先序遍历 * @param root 根 */voidpreOrderTraverse(TreeNoderoot);/** * 中序遍历 * @param root 根 */voidinOrderTraverse(TreeNoderoot);/** * 后序遍历 * @param root 根 */voidpostOrderTraverse(TreeNoderoot);/** * 层序遍历 * @param root 根 */voidlevelOrderTraverse(TreeNoderoot);}

  • 二叉树的功能

    • 前序遍历

      /** * 先序遍历：根 -> 左 -> 右 * 递归实现，直接打印节点数据 * @param root 根节点 */publicvoidpreOrderTraverse(TreeNoderoot){if(root==null)return;System.out.print(root.data+" ");preOrderTraverse(root.lchild);preOrderTraverse(root.rchild);}

    • 中序遍历

      /** * 中序遍历：左 -> 根 -> 右 * 递归实现，直接打印节点数据 * @param root 根节点 */publicvoidinOrderTraverse(TreeNoderoot){if(root==null)return;inOrderTraverse(root.lchild);System.out.print(root.data+" ");inOrderTraverse(root.rchild);}

    • 后序遍历

      /** * 后序遍历：左 -> 右 -> 根 * 递归实现，直接打印节点数据 * @param root 根节点 */publicvoidpostOrderTraverse(TreeNoderoot){if(root==null)return;postOrderTraverse(root.lchild);postOrderTraverse(root.rchild);System.out.print(root.data+" ");}

    • 层序遍历

      /** * 层序遍历（广度优先遍历） * 使用队列完成，从上到下，同一层从左到右打印 * @param root 根节点 */publicvoidlevelOrderTraverse(TreeNoderoot){if(root==null)return;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNodecur=queue.poll();System.out.print(cur.data+" ");// 左孩子不为空入队if(cur.lchild!=null)queue.offer(cur.lchild);// 右孩子不为空入队if(cur.rchild!=null)queue.offer(cur.rchild);}}

    • 获取树中节点的个数

      /** * 统计二叉树结点总个数 * @param root 根节点 * @return 全部节点数量，空树返回0 */publicintsize(TreeNoderoot){if(root==null)return0;// 当前节点1个 + 左子树节点数 + 右子树节点数return1+size(root.lchild)+size(root.rchild);}

    • 获取叶⼦节点的个数

      /** * 获取叶子结点的个数 * 叶子节点：左右孩子都为null的节点 * @param root 根节点 * @return 叶子节点总数，空树返回0 */publicintgetLeafNodeCount(TreeNoderoot){if(root==null)return0;// 当前是叶子节点，计数+1if(root.lchild==null&&root.rchild==null)return1;// 左子树叶子 + 右子树叶子returngetLeafNodeCount(root.lchild)+getLeafNodeCount(root.rchild);}

    • 获取第K层节点的个数

      /** * 获取第K层的节点个数，层数从1开始 * @param root 根节点 * @param k 目标层数，k>=1 * @return 第k层节点数量，root为null或k非法返回0 */publicintgetKLevelNodeCount(TreeNoderoot,intk){// 树为空 或者层数不合法直接返回0if(root==null||k<=0)return0;// k=1代表当前就是目标层，节点数为1if(k==1)return1;// 左子树k-1层 + 右子树k-1层节点之和returngetKLevelNodeCount(root.lchild,k-1)+getKLevelNodeCount(root.rchild,k-1);}

    • 获取⼆叉树的⾼度

      /** * 获取二叉树的高度（深度） * 递归：当前树高度 = max(左子树高度,右子树高度) + 1 * @param root 根节点 * @return 树的高度，空树返回0 */publicintgetHeight(TreeNoderoot){if(root==null)return0;intleftHeight=getHeight(root.lchild);intrightHeight=getHeight(root.rchild);returnMath.max(leftHeight,rightHeight)+1;}

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

      /** * 在二叉树中查找值为val的节点 * 先序递归遍历查找 * @param root 根节点 * @param val 需要查找的目标数值 * @return 找到返回对应TreeNode，找不到返回null */publicTreeNodefind(TreeNoderoot,intval){// 递归终止条件：当前节点为空if(root==null)returnnull;// 当前节点就是目标节点，直接返回if(root.data==val)returnroot;// 递归查找左子树TreeNodeleft=find(root.lchild,val);// 左子树找到，直接返回if(left!=null)returnleft;// 左子树没找到，去右子树查找returnfind(root.rchild,val);}

    • 判断⼀棵树是不是完全⼆叉树

      /** * 判断一棵树是否为完全二叉树 * 思路：层序遍历，遇到null节点后，后续不能再出现非null节点 * @param root 二叉树根节点 * @return true：是完全二叉树；false：不是完全二叉树 */publicbooleanisCompleteBinaryTree(TreeNoderoot){// 空树认为是完全二叉树if(root==null)returntrue;Queue<TreeNode>que=newLinkedList<>();que.offer(root);// 标记是否已经遇到空节点booleanflag=false;while(!que.isEmpty()){TreeNodenode=que.poll();if(node==null){// 遇到空节点，置标记为trueflag=true;}else{// 如果之前已经遇到过null，现在又出现非空节点，说明不是完全二叉树if(flag)returnfalse;// 无论孩子是否为null，全部入队que.offer(node.lchild);que.offer(node.rchild);}}returntrue;}

• 二叉树模拟实现完整代码

  packageDataStructure.DS_BinaryTree;importjava.util.LinkedList;importjava.util.Queue;/** * 二叉树基础实现类 * 提供二叉树遍历、统计节点、高度、查找、判断完全二叉树等基础功能 */publicclassMyBinaryTree{/** * 判断一棵树是否为完全二叉树 * 思路：层序遍历，遇到null节点后，后续不能再出现非null节点 * @param root 二叉树根节点 * @return true：是完全二叉树；false：不是完全二叉树 */publicbooleanisCompleteBinaryTree(TreeNoderoot){// 空树认为是完全二叉树if(root==null)returntrue;Queue<TreeNode>que=newLinkedList<>();que.offer(root);// 标记是否已经遇到空节点booleanflag=false;while(!que.isEmpty()){TreeNodenode=que.poll();if(node==null){// 遇到空节点，置标记为trueflag=true;}else{// 如果之前已经遇到过null，现在又出现非空节点，说明不是完全二叉树if(flag)returnfalse;// 无论孩子是否为null，全部入队que.offer(node.lchild);que.offer(node.rchild);}}returntrue;}/** * 在二叉树中查找值为val的节点 * 先序递归遍历查找 * @param root 根节点 * @param val 需要查找的目标数值 * @return 找到返回对应TreeNode，找不到返回null */publicTreeNodefind(TreeNoderoot,intval){// 递归终止条件：当前节点为空if(root==null)returnnull;// 当前节点就是目标节点，直接返回if(root.data==val)returnroot;// 递归查找左子树TreeNodeleft=find(root.lchild,val);// 左子树找到，直接返回if(left!=null)returnleft;// 左子树没找到，去右子树查找returnfind(root.rchild,val);}/** * 获取二叉树的高度（深度） * 递归：当前树高度 = max(左子树高度,右子树高度) + 1 * @param root 根节点 * @return 树的高度，空树返回0 */publicintgetHeight(TreeNoderoot){if(root==null)return0;intleftHeight=getHeight(root.lchild);intrightHeight=getHeight(root.rchild);returnMath.max(leftHeight,rightHeight)+1;}/** * 获取第K层的节点个数，层数从1开始 * @param root 根节点 * @param k 目标层数，k>=1 * @return 第k层节点数量，root为null或k非法返回0 */publicintgetKLevelNodeCount(TreeNoderoot,intk){// 树为空 或者层数不合法直接返回0if(root==null||k<=0)return0;// k=1代表当前就是目标层，节点数为1if(k==1)return1;// 左子树k-1层 + 右子树k-1层节点之和returngetKLevelNodeCount(root.lchild,k-1)+getKLevelNodeCount(root.rchild,k-1);}/** * 获取叶子结点的个数 * 叶子节点：左右孩子都为null的节点 * @param root 根节点 * @return 叶子节点总数，空树返回0 */publicintgetLeafNodeCount(TreeNoderoot){if(root==null)return0;// 当前是叶子节点，计数+1if(root.lchild==null&&root.rchild==null)return1;// 左子树叶子 + 右子树叶子returngetLeafNodeCount(root.lchild)+getLeafNodeCount(root.rchild);}/** * 统计二叉树结点总个数 * @param root 根节点 * @return 全部节点数量，空树返回0 */publicintsize(TreeNoderoot){if(root==null)return0;// 当前节点1个 + 左子树节点数 + 右子树节点数return1+size(root.lchild)+size(root.rchild);}/** * 先序遍历：根 -> 左 -> 右 * 递归实现，直接打印节点数据 * @param root 根节点 */publicvoidpreOrderTraverse(TreeNoderoot){if(root==null)return;System.out.print(root.data+" ");preOrderTraverse(root.lchild);preOrderTraverse(root.rchild);}/** * 中序遍历：左 -> 根 -> 右 * 递归实现，直接打印节点数据 * @param root 根节点 */publicvoidinOrderTraverse(TreeNoderoot){if(root==null)return;inOrderTraverse(root.lchild);System.out.print(root.data+" ");inOrderTraverse(root.rchild);}/** * 后序遍历：左 -> 右 -> 根 * 递归实现，直接打印节点数据 * @param root 根节点 */publicvoidpostOrderTraverse(TreeNoderoot){if(root==null)return;postOrderTraverse(root.lchild);postOrderTraverse(root.rchild);System.out.print(root.data+" ");}/** * 层序遍历（广度优先遍历） * 使用队列完成，从上到下，同一层从左到右打印 * @param root 根节点 */publicvoidlevelOrderTraverse(TreeNoderoot){if(root==null)return;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNodecur=queue.poll();System.out.print(cur.data+" ");// 左孩子不为空入队if(cur.lchild!=null)queue.offer(cur.lchild);// 右孩子不为空入队if(cur.rchild!=null)queue.offer(cur.rchild);}}}