- @return
*/
public boolean hasTwoChildren() {
return left != null && right != null;
}
}
该节点类，提供了一个构造函数以及两个特有的方法，对于构造函数而言，初始化的时候，我们需要指定节点存储的元素以及父节点，为什么左右子节点不初始化呢，因为你添加一个节点时，是一定要知道其父节点的，但是你并不知道它有没有子节点。
对于另外两个方法，我觉的这是节点类所特有的行为，因为节点的概念在二叉树中是通用的，所以直接封装在节点类中，而不是在后面，对于每一种独特的二叉树，需要用到判断叶子节点以及度为 2 的节点的时候，再去编写，那样就太繁琐了
针对前面说到的size,root,以及节点类，这些应该是二叉树的内部逻辑，对外是不公开的，外界不知道节点类的，它只需要指定节点，也就是二叉树存储的类型就可以了，但是我们需要对外界开放接口，通过接口来使用二叉树，也就是说你只要知道怎么用就好了，不需要知道我是怎么实现的。
公共接口
对于二叉树，我们提供给外界的方法应该有以下方法：
public int size() —— 获取元素节点的数量
public boolean isEmpty() —— 判断树是否为空树
public void clear() —— 清空树的所有元素
public void preorder() —— 前序遍历
public void inorder() —— 中序遍历
public void postorder() —— 后序遍历
public void levelOrder() —— 层序遍历
public int height() —— 计算树的高度
public boolean isComplete() —— 判断是否为完全二叉树
public boolea **Java开源项目【ali1024.coding.net/public/P7/Java/git】** n isProper () —— 判断是否为真二叉树
public String toString() —— 重新toString方法，树状打印二叉树
我们对外界提供的方法大致就是这些了，那么问题来了，我们可以有疑惑了，既然二叉树是用来存放元素的，为什么没有add、remove添加以及移除节点的方法的呢，那么这样的一棵树new出来之后就是一棵空树呀，是不是忘记了？很明确说明，没有忘了，就是不给提供添加、移除的方法。
我们来思考一下，有下面这么一段代码：
BinaryTree bTree = new BinaryTree<>();
bTree.add(9);
bTree.add(5);
bTree.add(8);
可以明确的是第一个添加的元素9就是根节点，那么问题来了，接下来的 5，是要作为 9 的左子节点还是右子节点，8 应该是 5 的兄弟节点还是左右子节点其中一个，是的，我们并没有明确二叉树的添加规则，写起来是很麻烦也是没有意义的，当然，我们也可以默认一致往左或者往右添加，但是这样没有多大意义，没有明确的规则，那就是普通的二叉树，是没有什么用处的，规则就是树的特性，像二叉搜索树，红黑树，AV树等等，都是有明确的规则的。实际上，我们是在普通的二叉树加一些自定义的逻辑和规则，所以这里的二叉树类BinaryTree实际上应该是基类，而添加以及移除等特有的规则，应该在继承普通二叉树的基础上编写的，而二叉树提供的就是一些通用的方法。这也是前面将BinaryTree的类的属性的访问修饰符设计为protected的原因
简单方法public int size() —— 获取元素节点的数量
public int size() {
return size;
}
public boolean isEmpty() —— 判断树是否为空树
public boolean isEmpty() {
return size == 0;
}
public void clear() —— 清空树的所有元素
public void clear() {
root = null;
size = 0;
}
简单的方法直接放出来，直接瞄一眼即可
有趣的遍历对于数组，链表等数据结构，我们都能遍历，获取到所有元素，线性数据结构的遍历比较简单 — 正序遍历与逆序遍历，对于我们的二叉树，同样也应该提供遍历的方法
根据节点访问顺序的不同，二叉树的常见遍历方式有4种常见的遍历方式（Preorder Traversal）：
- 前序遍历（Preorder Traversal）
- 中序遍历（Inorder Traversal）
- 后序遍历（Postorder Traversal）
- 层序遍历（Level Order Traversal）
我们以二叉搜索树 —— {7,4,9,2,5,8,11,3,12,1}为例，分别分析这四种遍历方式
前序遍历访问顺序：根节点、前序遍历左子树、前序遍历右子树 — （根节点访问在前）
遍历结果是：7、4、2、1、3、5、9、8、11、10、12
前序遍历、中序遍历、后序遍历用递归遍历的方式实现都很简单，这里就不放出来占篇幅了，但是有提供，如果想看的话，后面会将完整代码上传Github,需要再去下载下来即可，下载的时候，注意选择dev分支，那边才是最新的代码
实现步骤：
- 利用栈先进后出的特性：
- 设置node = root，将root入栈，循环执行以下操作，直到栈为空
- 弹出栈顶节点top，进行访问
- 将top.right入栈将top.left入栈
private void preorderByIteration(){
if (root == null) return;
Stack
stack.push(root);
while (!stack.isEmpty()) {
Node node = 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入栈，循环执行以下操作，直到栈为空
- 如果node！= null将node入栈，设置node = node.left
- 如果node == null如果栈为空，结束遍历，如果栈不为空，弹出栈顶元素并赋值给node，对node进行访问
- 设置node = node.right
while (node != null || !stack.isEmpty()) { while (node != null){ 访问顺序：后序遍历左子树、后序遍历右子树、根节点 — （根节点访问在后） 遍历结果是：1、3、2、5、4、8、10、12、11、9、7 实现步骤： Node node = root; while (node != null){ node = stack.pop(); 访问顺序：从上到下、从左到右依次访问每一个节点 遍历结果是：7、4、9、2、5、8、11、1、3、10、12 层序遍历采用迭代的方式实现，利用队列的先进先出性质，能很好的做到层序遍历 实现步骤： 画一波图解： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xXmhNbgU-1650625437640)(https://upload-images.jianshu.io/upload_images/24195226-ef418c666e08b12a.image?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)] 结合图解，看代码，很清晰 Queue while (!queue.isEmpty()){ //如果有左子节点，入队 如果对于二叉树的四种遍历方式还是比较迷惑的话，我只是画了静态图的顺序，可能阅读起来理解不够到位，但是有时候画图解的时间很长，看一下图解，再回来阅读，相信会好一些 对比： 上面四种遍历的方法都编写出来了，但是你觉得这样的遍历，功能够吗？ 或者说，你觉得这个对比我们前面在动态数组，链表、栈和队列中的遍历有什么区别？没有阅读过动手编写 —— [动态数组](()，[链表](()，[栈和队列](()的同学，有兴趣的可以点击关键词看看 我们简单写一下JDK数组或者动态链表遍历的代码: //遍历数组 //遍历链表 这样看起来好像没有什么问题，二叉树遍历是System.out.print(node.element); 而数组和链表是System.out.println(value); 都是打印呀，能有什么区别呀。可能上面的代码具备迷惑性，我们再来看看另一个代码： int[] arr = {1,2,3,4,5,6,7,8,9}; 嗨，这样就醒目点了，数组可以打印出节点存储的元素的同时，补上一句Kalton是帅哥，而上面二叉树的遍历却是做不到的，因为一个是 《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》开源 写死在类里面的，一个是在类外部编写的。 这样的区别就是，二叉树的遍历只是打印一遍元素，并没有真正获取到存在在二叉树的元素，而数组、链表的遍历是获取到每一个元素，至于做什么，打印还是增加，还是说Kalton是帅哥，这些遍历规则都是由调用者自定义的，而不是写死了，所以我们的二叉树内部应该做到能够遍历的同时将节点元素传给调用者，由用户自定义遍历规则，我们的做法时，在二叉树编写一个抽象内部类Visitor： //遍历停止遍历的标记 /** Kafka高级篇知识点 44个Kafka知识点（基础+进阶+高级）解析如下 由于篇幅有限，小编已将上面介绍的**《Kafka源码解析与实战》、Kafka面试专题解析、复习学习必备44个Kafka知识点（基础+进阶+高级）都整理成册，全部都是PDF文档** tract static class Visitor{ //遍历停止遍历的标记 /** [外链图片转存中…(img-VM7mMzfa-1650625437641)] Kafka高级篇知识点 [外链图片转存中…(img-f2jFq8wv-1650625437642)] 44个Kafka知识点（基础+进阶+高级）解析如下 [外链图片转存中…(img-Lg4HYhJr-1650625437643)] 由于篇幅有限，小编已将上面介绍的**《Kafka源码解析与实战》、Kafka面试专题解析、复习学习必备44个Kafka知识点（基础+进阶+高级）都整理成册，全部都是PDF文档**
private void inorderByIteration(){
if (root == null) return;
Stack
Node node = root;
stack.push(node);
node = node.left;
}
node = stack.pop();
System.out.print(node.element + " ");
node = node.right;
}
}
private void postorderByIteration(){
if (root == null) return;
//记录上一次访问的节点
Node lastVisited = null;
Stack
while (node != null || !stack.isEmpty()) {
stack.push(node);
node = node.left;
}
//栈顶节点是叶子节点或者上一次访问的节点是栈顶节点的子节点
if (node.right == null || node.right == lastVisited){
System.out.print(node.element + " ");
lastVisited = node;
//这里node没有改变指向，所以需要指向null，否则会死循环
node = null;
}else {
//既不是子节点且上一次访问的节点又不是栈顶节点的子节点话，代表是符节点，重新进栈
stack.push(node);
node = node.right;
}
}
}
public void levelOrderTraversal(){
if (root == null) return;
//入队
queue.offer(root);
Node node = queue.poll();
System.out.print(node.element + " ");
if (node.left != null){
queue.offer(node.left);
}
//如果有右子节点，入队
if (node.right != null){
queue.offer(node.right);
}
}
}
int[] arr = {1,2,3,4,5,6,7,8,9};
for (int value:arr) {
System.out.println(value);
}
List list = new LinkedList<>(){{
add(1);add(2);add(3);add(4);add(5);
}};
for (int value:list) {
System.out.println(value);
}
for (int value:arr) {
System.out.println(value + “–>” + “Kalton是帅哥”);
}
public abstract static class Visitor{
boolean stop;
boolean stop;
