当前位置：首页 > news >正文

二叉树-------前,中,后序遍历 + 前，中，后序查找+删除节点（java详解）

news 来源：原创 2024/5/9 19:23:46

提要：

创建一个简单的二叉树：

二叉树的前中后序遍历：

二叉树的前序遍历：

二叉树的中序遍历：

二叉树的后续遍历：

小结：

二叉树的前中后续查找：

二叉树的前序查找：

二叉树的中序查找：

二叉树的后续查找:

代码实现：

二叉树节点删除操作：

思路与约定：

代码实现：

最后，完整代码：

提要：

二叉树的遍历是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅能访问一次（说明不可二次访问，一遍而过）。遍历一颗二叉树便要决定对根结点N、左子树L和右子树的访问顺序。二叉树常的的遍历方法有前序遍历（NLR）、中序遍历（LNR）和后序遍历（LRN）三种遍历算法，其中 “序” 指的是根结点在何时被访问。

遍历大致过程：

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

--------------------------------------------------------------------------------------------------------------------------------

创建一个简单的二叉树：

二叉树的存储结构分为：顺序存储和类似于链表的链式存储，这里我们学习链式存储的方式，简单枚举一棵二叉树。

用孩子表示法创建一颗二叉树：

//孩子表示法
class KunBinaryTree{//数据域public int no;//序号public String name;//姓名public KunBinaryTree left;//左孩子的引用，常常代表左孩子为根的整棵左子树public KunBinaryTree right;//右孩子的引用，常常代表右孩子为根的整棵右子树//构造方法public KunBinaryTree(int no,String name){super();this.no = no;this.name = name;}
}
public class TestBinaryTree {public static void main(String[] args){//对象实例化KunBinaryTree root = new KunBinaryTree(1,"唱");KunBinaryTree node1 = new KunBinaryTree(2,"跳");KunBinaryTree node2 = new KunBinaryTree(3,"rap");KunBinaryTree node3 = new KunBinaryTree(4,"篮球");KunBinaryTree node4 = new KunBinaryTree(5,"music");KunBinaryTree node5 = new KunBinaryTree(6,"坤坤");//链接各个节点，使其构成一颗二叉树root.left = node1;root.right = node2;node2.left = node3;node2.right = node4;node4.left = node5;}
}

创建了一颗如图所示的二叉树（一共有6个节点，其中root节点为 “唱”）：

--------------------------------------------------------------------------------------------------------------------------------

二叉树的前中后序遍历：

通过上面的简单介绍，我们可以开始正式学习接下来的操作了

二叉树的前序遍历：

基本思路：

若二叉树为空，什么都不做，否则：

i、先访问根结点；

ii、再前序遍历左子树；

iii、最后前序遍历右子树；

代码实现：

//前序遍历public static void preOrder(KunBinaryTree root){if(root == null){return ;}System.out.print(root.no+" "+root.name+" ");//先访问根preOrder(root.left);//接着左右子树preOrder(root.right);}

函数递归展开图解：

首先，我们从蓝色出发，也就是途中的①，按照先根节点后左右子树的过程进行依次遍历，这里相当于先打印根节点所对应的数据域中的信息后，在接着递归调用左子树，直到为空，回溯后递归调用右子树，直到为空。该树的左子树（总的）调用完后，开始调用右子树，来到②过程，按照（根-----》左子树---》右子树）的规则继续递归。直到左右子树都为空，返回，也就是③，④过程。从途中可以看出，打印的顺序为：1 唱 2 跳 3 rap 4 篮球 5 music 6 坤坤

通过遍历的测试结果也显示，上述过程正确：

或则用更明了直观的动图解释（图中栗子不为上述栗子，仅做参考，便于理解）：

二叉树的中序遍历：

基本思路：

二叉树为空，什么也不做，否则：

i、中序遍历左子树；

ii、访问根结点；

iii、中序遍历右子树

代码实现：

 //中序遍历public static void infixOrder(KunBinaryTree root){if(root == null){return ;}infixOrder(root.left);System.out.print(root.no +" "+root.name+" ");infixOrder(root.right);}

函数递归展开图：

首先，我们先从红色出发，也就是①，按照(左子树---》根---》右子树)的规则依次遍历，这里相当于从不可在分割的左子树开始从后往前进行打印输出对应信息，与前序遍历基本一致，就是中间根节点的位置变化导致输出顺序的不同。

最终递归结果为(打印顺序为)：2 跳 1 唱 4 篮球 3 rap 6 坤坤 5 music

通过测试也可已看出确实是这样:

用更直观的动图展示（栗子与上述不同，主要是便于理解其过程）：

二叉树的后续遍历：

基本思路：

若二叉树为空，什么也不做，否则：

i、后序遍历左子树

ii、后序遍历右子树

iii、访问根结点

代码实现：

