二叉树的回顾在上一篇文章中，我们回顾了二叉树的几个基本概念，同时比较了线性结构和树形结构，总结了几种常见二叉树的性质，如二叉树、真二叉树、完全二叉树、满二叉树等。但是我们只理解了二叉树的概念，没有编码。今天我们将改进这一步，直接进入二叉树的设计和编码。 属性和节点。首先，我们的二叉树是用来存储元素的。同时，它还需要知道它的父节点和它的子节点之间的关系。因此，很容易想到使用节点类。那么，二叉树的节点类应该如何设计呢？同时，我的二叉树类应该具备哪些基本元素？//树节点数受保护int size//树的根节点是受保护的节点；根；这里先不说为什么保护访问修饰符。先说如何设计节点类。我们需要知道一个节点的父节点，左右子节点的关系，节点中存储的element元素。那么我们的节点应该是这样的:/* * *设置自己的节点类来维护二叉树* @ param < E & gt*/protected静态类节点& ltE & gt{ E元素；节点& ltE & gt左；节点& ltE & gt对；节点& ltE & gt父母；/* * *构造函数，添加节点时需要指定元素*的父节点，但不确定是否有左右子节点* @ param element * @ param parent */public node(ee element，node < E & gtparent){ this . element = element；this.parent = parent}/* * *判断是否可以是叶节点* @ return */public boolean是leaf(){ return left = = null & & amp；right = = null}/* * *确定左右子节点是否可以有* @ return */public boolean children(){ return left！= null & amp& amp对！= null}}这个节点类提供了一个构造函数和两个唯一的方法。对于构造函数，在初始化时，我们需要指定存储在节点和父节点中的元素。左右子节点为什么不初始化？因为当你添加一个节点时，你必须知道它的父节点，但是你不知道它是否有子节点。 对于另外两种方法，我认为这是node类特有的行为。因为节点的概念在二叉树中是通用的，所以直接封装在node类中，而不是后面。对于每一棵唯一的二叉树，在写之前都要判断叶子节点和度为2的节点，太繁琐了。对于前面提到的size、root和node类，这些应该是二叉树的内部逻辑。不对外开放，外界不知道节点类。它只需要指定节点，也就是二叉树存储的类型，但是我们需要对外开放接口，通过接口使用二叉树，也就是说你只需要知道怎么用，不需要知道我是怎么实现的。 二叉树的公共接口， 我们对外提供的方法应该有以下方法:public int size()-获取元素节点数public boolean isempty()-判断树是否可以是空树public void clear()-清除树的所有元素public void preorder () ——前序遍历public void inorder() ——中序遍历public void posorder()——后序遍历public void levelOrder() ——序列遍历public int height() ——计算树公共布尔isComplete()的高度——判断是否可以是一个完整的二叉树公共布尔is properter()——判断是否可以是一个真正的二叉树公共字符串toString() —— re-toString方法，这些基本上都是我们提供给外界的打印二叉树的方法。 那么问题来了，我们可以有疑惑。既然用二叉树存储元素，为什么没有办法添加和删除节点？那么这样的树出来新的以后就是空树了，你不记得了吗？很清楚我没有忘记，就是不提供添加或者移除的方法。 让我们考虑一下。有以下代码:二叉树< Integer & gtbTree = new BinaryTree<。& gt();btree . add(9)；btree . add(5)；btree . add(8)；很明显第一个添加的元素9是根节点，那么问题来了。下一个5是9的左子节点还是右子节点，8应该是5的兄弟节点还是左右子节点中的一个？是的，我们没有一个明确的添加二叉树的规则，写起来很麻烦，没有意义。当然，我们可以默认加到左边或者右边，但是没有太大意义。没有明确的规则，就是普通的二叉树，没什么用。规则是树的特性，如二分搜索法树、红黑树、AV树等。，都有明确的规则。 我们实际上是在普通二叉树上添加了少量自己设定的逻辑和规则，所以这里的二叉树类实际上应该是基类，添加、删除等特殊规则应该在继承普通二叉树的基础上编写，而二叉树提供了少量的通用方法。 这也是BinaryTree的属性的访问修饰符被设计成受保护的原因。简单方法public int size()-获取元素节点数/* * *获取元素节点数* @ return */public int size(){ return size；} public boolean isempty()-判断树是否可以为空/* *判断树是否可以为空* @ return */public boolean isempty(){ return size = = 0；} public void clear()-清空树的所有元素/* *清空树的所有元素*/public void clear(){ root = null；大小= 0；}简单的方法可以直接放出来，一目了然的遍历就可以了。对于数组和链表这样的数据结构，我们可以遍历它们，得到所有的元素。线性数据结构的遍历比较简单——正序遍历和逆序遍历。对于我们的二叉树，也要根据节点的不同访问顺序提供遍历方法。二叉树有四种常见的遍历方法:前序遍历、中序遍历、后序遍历、层次序遍历。我们以二进制搜索树- {7，4，9，2，5，8，11，3，12，1}为例，分析了这四种遍历方法的访问顺序:根节点、左子树和右子树。遍历结果(首先访问根节点)是:7，4，2，1，3，5，5。但是，它提供了。想看的话，后面会上传完整代码到Github，需要重新下载。下载时注意dev分支，这是最新的代码实现步骤:利用栈的先进后出特性:设置node = root，将root放入栈中，循环执行以下操作，直到栈为空，栈顶节点弹出。访问stack top . right to stack top.left/* * *迭代-preorder遍历*/private void preorderbiteration(){ if(root = = null)返回；堆栈& lt节点& ltE & gt& gtstack =新堆栈& lt& gt();stack . push(root)；而(！stack . isempty()){ Node & lt；E & gtnode = stack . pop()；system . out . print(node . element+" ")；if (node.right！= null){ stack . push(node . right)；} if (node.left！= null){ stack . push(node . left)；}}}中序遍历访问顺序:-(根节点访问于)1。左子树中序遍历，根节点，右子树中序遍历(如果是二叉查找树，结果是升序)2。右子树中序遍历，根节点，左子树中序遍历(如果是二叉查找树，结果降序)遍历结果为:1，2，3，4，5，7，8，9，10，11，12(升序)。实现步骤:利用堆栈的先进后出特性:设置node = root，将root放入堆栈，循环执行以下操作，直到堆栈为空。If节点！= null将node放入栈中，set node = node.left如果node == null，如果栈为空，则结束遍历，如果栈不为空，则弹出栈顶元素并赋给node，访问节点并设置node = node.right/** *迭代实现-中序遍历*/private void inorder迭代(){if (root = = null)返回；堆栈& lt节点& ltE & gt& gtstack =新堆栈& lt& gt();节点& ltE & gt节点=根；while(节点！= null ||！stack.isEmpty()) { while (node！= null){ stack . push(node)；node = node.left} node = stack . pop()；system . out . print(node . element+" ")；node = node.right}}}后序遍历访问顺序:左子树后序遍历、右子树后序遍历、根节点——(最后访问根节点)遍历结果为:1、3、2、5、4、8、10、12、11、9、7。实现步骤:利用栈的后进先出特性:设置node = root，将root放入栈中。直到堆栈为空。如果栈顶节点是叶节点或者上次访问的节点是顶节点的子节点，则弹出顶节点进行访问。否则，将顶部节点的右侧和左侧按顺序放入堆栈。/* *迭代实现-后序遍历*/private void postorderbyiteration(){ if(root = = null)返回；节点& ltE & gt节点=根；//记录最后访问的节点node < E & gtlastVisited = null堆栈& lt节点& ltE & gt& gtstack =新堆栈& lt& gt();while(节点！= null ||！stack.isEmpty()) { while (node！= null){ stack . push(node)；node = node.left} node = stack . pop()；//栈顶节点是叶节点或者最后访问的节点是顶节点的子节点if(node . right = = null | | node . right = = last visited){ system . out . print(node . element+" ")；lastVisited = node//这里节点没有改变指向，所以需要指向null，否则就是无限循环node = null}else {//如果不是子节点，且上次访问的节点不是栈顶节点的子节点，则表示是一个操作符节点，然后重新进入stack . push(node)；node = node.right}}}顺序遍历访问顺序:从上到下、从左到右依次访问每个节点。遍历结果为:7，4，9，2，5，8，11，1，3，10，12。序列遍历是以迭代的方式实现的，利用队列的先入先出特性可以很好地实现序列遍历的步骤:利用队列的先入先出特性对根节点进行根操作。直到队列为空，将头节点出队，访问它，将节点的左子节点排队，将节点的右子节点排队。画一波图:组合图，看代码，很清楚/* *顺序遍历，迭代方式*/public void levelroldertraversal(){ if(root = = null)return；队列& lt节点& ltE & gt& gtqueue = new LinkedList & lt& gt();//queue . offer(root)；而(！queue . isempty()){ Node & lt；E & gtnode = queue . poll()；system . out . print(node . element+" ")；//如果有左子节点，则入队if (node.left！= null){ queue . offer(node . left)；}//如果有右子节点，加入团队if (node.right！= null){ queue . offer(node . right)；}}}补充如果我对二叉树的四种遍历方式还很迷茫，我只是画了静态图的顺序，看的时候可能不太懂，但是有时候画图会花很长时间。看了图，再回来看，相信遍历接口的对比会少量加强:以上四种遍历方法都写了，但是你觉得这样的遍历功能够用吗？或者说，你觉得这和我们之前在动态数组、链表、栈、队列的遍历有什么区别？没有读过动手写——动态数组、链表、栈、队列的同学，有兴趣的可以点一下关键词，看看我们能不能简单写出JDK数组或者动态链表遍历的代码://遍历数组int[] arr = {1，2，3，4，5，6，7，8，9 }；for(int value:arr){ system . out . println(value)；}//遍历链表< Integer & gtlist = new LinkedList<。& gt(){{添加(1)；添加(2)；增加(3)；增加(4)；增加(5)；}};for(int value:list){ system . out . println(value)；}这个看起来没有问题。二叉树遍历是system . out . print(node . element)；数组和链表是system . out . println(value)；都印好了。能有什么区别呢？ 上面的代码可能会令人困惑。我们再来看另一个代码:int[] arr = {1，2，3，4，5，6，7，8，9 }；for(int value:arr){ system . out . println(value+"-& gt；+“卡尔顿是个帅哥”)；}嗨，这是醒目的。同时数组可以打印出存储在节点中的元素，同时补充一句Kalton很帅，但是上面二叉树的遍历就做不到了，因为一个写在类内，一个写在类外。 不同的是二叉树的遍历只是打印一次元素，并没有真正得到二叉树中存在的元素，而数组和链表的遍历是得到每一个元素。至于怎么做，打印还是添加，或者卡尔顿是个帅哥，这些遍历规则都是调用者自己定的，而不是写死的。因此，我们应该在遍历二叉树时将节点元素传递给调用者。遍历规则由客户自己设置。当我们这样做时，我们编写一个通用内部类Visitor:/* * *来提供一个外部遍历接口* @ param < E & gt*/公共抽象静态类访问者& ltE & gt{//遍历停止遍历的标记布尔停止；/* * * visit方法将节点元素传递给调用方* @param element * @return。如果返回true，则结束遍历*/抽象布尔访问(ee element)；}visit方法，其方法参数为E元素，遍历时接收节点元素，并传递给外部调用方。如果返回值为真，则意味着客户希望结束遍历。下面以preamble遍历为例来实现我们的逻辑:/* * *迭代方法-preamble遍历* @ param visitor */public void preamble迭代(visitor < E & gtvisitor){ if(root = = null | | visitor = = null)返回；堆栈& lt节点& ltE & gt& gtstack =新堆栈& lt& gt();stack . push(root)；而(！stack . isempty()){ Node & lt；E & gtnode = stack . pop()；//将其传递给外部调用方。如果条件成立，则停止遍历if(visitor . visit(node . element))return；if (node.right！= null){ stack . push(node . right)；} if (node.left！= null){ stack . push(node . left)；}}}其实客户需要自己传入遍历规则类Visitor集合，然后在我们原来的方法打印元素的地方改成if(Visitor . visit(node . element))return；，也就是将节点元素返回给方法调用方，使用被调用的遍历规则。同时向二叉树类返回一个布尔变量值，由stop接收，告知是否可以完成遍历。所以遍历完了，客户也自己定规则。但是，一个不好的地方是，当我们调用二叉树的遍历方法时，需要强制一个遍历规则类。同时无论我们的遍历方法是递归还是迭代都暴露了调用者，所以我做了一个小包装:/* * Preorder遍历——如果客户没有通过遍历规则，默认print element */public void Preorder(){ Preorder(new visitor < & gt；(){ @ Override boolean visit(E element){ system . out . print(element+" ")；返回false} });}/* * *加强前序遍历，提供调用者自己编写遍历规则* @ paramvisitor */public void前序(visitor < E & gtvisitor) { if (visitor == null)返回；/* * *底层使用递归方法*//preorderbyrecursion(root，visitor)；/* * *底层使用迭代法*/preorderByIteration(visitor)；system . out . println()；}public void preorder()方法不需要传递参数，默认的遍历规则是打印节点元素，而客户需要自己设置比较规则来调用public void preorder(visitor < E & gt；访客)，传入比较器。至于是用preorderByRecursive递归还是preorderByIteration，客户也不知道。是我们在设计时决定的，其他三种遍历都是同样的逻辑。代码比较长，没必要展示，就不贴了。我会在后面给出GitHub的地址。如有必要，在二叉树的前奏中，我们已经讲过完全二叉树和真二叉树的特征和性质，这里不再赘述。其实他们对树高的判断和计算都是基于序列遍历的方法，所以序列遍历很重要。最好给我手写的判定完全二叉树的步骤:/* *判定是否可以是完全二叉树——(顺序遍历)* @ return */public boolean is complete(){ if(root = = null)返回false队列& lt节点& ltE & gt& gtqueue = new LinkedList & lt& gt();queue . offer(root)；布尔叶=假；而(！queue . isempty()){ Node & lt；E & gtnode = queue . poll()；如果(叶子& amp& amp！node.isLeaf())返回falseif (node.left！= null){ queue . offer(node . left)；} else if (node.right！= null) {//等同于node.left = = null & ampnode .对！= null返回false} if (node.right！= null){ queue . offer(node . right)；} else {//node . left = = null & amp；& ampnode.right == null //node.left！= null & amp& ampNode.right == null //后面遍历的所有节点都必须是叶节点leaf = true} }返回true}确定真二叉树的步骤:1。利用队列的先进先出特性；2.利用真实二叉树的节点的度为0或2的特性；3.在遍历序列时，如果levelSize% 2！= 0，返回到flase4。结合上面的顺序遍历的示意图，你会发现每一层的节点被遍历后，队列大小的节点数等于下一层的节点数，而第一层只有根节点/* *来判断是否可以是真二叉树——(顺序遍历)* @ return */public boolean is proper(){ if(root = = null)返回false//每层元素个数存储int levelSize = 1；队列& lt节点& ltE & gt& gtqueue = new LinkedList & lt& gt();queue . offer(root)；而(！queue . isempty()){ Node & lt；E & gtnode = queue . poll()；levelSize-；if (node.left！= null){ queue . offer(node . left)；} if (node.right！= null){ queue . offer(node . right)；}//表示即将访问下一层if(levelSize = = 0){//每访问一层后，下一层的节点数为队列的大小levelSize = queue . size()；if (levelSize % 2！= 0)返回false} }返回true}树的高度树的高度其实就是树的层数，非常接近真二叉树的上述判断。只要设置一个高度，当你遍历每一层的时候，height++，遍历完之后，返回树的高度。其实所有子节点的高度都是最大的，然后+1。这种思想很容易递归实现，所以计算树的高度。有两种方法:递归和迭代。递归方法贴在这里。因为迭代法是上面判断二叉树的方法，就不贴了。如果需要，自己下载源代码。 /* * *计算树的高度* @return */public int height(){ //递归方法返回heightbyrecursife(root)；//迭代方法//返回heightbypiteration()；}/* * *(递归方法)获取传入节点的高度* @ param node * @ return */Private Int heightbyrecursife(node < E & gt；node){ if (node == null)返回0；return 1+math . max(heightbyrecursife(node . left)，heightbyrecursife(node . right))；}前任和继任者搜索前任节点根据上述判断条件给出实现代码:/* * *获取传入节点的前任节点* @ param node * @ return */protected node < E & gt；前任(节点& ltE & gtnode) { if (node == null)返回null；//前置节点在左子树(left.right.right.right...)节点< E >p = node.left如果(p！= null) { while (p.right！= null){ p = p . right；}返回p；}//查找前置节点while (node.parent！= null & amp& ampnode = = node . parent . left){ node = node . parent；}//node . parent = = null//node = = node . parent . right返回node . parent；}根据上述判断条件找到后继节点并给出实现代码:/* * *获取传入节点的后继节点* @ param node * @ return */protected node < E & gt；后继者(节点& ltE & gtnode) { if (node == null)返回null；//前置节点在左子树(right.left.left.left...)节点< E >p = node.right如果(p！= null) { while (p.left！= null){ p = p . left；}返回p；}//查找前置节点while (node.parent！= null & amp& ampnode = = node . parent . right){ node = node . parent；}返回node.parent}现在，我们可能很迷茫。这两种方法寻找前任或继任节点有什么用？不知道大家有没有看到方法的访问修饰符:protected。实际上，这意味着两个方法都没有调用给客户。就像我们的困惑，客户不知道怎么用，也不知道怎么处理。实际上是用来继承BinaryTree类的子类，其作用是在删除度为2的情况下，寻找前任或继任节点。 总结到目前为止，我们已经复习了二叉树的基本概念，并编写了一般方法的设计。我们对二叉树的结构有积极的认识，但有时候知识总是在你以为记住的时候溜走。所以，把学到的东西总结成笔记，以便以后阅读，加深印象。 最后，如果看完还有什么不明白的，可以在下面留言讨论。感谢您的观看。 记得关注我，觉得文章对你有帮助就给我赞！作者:闫芳参考链接:https://www.cnblogs.com/kalton/p/13689985.html