汉阳网站建设哪家便宜,如何做家政网站,一个做礼品的网站,爱淘宝淘宝网首页目录
1、遍历方式
2、前序遍历
3、中序遍历 1、遍历方式
学习二叉树的结构#xff0c;最简单的方式就是遍历二叉树。遍历二叉树就是通过某条线路对二叉树的各个结点进行一次访问#xff0c;访问的方法有三种分为前序遍历、中序遍历、后续遍历#xff0c;层序遍历它们的遍…
目录
1、遍历方式
2、前序遍历
3、中序遍历 1、遍历方式
学习二叉树的结构最简单的方式就是遍历二叉树。遍历二叉树就是通过某条线路对二叉树的各个结点进行一次访问访问的方法有三种分为前序遍历、中序遍历、后续遍历层序遍历它们的遍历顺序如下所示
前序遍历:根节点》根节点的左子树》根节点的右子树中序遍历:根节点的左节点》根节点》根节点的右子树后续遍历:根节点的左节点》根节点的右节点》根节点
在二叉树的遍历中遍历的开始是从头节点开始的遍历的结束也是从头节点结束的。 有一个二叉树它有六个节点ABCDEF其值为123456。对应的结构为
A为根节点时A的左子树是DA的右子树是EA的值为1。B为根节点时B的左子树是DB的右子树是EB的值为2。C为根节点时C的左子树是nullC的右子树是FC的值为3。D为根节点时D的左子树是nullF的右子树是null的值为4。E为根节点时E的左子树是nullF的右子树是null的值为5。F为根节点时F的左子树是nullF的右子树是null的值为6。 本期博文所演练的遍历方式均以上图中的二叉树进行展示。 2、前序遍历
前序遍历我们在上方已经了解到了它的遍历顺序为根节点》根节点的左子树》根节点的右子树。因此前序遍历上述的定义好的二叉树的顺序应为ABDECF得到的值也应该为124536。具体实现方式看下方讲解
第一步获取根节点A。判断A节点是否有左子树。有则往下一个左子树遍历。没有则遍历右子树右子树也没有则返回父节点。如果无父节点则程序结束
此步骤往A的左子树进行遍历首先获取A节点发现A存在左子树则往下遍历A的左子树节点。此时遍历到节点为:A、元素为:1。 第二步来到B节点获取B节点。判断B节点是否有左子树。有则往下一个左子树遍历。没有则遍历右子树右子树也没有则返回父节点。如果无父节点则程序结束
此步骤往B的左子树进行遍历发现B存在左子树则往下遍历B的左子树节点。此时遍历到的节点为AB、元素为:12。 第三步来到D节点获取D节点。然后判断D节点是否有左子树有则往下一个节点遍历。没有则遍历右子树右子树也没有则返回父节点。
此时发现D没有左子树遍历D的右子树发现右子树也没有返回到B节点并且往B节点的右子树进行遍历。 此时遍历到的节点为:ABD、元素为:124。 第四步来到E节点获取E节点。判断E是否有左子树。有则往下一个节点遍历。没有则遍历右子树右子树也没有则返回父节点。
此时发现E节点没有左右子树则返回到B节点B节点再返回到A节点A节点再遍历到C节点此时遍历到的节点为:ABDE、元素为:1245。 第五步来到C节点获取C节点。判断C是否有左子树。有则往下一个节点遍历。没有则遍历右子树右子树也没有则返回父节点。
此时发现C节点没有左子树则访问C节点右子树F节点获取F节点的根节点。往F的左子树进行遍历此时获取到的节点为:ABDEC元素为:12453。 最后一步来到F节点获取F节点。F节点没有左右子树返回F节点的父节点C节点C节点再返回到C的父节点A节点。最后发现A没有父节点程序结束。此时获取到的节点为:ABDECF元素为:124536。 以上就是对前序遍历步骤的一个详细讲解下面我们来看代码的实现
//MyBinaryTree.java文件下
public class MyBinaryTree {//静态内部类BinaryTreestatic class BinaryTree {public int val;public BinaryTree left;public BinaryTree right;public BinaryTree(int val) {this.val val;}}//根节点public BinaryTree root;//创建一个二叉树public void initBinaryTree() {BinaryTree A new BinaryTree(1);BinaryTree B new BinaryTree(2);BinaryTree C new BinaryTree(3);BinaryTree D new BinaryTree(4);BinaryTree E new BinaryTree(5);BinaryTree F new BinaryTree(6);A.left B;A.right C;B.left D;B.right E;C.right F;root A;}//前序遍历二叉树public void preOrder(BinaryTree tree) {if( tree null) {return;}//节点的元素System.out.print(tree.val );//节点的左子树preOrder(tree.left);//节点的右子树preOrder(tree.right);}
}//Test.java文件下
public class Test {public static void main(String[] args) {MyBinaryTree myBinaryTree new MyBinaryTree();myBinaryTree.initBinaryTree();myBinaryTree.preOrder(myBinaryTree.root);}
}运行后输出 我们可以运行后的结果与上述演练的最终结果是一致的。通过程序我们也不难看出二叉树的遍历是一种递归思想它的终止条件就是节点本身不为空。另外细心的朋友可以发现前序遍历得到的首结果就是这个二叉树的头节点因为头节点是第一个被遍历的。 3、中序遍历
中序遍历的顺序为根节点的左节点》根节点》根节点的右节点。因此中序遍历本期二叉树得到的根节点顺序为DBEACF、根节点元素为425136。
第一步遍历A的左节点。如果A节点有左节点往A的左节点遍历不存在则获取A节点并往A节点的右节点遍历如果右节点也为空则返回父节点。此时遍历到了B节点。以下的每个节点也是同此步骤进行的。 第二步遍历来到B节点。判断B节点的左节点不为空。遍历来到D节点判断D节点的左子树为空获取D节点访问D的右子树为空返回父节点B获取B节点的根节点。此时遍历到的节点为DB元素为42。 第三步遍历来到E节点。E节点的左子树为空获取E节点右子树也是空返回父节点BB节点返回父节点A获取A节点的根节点。此时遍历到的节点为DBEA元素为4251。 第四步遍历来到C节点。C节点的左子树为空获取C节点判断C节点的右子树不为空。遍历到F节点此时遍历到的节点为DBEAC元素为42513。 第五步遍历来到F节点。F节点的左子树为空获取F节点F节点的右子树也为空返回父节点CC节点返回父节点AA节点没有父节点程序结束。此时遍历到的节点为DBEACF元素为425136。程序结束。 中序遍历我们只需将上述代码中的preOrder方法中的访问节点的根节点位置稍微改动一下其余代码不变。 //中序遍历二叉树
public void inOrder(BinaryTree tree) {if( tree null) {return;}//节点的左子树preOrder(tree.left);//节点的元素System.out.print(tree.val );//节点的右子树preOrder(tree.right);} 运行后输出: 通过上述结果我们可以看到输出的结果与上方展示的结果是一致。细心的朋友可以发现当我们中序遍历后头节点的左侧都是左子树头节点的右侧都是右子树。在上方代码中1的左侧为4251的右侧为36正好与我们的二叉树一致。因此当我们知道了一个二叉树的头节点是谁后可以通过中序遍历推出这个二叉树的左、右则的树。 4、后序遍历
后序遍历的步骤为根节点的左节点》根节点的右节点》根节点在本篇示例二叉树中对应的遍历节点顺序为DEBFCA节点元素为452631。
在上文中前序遍历与后序遍历我给大家展示了流程图以及实现步骤其实后序遍历也是一样的按照左节点、右节点、根节点的遍历顺序去遍历在此博主就不多讲解了大家可以自己尝试去画图。
后序遍历二叉树的代码我们也是将preOrder方法中的根节点位置互换一下即可
//后序遍历二叉树
public void postOrder(BinaryTree tree) {if( tree null) {return;}//节点的左子树preOrder(tree.left);//节点的右子树preOrder(tree.right);//节点的元素System.out.print(tree.val );}
运行后输出
通过运行结果可以看到与上方遍历得到的结果是一致的。通过观察我们也可以知道。知道了一个二叉树的后序遍历就能得到头节点因为后序遍历的最后一个数据就是我们的头节点。 当我们知道一个二叉树的前序遍历或后续遍历结果与中序遍历结果时就能轻易的推出这个二叉树的全貌。
如一个二叉树的前序遍历结果为ABDECF中序遍历结果为DBEACF。则这个二叉树的头节点为A左侧子树为DBE、右侧子树为CF。因此可以推出这个二叉树的全貌为 当然知道一个二叉树的中序遍历与后序遍历也能很轻松的推出这个二叉树但知道前序遍历和后序遍历却不能推出这个二叉树因为通过这两个遍历方式我们不能得到左侧、右侧的子树是什么。 本期博客到这里就结束了大家下来了可以自己去画图理解不懂之处或者私信博主、评论留言都可以。感谢你的阅读我们下期再见
