二叉树二叉树的定义二叉树是n（n>=0）个节点的有限集，它要么是一棵空树（n=0），要么由一个根节点组成的两棵不相交的二叉树分别称为左子树和右子树。二叉树是一个有序树，每个节点最多有两个子树。二叉树的子树通常被称为“左子树”和“右子树”。左右子树的顺序不能互换。各种形式的二叉树二叉树有不同的形式。根据问题处理的一般情况和特殊情况的分类处理原则，我们可以将二叉树的五种基本形式和两种特殊形式分类，便于对二叉树的讨论。(1)二叉树的基本形式，二叉树可以是空集：根节点可以有空的左子树或右子树；或者左右子树都为空。(2)二叉树的特殊形式：①满二叉树(FullBinaryTree)满二叉树是一棵二叉树，其中除叶子节点外，每个节点都有左右子树，叶子节点在底部。或者，如果一棵深度为k的二叉树有2的k-1次方节点，则称为满二叉树。②完全二叉树（CompleteBinaryTree）如果一棵树除底层外，每层的节点数达到最大值，底层要么满，要么缺少右边连续的节点数（要求从右下角），那么这棵二叉树就是一棵完全二叉树。如下图所示：可以说满二叉树是完全二叉树的特例。基本操作是根据二叉树的逻辑结构定义的。二叉树有以下基本操作：构造：构建一棵二叉树查找：查找根节点、父节点、子节点、叶节点等插入：在指定位置插入节点删除：删除指定位置的节点位置遍历：按照一定的搜索路线，依次访问二叉树中的每个节点，并且只访问一次。深度：计算二叉树的深度链结构及其二叉链表的基本实现。二叉树的每个节点包含两个指针字段以指向相应的分支。我们一般称它为二进制链表。对应的数据结构说明：publicclassBinaryTreeNode{privateintdata;私有二叉树节点左树节点；privateBinaryTreeNoderightTreeNode;}这种形式的二叉树，我们得到一个节点后，很容易得到它的子节点，而得到它的父节点就比较困难了。如果我们想在获取节点的时候方便的获取它的父节点和它的子节点怎么办？三叉链表这也是一个三叉链表。当一个节点存储子节点时，它存储父节点的位置，如下图所示：基本属性二叉树的第i层最多有2i-1个节点(i>=1)证明归纳：i=1层，只有一个根节点，21-1=20=1。归纳假设对于所有n，n>=1，命题成立。归纳证明：二叉树中每个节点至多有两个子树，则第n+1层的节点数为2n-1*2=2n。命题成立。深度为h的二叉树最多有2h-1个节点（h>=1）。证明：根据上述性质，一棵深度为k的二叉树的节点数至多为：20+21+.....+2k-1=2k-1。对于任意一棵二叉树，如果它包含n0个叶子节点和n2个度数为2的节点，必然存在关系：n0=n2+1。令n1为度数为1的节点数。叶子节点的度数为0，度数为一棵二叉树只能是0,1,2设二叉树的总节点数：n=n0+n1+n2。一棵二叉树的总分支数为：b=n1+2n2。树中的每个节点上都会有一个分支，但只有一个节点是例外——根节点。所以b=n-1=n0+n1+n2-1。因此，n0=n2+1。具有n个节点的完全二叉树的深度为[log2n]+1（方括号表示四舍五入）让深度一棵完全二叉树为k，则根据第二个性质，2k-1<=n<2k，即k-1<=log2nn，则该节点没有左节点，否则编号为2i的节点为其左子节点。如果2i+1>n，则该节点没有右子节点，否则编号为2i+1的节点为其右子节点。通过归纳可以证明，如果第i个节点有左节点，则左节点的编号为2i，如果有右节点，则为2i+1。i=1时成立。假设i=n时为真，假设有左子节点，数为2n，假设有右子节点，数为2n+1。如果有左子节点，就说明有右子节点，因为是完全二叉树，这两个节点是相邻的，所以编号为n+1的节点的左子树为2i+2、2i+3.结论成立。树遍历（Traversal）——树遍历（也称树搜索）是图遍历（GraphTraversal）的一种，是指按一定规则不重复地访问某一树结构的所有节点的过程。具体的访问操作可能是检查节点的值，更新节点的值等等。不同的遍历方法访问节点的顺序不同。树遍历在日常生活中也很常见：例1：机电设备开机自检的简单模型任何机电设备都是由几个部分组成的。例如，计算机硬件由板和非板等一系列设备组成。根据计算机的组成，可以建立计算机硬件组成的二叉树（其实就是多叉树），如下图所示：设备正常运行的前提是各个设备都正常工作。对于每一个设备及其部件乃至整个设备的状态是否正常，从底层开始检测显然是正确的。设备上电自检模型检测步骤：第一步：各设备（叶节点）自检正常第二步：对二叉树进行“后序遍历”，直到逐级检测到根节点。第三步：如果有错误提示，会报错，否则会显示设备正常。第四步：结束。具体检测步骤如下：左子树：网卡等正常->PCI正常->显卡等正常->非PCI正常->板卡正常。右子树：硬盘等正常->外存正常->键盘等正常->其他正常->非板卡正常。整棵树：BoardOK->Non-boardOK->ComputerOK。在上面的检测过程中，“后序遍历”是指树的根节点是最后被访问的，无论是整棵树还是左右子树。示例2：网购商品管理某网购食品店按照品类、颜色和品种对商品进行分类和组织。分类图如下：通过程序自动读取树形结构中的信息并打印出所有产品名称应该怎么做？怎么可能清楚无遗漏呢？我们可以先分析一个列表中数据的规律，如下图所示：从树到表的打印顺序是怎样的？根节点：Food左子树：Meat->Pork/Beef右子树：Fruit->(leftsubtree)Yellow->BananaFruit->(leftsubtree)Red->Cherry打印的顺序是根节点的首先访问树，无论是整棵树还是左右子树。以这样的规则访问树的节点，我们可以用一个词来称呼它——前序遍历。根据搜索策略的不同，二叉树的遍历可以分为广度优先搜索和深度优先搜索两种方式。树的广度优先遍历广度优先遍历是连通图的一种遍历策略，因其思想是从一个顶点开始，径向遍历与其直接相邻的广阔节点区域，故而得名。二叉树的广度优先遍历也称为层次遍历。从二叉树的第一层（根节点）开始，从上到下逐层遍历。在同一层中，节点按照从左到右的顺序逐一访问。树的广度优先遍历操作是从根节点开始访问，然后以这个节点为线索依次访问与其直接相邻的节点（子节点）序列，然后在中应该使用什么样的节点广度遍历的下一步？点开始线程。如下图所示，第一次访问的节点是A，在链式存储结构上搜索A的直接邻居。如果有两个节点B和C，那么可以访问的节点顺序是ABC。下面A新的搜索节点从B开始，即以访问过的节点序列中第一个还没有被线索的节点作为线索，重复该操作，直到访问完所有节点。上述操作过程是在“已访问序列”中不断向后移动线索节点，并在“已访问序列”中不断添加新的访问节点的过程。因此，“已访问序列”的操作过程是一个Queue处理方法。先进先出。二叉树的数据结构如下图所示：publicclassBinaryTreeNode{privateintdata;私有二叉树节点左树节点；privateBinaryTreeNoderightTreeNode;}queueadd和offer的区别：add抛出异常让你处理，offer返回false为广度优先树遍历：/***广度优先遍历*@paramroot根节点*/publicstaticvoidlevelOrder(BinaryTreeNoderoot){//LinkedListimplementsQueue我们使用LinkedList来实现queueLinkedListnodeQueue=newLinkedList<>();//根节点先入队nodeQueue.offer(root);while(nodeQueue.size()>0){BinaryTreeNodenode=nodeQueue.poll();System.out.println(node.getData());BinaryTreeNodeleftNode=node.getLeftTreeNode();如果（leftNode！=null）{nodeQueue.offer（leftNode）;}BinaryTreeNoderightNode=node.getRightTreeNode();if(rightNode!=null){nodeQueue.offer(rightNode);二叉树的深度优先遍历可以从二叉树的定义中得知。一棵二叉树由一个根组成结点，根结点的左子树，根结点的右子树三部分组成。因此，二叉树的遍历也可以相应地分解为三个“子任务”。①：访问根节点②：遍历左子树（即依次访问左子树上的所有节点）③：遍历右子树（即依次访问右子树上的所有节点）因为左子树和右子树都是二叉树（也可以是空二叉树）。它们的遍历可以按照上述注意事项继续分解，直到每棵子树都是一棵空二叉树。可以看出以上三个子任务之间的先后顺序。如果三个子任务分别用D、L、R表示，则有6种可能的顺序：①：DLR②：LDR③：LRD④：DRL⑤：RDL⑥：RLD通常我们有“先左后右”的限制"，即子任务二先于子任务三完成，所以只剩下三个阶数：DLR--先根遍历（前序遍历）LDR--中根遍历（中序遍历）LRD--后续遍历（或后序遍历）三种遍历方式定义如下：前序遍历：先访问根节点D，然后按照前序遍历的策略分别遍历D的左子树和右子树。先访问根节点，即每次遇到要遍历的子树，都先访问该子树的根节点。比较通俗的解释是：如果我到达一个节点，先打印当前节点，然后再访问其他节点。中序遍历：先按照中序遍历策略遍历根D的左子树，然后访问根节点D，最后按照中序遍历策略遍历D的右子树。在中间访问根。通俗的解释是：当我到达一个节点时，首先判断当前节点的左节点是否为空，如果有则向下访问，如果没有则打印当前节点。后续遍历：依次遍历根的左右子树，然后访问根节点D，最后访问到根。通俗的解释是：当我到达一个节点时，首先判断当前节点的左节点是否为空，如果是，则往下走，如果左子树为空，则访问现有节点，如果不是就打印当前节点。从定义上看，这就是递归，我们可以根据递归写代码：//前序遍历publicvoidfrontShow(BinaryTreeNoderoot){System.out.println(root.getData());如果(root.getLeftTreeNode()!=null){frontShow(root.leftTreeNode);}if(root.getRightTreeNode()!=null){frontShow(root.rightTreeNode);}}publicvoidmiddleShow(BinaryTreeNoderoot){if(root.getLeftTreeNode()!=null){frontShow(root.leftTreeNode);}System.out.println(root.getData());if(root.getRightTreeNode()!=null){frontShow(root.rightTreeNode);}}publicvoidrightShow(BinaryTreeNoderoot){if(root.getLeftTreeNode()!=null){frontShow(root.leftTreeNode);}if(root.getRightTreeNode()!=null){frontShow(root.rightTreeNode);}System.out.println(root.getData());}栈是实现递归时最常用的辅助结构。一个栈用来记录要遍历的节点，方便以后访问。我们可以把递归的深度优先遍历改成非递归的算法。(1)二叉树的每个节点非递归前序遍历的顺序是，一路向下访问其左链，边访问节点边压入栈，直到左链为空。然后节点从栈中弹出。对于每一个出栈节点，都意味着该节点及其左子树都被访问过，应该访问该节点的右子树。准备一个临时变量指向根节点并打印当前节点。当前临时变量指向左子节点并将其压入堆栈。重复(2)直到左孩子为NULL。然后，当前指针指向右孩子。如果栈不为空或者当前指针不为NULL，则执行(2)，否则结束。遇到节点就访问，把节点压入栈，然后遍历它的左子树。代码示例1：publicvoidfrontShowNoRecursion(BinaryTreeNoderoot){Stackstack=newStack<>();do{while(root!=null){System.out.println(root.getData());堆。推（根）；root=root.getLeftTreeNode();}if(!stack.isEmpty()){root=stack.pop();root=root.getRightTreeNode();}}while(!stack.isEmpty()||root!=null);//只要栈中有元素或者根不为null，就表示没有结束}代码示例2：publicvoidfrontShowNoRecursion2(BinaryTreeNoderoot){Stackstack=newStack<>();如果（root！=null）{stack.push（root）；while(!stack.isEmpty()){BinaryTreeNodehead=stack.pop();System.out.println(head);如果(head.rightTreeNode!=null){stack.push(head.rightTreeNode);}如果(head.leftTreeNode!=null){stack.push(head.leftTreeNode);}}}}代码示例2的思路是：先压入根节点，因为入栈是先进后出的，前序遍历是根左右，所以右节点需要先入栈，再入左节点(2)非递归中序遍历中序遍历的顺序是从左到右。根据栈的特性，为了实现这样的特性，越晚打印，越早入栈。遍历步骤为：先将整个左子树压入栈中。左子树如下图所示：当下一个节点不再有左子树时，出栈的每个节点都认为访问了它的左子树，然后打印当前节点，然后在本次使用方式访问当前节点的子树。publicvoidmiddleShowNoRecursion(BinaryTreeNodehead){Stackstack=newStack<>();while(!stack.isEmpty()||head!=null){if(head!=null){stack.push(head);head=head.leftTreeNode;}else{BinaryTreeNodenode=stack.pop();System.out.println(node.getData());head=node.rightTreeNode;}}}(3)非递归后序遍历后序遍历是左右根，即如果3426751的形式从右向左遍历：就是1576243，正好是后序遍历的逆形式。headrightleft的遍历形式是先按左，再按右。一个栈用来收集headerrightleft形式的节点，另一个栈用来收集headerright和left出栈的节点，实现后序遍历。代码示例1：publicvoidafterShowNoRecursion(BinaryTreeNoderoot){if(root!=null){Stacks1=newStack<>();Stacks2=newStack<>();s1.push(根);while(!s1.isEmpty()){BinaryTreeNodenode=s1.pop();s2.push（节点）；if(node.leftTreeNode!=null){s1.push(node.leftTreeNode);}if(node.rightTreeNode!=null){s1.push(node.rightTreeNode);}}while(!s2.isEmpty()){System.out.println(s2.pop().getData());}}}参考资料《数据结构与算法分析新视角》周兴妮、任志远、马延灼、范凯编着
