目录
1，二叉树的介绍
【数据结构|数据结构-二叉树（一 链式存储）（Java版）】1.1，树的定义
1.2，概念解释
2，二叉树
2.1，二叉树的特点
2.2，二叉树的性质
2.3，斜树
2.4，满二叉树
2.5，完全二叉树
3，二叉树的实现
3.1，二叉树的节点类型
3.2，二叉树遍历操作（递归实现）
3.2.1，前序遍历递归实现
3.2.2，中序遍历递归实现
3.2.3，后序遍历递归实现
3.3，二叉树的遍历操作（非递归实现）
3.3.1，前序遍历非递归实现
3.3.2，中序遍历非递归实现
3.3.3，后序遍历非递归实现
3.4，二叉树的层次遍历实现
3.5，二叉树的查找算法（递归实现）
3.5.1，前序查找递归实现
3.5.2，中序查找非递归实现
3.5.3，后续查找递归实现
3.6，二叉树中删除一个节点
3.7，定义一颗二叉树
4，测试代码
1，二叉树的介绍 在介绍二叉树的概念之前，我们先来看看什么是树。
1.1，树的定义 树（Tree）是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：

• 有且仅有一个特定的称为根（Root）的结点；
• 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

此外，对于树这种数据结构，我们还应该注意以下两点：

• n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。
• m>0时，子树的个数没有限制，但它们一定是互不相交的。

概念很抽象，下面看看树的结构：由树的定义可以看出，树的定义使用了递归的方式。递归在树的学习过程中起着重要作用

文章图片

1.2，概念解释 针对树的定义，现在我们来看一些关于树的概念。

• 节点的度：结点拥有的子树数目称为结点的度。看下面图片，每个节点拥有子节点的个数就是本节点度的大小。

文章图片

• 节点之间的关系
  

某一个节点的子节点称为该节点的孩子节点，相应的该节点就叫做双亲节点，同一个双亲结点的孩子结点之间互称兄弟结点。如上面的图中，A节点是B节点的父节点，那自然B节点就是A节点的孩子节点，B节点和C节点有相同的父节点A，那么B节点和C节点就是兄弟节点。

• 节点的层次

从根开始定义起，根为第一层，根的孩子为第二层，以此类推。下面展示树的层次关系。

文章图片

• 树的深度

树中结点的最大层次数称为树的深度或高度，上面图中的树的深度是4。
2，二叉树 了解了上面树的基本概念之后，下面我们来看看树的一种特殊情况，树中每一个节点的度最大是2的这种特殊的树，二叉树。二叉树的节点有左右之分。
2.1，二叉树的特点

• 由二叉树定义以及图示分析得出二叉树有以下特点：
  • 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
  • 左子树和右子树是有顺序的，次序不能任意颠倒。
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

2.2，二叉树的性质

• 在二叉树的第
  文章图片
  层上最多有
  文章图片
  个节点 。（i>=1）