 //后续遍历public static void postOrder(KunBinaryTree root){if(root == null){return ;}postOrder(root.left);postOrder(root.right);System.out.print(root.no +" "+root.name+" ");}

函数递归展开图：

首先从①开始，按照（左子树---》右子树---》根）的规则依次遍历，过程与上述类似，不在赘述。递归结果为:2 跳 4 篮球 6 坤坤 5 music 3 rap 1 唱

测试结果也表明上述结果正确：

用更直观的动图演示该过程（栗子与上述不同，主要是便于理解其过程）：

小结：

比较各个遍历的过程

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

我们不难发现，前序遍历的root节点（栗子中也就是"1.唱"）一定在遍历结果的首部，二中序遍历的root节点在整个树的中部，在遍历的结果中随树的变化二变化，后续遍历的root节点一定在尾部，利用这个特性，我们可以只知道（前序+中序）或者（后续+中序）或则（前序+后续）的遍历结果还原出该二叉树。

二叉树的前中后续查找：

有了前中后续遍历的实现，我们接着就能实现查找过程，这是基于遍历来实现的

二叉树的前序查找：

基本思路：

1.先判断当前节点的no(序号)是否等于要查找的

2.如果是相等的，则返回当前节点

3.如果不等，则判断当前节点的左右子节点是否为空，如果不为空，则递归前序查找

4.如果左递归前序查找找到节点，则返回，否则继续判断当前节点的左右子节点是否为空，如果不为空，则继续右递归前序查找

代码实现：

//前序查找public static int count1 = 0;//用于记录递归查找的次数public static KunBinaryTree preOrderSearch(KunBinaryTree root,int no){++count1;if(root.no == no){return root;}KunBinaryTree resNode = null;if(root.left != null){resNode = preOrderSearch(root.left,no);}if(resNode != null){return resNode;}if(root.right != null){resNode = preOrderSearch(root.right,no);}return resNode;}

按照上述的遍历结果我们可以知道，一共进行了6次遍历，（咱们这里查找数字6）那么前序查找遍历的次数为6（即count1=6）：

测试结果：

二叉树的中序查找：

基本思路：

1.判断当前节点的左右子节点是否为空，如果不为空，则递归中序查找

2.如果找到，则返回，若果没有找到，就和当前节点比较，如果是则返回当前节点，否则继续进行右递归的中序查找

3.右递归中序查找，找到就返回，否则返回null

代码实现：

//中序查找public static int count2 = 0;//记录中序查找次数public static KunBinaryTree infixOrderSearch(KunBinaryTree root,int no){KunBinaryTree resNode = null;if(root.left != null){resNode = infixOrderSearch(root.left,no);}if(resNode != null){return resNode;}++count2;if(root.no == no){return root;}if(root.right != null){resNode = infixOrderSearch(root.right,no);}return resNode;}

按照上述的遍历结果我们可以知道，一共进行了6次遍历，（咱们这里查找数字6）那么中序查找的遍历次数为5（count2=5）:

测试结果：

二叉树的后续查找:

基本思路：

1.判断当前节点的左子节点是否为空，如果不为空，则递归后序查找

2.如果找到，就返回，如果没有找到，就判断当前节点的有子节点是否为空，如果不为空，则右递归进行后序查找，如果找到，就返回

3.接着和当前节点进行比较，找到则返回，否则返回null

代码实现：

   //后序查找public static int count3 = 0;//记录后序查找遍历次数public static KunBinaryTree postOrderSearch(KunBinaryTree root,int no){KunBinaryTree resNode = null;if(root.left != null){resNode = postOrderSearch(root.left,no);}if(resNode != null){return resNode;}if(root.right != null){resNode = postOrderSearch(root.right,no);}if(resNode != null){return resNode;}++count3;if(root.no == no){return root;}return resNode;}

按照上述的遍历结果我们可以知道，一共进行了6次遍历，（咱们这里查找数字6）那么后序查找的次数为3（count3=3）:

测试结果：

二叉树节点删除操作：

最后，咱么来进行二叉树节点删除的操作

思路与约定：

代码实现：

 //删除节点public static void delTreeNode(KunBinaryTree root,int no){if(root.no == no){root = null;}else{if(root.left != null && root.left.no == no){root.left = null;return ;}if(root.right != null && root.right.no == no){root.right = null;return ;}if(root.left != null){delTreeNode(root.left,no);}if(root.right != null){delTreeNode(root.right,no);}}}

这里我们删除4子节点，也就是篮球

测试结果：

当我们删除3这个子节点时，后面的节点也一并删除了：

最后，完整代码：

import java.util.*;class KunBinaryTree{public int no;public String name;public KunBinaryTree left;public KunBinaryTree right;public KunBinaryTree(int no,String name){super();this.no = no;this.name = name;}
}public class BinaryTree {
//前中后序遍历//前序遍历public static void preOrder(KunBinaryTree root){if(root == null){return ;}System.out.print(root.no+" "+root.name+" ");preOrder(root.left);preOrder(root.right);}//中序遍历public static void infixOrder(KunBinaryTree root){if(root == null){return ;}infixOrder(root.left);System.out.print(root.no +" "+root.name+" ");infixOrder(root.right);}//后续遍历public static void postOrder(KunBinaryTree root){if(root == null){return ;}postOrder(root.left);postOrder(root.right);System.out.print(root.no +" "+root.name+" ");}
//前中后序查找//前序查找public static int count1 = 0;//用于记录递归查找的次数public static KunBinaryTree preOrderSearch(KunBinaryTree root,int no){++count1;if(root.no == no){return root;}KunBinaryTree resNode = null;if(root.left != null){resNode = preOrderSearch(root.left,no);}if(resNode != null){return resNode;}if(root.right != null){resNode = preOrderSearch(root.right,no);}return resNode;}//中序查找public static int count2 = 0;//记录中序查找次数public static KunBinaryTree infixOrderSearch(KunBinaryTree root,int no){KunBinaryTree resNode = null;if(root.left != null){resNode = infixOrderSearch(root.left,no);}if(resNode != null){return resNode;}++count2;if(root.no == no){return root;}if(root.right != null){resNode = infixOrderSearch(root.right,no);}return resNode;}//后序查找public static int count3 = 0;//记录后序查找遍历次数public static KunBinaryTree postOrderSearch(KunBinaryTree root,int no){KunBinaryTree resNode = null;if(root.left != null){resNode = postOrderSearch(root.left,no);}if(resNode != null){return resNode;}if(root.right != null){resNode = postOrderSearch(root.right,no);}if(resNode != null){return resNode;}++count3;if(root.no == no){return root;}return resNode;}//删除节点public static void delTreeNode(KunBinaryTree root,int no){if(root.no == no){root = null;}else{if(root.left != null && root.left.no == no){root.left = null;return ;}if(root.right != null && root.right.no == no){root.right = null;return ;}if(root.left != null){delTreeNode(root.left,no);}if(root.right != null){delTreeNode(root.right,no);}}}//测试public static void main(String[] args){Scanner sc = new Scanner(System.in);KunBinaryTree root = new KunBinaryTree(1,"唱");KunBinaryTree node1 = new KunBinaryTree(2,"跳");KunBinaryTree node2 = new KunBinaryTree(3,"rap");KunBinaryTree node3 = new KunBinaryTree(4,"篮球");KunBinaryTree node4 = new KunBinaryTree(5,"music");KunBinaryTree node5 = new KunBinaryTree(6,"坤坤");root.left = node1;root.right = node2;node2.left = node3;node2.right = node4;node4.left = node5;preOrder(root);System.out.println();infixOrder(root);System.out.println();postOrder(root);System.out.println();System.out.print("请输入要查找的数字：");int n = sc.nextInt();KunBinaryTree resNode = postOrderSearch(root,n);System.out.println("一共查找的次数count3："+count3);if(resNode != null){System.out.printf("找到了,Kun节点 no=%d name=%s",resNode.no,resNode.name);}else{System.out.printf("没有找到Kun节点%d的信息",n);}System.out.println();System.out.print("请输入要删除的子节点：");int n2 = sc.nextInt();System.out.println("删除前：");preOrder(root);System.out.println();System.out.println("删除后：");delTreeNode(root,n2);preOrder(root);}
}

博客到这里也是结束了，制作不易，喜欢的小伙伴可以点赞加关注支持下博主，这对我真的很重要~~