• 二叉树中如果深度为k,那么最多有
  文章图片
  个节点(也就是二叉树是一棵完全二叉树的情况）。(k>=1）
• n0=n2+1， n0表示度数为0的节点数，n2表示度数为2的节点数。
• 在完全二叉树中，具有n个节点的完全二叉树的深度为[
  文章图片
  ]+1，其中[log2n]是向下取整。
• 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：
  • 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
  • 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
  • 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

2.3，斜树 所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

文章图片

2.4，满二叉树 满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

• 满二叉树的特点有：
  • 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
  • 非叶子结点的度一定是2。
  • 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

文章图片

2.5，完全二叉树 完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。


文章图片

• 特点：
  • 叶子结点只能出现在最下层和次下层。
  • 最下层的叶子结点集中在树的左部。
  • 倒数第二层若存在叶子结点，一定在右部连续位置。
  • 如果结点度为1，则该结点只有左孩子，即没有右子树。
  • 同样结点数目的二叉树，完全二叉树深度最小。
  • 注：满二叉树一定是完全二叉树，但反过来不一定成立。

3，二叉树的实现 通过上面的讲解，大致了解什么是二叉树，下面通过代码实现一个二叉树。
3.1，二叉树的节点类型

class TreeNode{ private int data; private TreeNode left; private TreeNode right; public TreeNode(int data) { this.data = https://www.it610.com/article/data; }public int getData() { return data; }public TreeNode getLeft() { return left; }public TreeNode getRight() { return right; }public void setLeft(TreeNode left) { this.left = left; }public void setRight(TreeNode right) { this.right = right; }@Override public String toString() { return"TreeNode{" + "data="https://www.it610.com/article/+ data +'}'; } }

3.2，二叉树遍历操作（递归实现） 3.2.1，前序遍历递归实现
前序遍历: 先输出父节点，再遍历左子树和右子树，在递归遍历左子树和右子树的时候需要判断节点是否是空，否则会报空指针异常。

/** * 二叉树的前序遍历递归实现 */ public void preOrder(){ //前序遍历，先输出节点值，在递归左右子树 System.out.println(this.getData()); //判断左边节点是否是空，如果不空就递归遍历 if(this.left != null){ this.left.preOrder(); } //判断右孩子是否是空 if(this.right != null){ this.right.preOrder(); } }

3.2.2，中序遍历递归实现
中遍历：先遍历左子树，再输出父节点，再遍历右子树。（同样需要判断左右孩子是否是空，否则发生空指针异常）

/** * 二叉树中序遍历递归实现 */ public void midOrder(){ //判断左边节点是否是空，如果不空就递归遍历 if(this.left != null){ this.left.midOrder(); } System.out.println(this.getData()); if(this.right != null){ this.right.midOrder(); } }

3.2.3，后序遍历递归实现
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点。

/** * 后序遍历递归实现 */ public void postOrder(){//判断左边节点是否是空，如果不空就递归遍历 if(this.left != null){ this.left.postOrder(); } if(this.right != null){ this.right.postOrder(); } System.out.println(this.getData()); }

小结：递归的实现，主要看输出父节点的顺序，在递归的过程中，每一个节点都有三次机会被访问到，第一次访问到并且直接输出，那就是前序遍历，第二次访问到输出的话就是中序遍历，第三次访问到并且输出的话就是后续遍历。
3.3，二叉树的遍历操作（非递归实现） 二叉树的非递归遍历实现需要借助一个栈来实现。
3.3.1，前序遍历非递归实现

• 二叉树前序非递归遍历实现过程
  • 如果二叉树非空，先把根节点入栈，如果是空直接返回。
  • 如果栈不空，先抛出栈顶元素，并且访问栈顶的元素。
  • 如果当前栈顶元素的左右子树都不空，那么先把右子树压入栈，在把左子树压入栈。注意：应为栈是先进后出的原则，所以在这里要先把右子树入栈，然后左子树在入栈。
  • 循环抛出栈顶元素，直到栈为空为止。
• 代码实现

public void preOrderNonRec(){ if(this.root == null) return ; //也就是二叉树不空 Stack stack=new Stack(); //先把根节点入栈 stack.push(this.root); while (!stack.isEmpty()){ //如果栈不空，就一直循环 TreeNode treeNode=(TreeNode)stack.pop(); System.out.println(treeNode.getData()); //如果当前节点的左右节点都不空，那么全部入栈，因为栈是先进后出原则 //所以前续遍历的时候，先入右子树，在入左子树 if(treeNode.getRight()!= null){ stack.push(treeNode.getRight()); } if(treeNode.getLeft() != null){ stack.push(treeNode.getLeft()); }} }

3.3.2，中序遍历非递归实现

• 二叉树中序遍历非递归过程：
  • 如果二叉树左子树非空，循环遍历左子树直到空为止。
    
  • 抛出栈顶元素并且访问栈顶元素。
    
  • 如果当前节点右子树非空，那么右子树入栈。
    
  • 循环访问直到栈空为止。
    
• 代码实现：
  

public void midOrderNonRec(){ if(this.root == null) return; Stackstack=new Stack(); TreeNode treeNode=this.root; //先一直走到最左边的节点 stack.push(this.root); while (!stack.isEmpty()){ while (treeNode.getLeft() != null){ stack.push(treeNode.getLeft()); treeNode=treeNode.getLeft(); } //退出循环，说明已经走到最左边的节点。抛出节点开始打印 treeNode=stack.pop(); System.out.println(treeNode.getData()); if(treeNode.getRight() != null){ stack.push(treeNode.getRight()); treeNode=treeNode.getRight(); }} }

3.3.3，后序遍历非递归实现
二叉树后续非递归遍历过程：对二叉树后续的非递归遍历，可以观察到和先续遍历相反，所以仿照先续遍历，先访问左子树，在访问右子树，把访问到的元素全部入栈，最后抛出栈即可。

• 二叉树后序非递归遍历 过程
  • 如果二叉树非空，先把根节点入栈。
    
  • 如果栈不空，先抛出栈顶元素，并且把元素入栈。
    
  • 如果当前栈顶元素的左右子树都部空，那么先把左子树压入栈，在把右子树压入栈。
    
  • 循环抛出栈顶元素，直到栈为空为止。
    

//后续非递归遍历 public void postOrderNonRec(){ if(this.root == null) return ; //也就是二叉树不空 Stack stack=new Stack(); Stack stack1=new Stack(); //先把根节点入栈 stack.push(this.root); while (!stack.isEmpty()){ //如果栈不空，就一直循环 TreeNode treeNode=(TreeNode)stack.pop(); stack1.push(treeNode.getData()); //如果当前节点的左右节点都不空，那么全部入栈，因为栈是先进后出原则 //所以中续遍历的时候，先入左子树，在入右子树 if(treeNode.getLeft()!= null){ stack.push(treeNode.getLeft()); } if(treeNode.getRight() != null){ stack.push(treeNode.getRight()); } } while (!stack1.isEmpty()){ System.out.println(stack1.pop()); } }

3.4，二叉树的层次遍历实现 二叉树的层次遍历需要借助队列来实现

//二叉树的层次遍历 public void levelOrder(){ TreeNode treeNode=this.root; Queue queue=new LinkedList(); queue.add(this.root); while (!queue.isEmpty()){ TreeNode treeNode1=queue.remove(); System.out.print(treeNode1.getData()+" "); if(treeNode1.getLeft() != null){ queue.add(treeNode1.getLeft()); } if(treeNode1.getRight()!= null){ queue.add(treeNode1.getRight()); } } }

3.5，二叉树的查找算法（递归实现） 3.5.1，前序查找递归实现

• 前序查找思路
  • 首先判断当前节点是否是要查找的节点。
  • 如果是当前查找的节点，就直接返回当前节点。
  • 如果不是当前查找的节点，就判断当前节点的左子树是否是空，如果不空，则递归前序查找左子树。
  • 如果左递归前序查找，找到该节点，就返回，否则继续判断当前节点的右子节点是否是空，如果不空，则继续向右递归查找。
• 代码实现：

/** * 前序遍历查找算法 * @param value 待查找的值 * @return 查找成功就返回，否则就返回null */ public TreeNode preOrderSearch(int value){ //首先判断当前节点值是否等于value if(this.getData() == value){ return this; } //递归遍历左子树 TreeNode treeNode=null; if(this.left !=null){ treeNode=this.left.preOrderSearch(value); } if(treeNode != null){ return treeNode; } //左子树没有找到就递归遍历右子树 if(this.right != null){ treeNode=this.right.preOrderSearch(value); } return treeNode; }

3.5.2，中序查找非递归实现

• 查找思路
  • 判断当前节点的左节点是否是空，如果不为空，就递归查找左子树。
  • 如果在左子树中找到，就返回，如果没有找到，就和当前节点进行比较，如果是就返回当前节点，否则就继续向右进行递归查找。
  • 如果右递归查找到，就返回，否则返回null。
• 代码实现：

/** * 中序查找算法 * @param value 待查找的值 * @return 查找成功返回节点，否则返回null */ public TreeNode midOrderSearch(int value){ //首先向左递归查找 TreeNode treeNode=null; if(this.left != null){ treeNode=this.left.midOrderSearch(value); } //如果查找到就返回 if(treeNode != null){ return treeNode; } //如果左子树中没有找到，就比价当前节点 if(this.getData() == value){ return this; } //递归在右子树上面查找 if(this.right != null){ treeNode=this.right.midOrderSearch(value); } return treeNode; }

3.5.3，后续查找递归实现

• 查找思路：
  • 判断当前节点的左子节点是否是空，如果不为空，则递归后续查找。
  • 如果找到，就返回节点，如果没有找到，就判断当前节点的右节点是否是空，如果不为空，则右递归进行后续查找，如果找到就返回。
  • 如果左子树和右子树都没有找到，就和当前节点进行比较，如果是查找到的元素就返回，不是就返回null。
• 代码实现：

/** * 后续查找算法 * @param value 待查找的值 * @return 查找成功返回节点，否则返回Null */ public TreeNode postOrderSearch(int value){ TreeNode treeNode=null; //递归在左子树上面查找 if(this.left != null){ treeNode=this.left.postOrderSearch(value); } //如果在左子树上面查找到就返回节点 if(treeNode != null){ return treeNode; } //递归在右子树上面查找 if(this.right != null){ treeNode=this.right.postOrderSearch(value); } //如果在右子树上面查找到，就直接返回 if(treeNode != null){ return treeNode; } //如果在左右子树上都没有查找到，就判断当前节点值 if(this.getData() == value) return this; return treeNode; }

3.6，二叉树中删除一个节点

• 删除条件：
  • 如果删除的是叶子节点，就直接进行删除。
  • 如果删除的是非叶子节点，就直接删除其子树，因为如果删除的是非叶子节点，需要涉及节点的调整问题，所以在这里就直接删除子树，在后面的avl树或者排序树会做具体非叶子节点的删除和调整。
• 代码实现：

/** * 递归删除二叉树中的节点 * @param value 需要删除的节点的值 * @return 删除成功返回1，否则返回-1 */ public int deleteNodeInBt(int value){ if(this.root != null){ //首先判断根节点是否是要删除的节点 if(this.root.getData() == value){ this.root = null; return 1; }else { //也就是根节点不是要删除的节点 return this.root.deleteNode(value); }}else { System.out.println("二叉树是空，不可删除！"); return -1; } }

3.7，定义一颗二叉树 注意，上面的代码是二叉树的节点类型，删除，插入，遍历的具体实现在节点类型的类中实现。下面这段代码才是二叉树的实现。

//定义一颗二叉树 class BinaryTree{ //二叉树的跟节点 private TreeNode root; public void setRoot(TreeNode root) { this.root = root; } //前序遍历 public void preOrder(){ if(this.root!=null){ this.root.preOrder(); }else { System.out.println("当前二叉树欸你空"); } } //中序遍历 public void midOrder(){ if(this.root != null){ this.root.midOrder(); }else { System.out.println("当前二叉树为空"); } } //后序遍历 public void postOrder(){ if(this.root != null){ this.root.postOrder(); }else { System.out.println("当前二叉树为空"); } } /** * 前序遍历查找算法 * @param value 待查找的值 * @return 查找成功返回该节点，否则返回null */ public TreeNode preOrderSear(int value){ //判断当前树是否是空，空就直接返回 if(this.root != null){ return this.root.preOrderSearch(value); }else { return null; } } public TreeNode midOrderSear(int value){ if(this.root != null){ return this.root.midOrderSearch(value); }else { return null; } } public TreeNode postOrderSear(int value){ if(this.root != null){ return this.root.postOrderSearch(value); }else { return null; } }/** * 递归删除二叉树中的节点 * @param value 需要删除的节点的值 * @return 删除成功返回1，否则返回-1 */ public int deleteNodeInBt(int value){ if(this.root != null){ //首先判断根节点是否是要删除的节点 if(this.root.getData() == value){ this.root = null; return 1; }else { //也就是根节点不是要删除的节点 return this.root.deleteNode(value); }}else { System.out.println("二叉树是空，不可删除！"); return -1; } } }

4，测试代码

public class BinaryTreeDemo { public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); TreeNode root=new TreeNode(1); TreeNode node2=new TreeNode(2); TreeNode node3=new TreeNode(3); TreeNode node4=new TreeNode(4); TreeNode node5=new TreeNode(5); TreeNode node6=new TreeNode(6); TreeNode node7=new TreeNode(7); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); node3.setRight(node7); binaryTree.setRoot(root); //前序遍历 //binaryTree.preOrder(); // binaryTree.preOrderNonRec(); //binaryTree.midOrderNonRec(); //binaryTree.postOrderNonRec(); //二叉树的层次遍历 // binaryTree.levelOrder(); //HashMap hashMap=new HashMap(); //二叉树的前序查找算法 //TreeNode treeNode= binaryTree.preOrderSear(6); //TreeNode treeNode1=binaryTree.midOrderSear(6); //TreeNode treeNode2=binaryTree.postOrderSear(77); //System.out.println(treeNode2); binaryTree.deleteNodeInBt(6); binaryTree.preOrder(); } }

推荐阅读

• 

  自汗是什么意思 自汗解释
• 

  怎样熬排骨汤又白又浓
• 

  驾驶证年审手续流程是什么
• 

  高手在民间！！！
• 

  华为P40是几W快充（华为P40的快充是多少）
• 

  早起打卡第62天，早饭打卡第8天
• 

  生菜对环境条件的要求 生菜适合的温度和环境
• 

  经常吃猪肝对身体好吗 经常吃猪肝好不好
• 

  cf手游像我这个比较穷的V5买啥好？
• 

  弹弹堂安卓苹果互通吗,弹弹幽灵大冒险:苹果和安卓不完全互通
• 

  除了《恶作剧之吻》,你还记得哪些小时候看的青春偶像剧？
• 

  苦练郭林气功复发 郭林新气功
• 

  爱普生l360打印机废墨收集垫6
• 

  想问一下在京东买手机靠谱吗？
• 

  美股基金有哪些
• 

  redis槽满了会怎么样 redis的插槽不均匀
• 

  银河破裂者最高难度战役模式怎么玩 战役模式通关方法推荐
• 

  vue+echarts实带渐变效果的折线图
• 

  什么是不成对电子数
• 

  为什么热水器只能75度，怎么修复与排查方法？

• 算法计算经典|二叉树知识点最详细最全讲解
• Quicksort最坏的情况何时发生（）
• 堆排序实际上在哪里使用（）
• 哪一种排序算法的内存写操作最少（）
• 用大于或等于m的数求和n的不同方法
• 矩阵的不同运算快速介绍
• 用C++ STL复制的不同方法std::copy()、copy_n()、copy_if()、copy_backward()
• Java中的TreeMap、HashMap和LinkedHashMap之间的区别
• #yyds干货盘点# 数据结构与算法学习——单链表相关算法