树--05---二叉树--02---二叉搜索树(BST)遍历

文章目录二叉树(BST)基础遍历----深度优先1. 前序遍历前序遍历的API实现步骤用的jDK自带的队列 LinkedBlockingDeque代码测试2.中序遍历中序遍历是按照Key从小到大遍历,最为重要中序遍历的API实现步骤代码测试:3. 后序遍历遍历的API实现步骤代码测试:二叉树的层序遍历----广度优先层序遍历的API实现步骤代码实现:测试:二叉树(BST)基础遍历----深度优先很多情况下我们可能需要像遍历数组数组一样遍历树从而拿出树中存储的每一个元素由于树状结构和线性结构不一样它没有办法从头开始依次向后遍历所以存在如何遍历也就是按照什么样的搜索路径进行遍历的问题。我们把树简单的画作上图中的样子由一个根节点、一个左子树、一个右子树组成那么按照根节点什么时候被访问我们可以把二叉树的遍历分为以下三种方式前序遍历先访问根结点然后再访问左子树最后访问右子树中序遍历先访问左子树中间访问根节点最后访问右子树后序遍历先访问左子树再访问右子树最后访问根节点如果我们分别对下面的树使用三种遍历方式进行遍历得到的结果如下1. 前序遍历前序遍历的API实现步骤把当前结点的key放入到队列中;找到当前结点的左子树如果不为空递归遍历左子树找到当前结点的右子树如果不为空递归遍历右子树用的jDK自带的队列 LinkedBlockingDeque代码//获取整个树中所有的键publicQueueKeypreErgodic(){QueueKeykeysnewLinkedBlockingDeque();preErgodic(root,keys);returnkeys;}//获取指定树x的所有键并放到keys队列中privatevoidpreErgodic(Nodex,QueueKeykeys){if(xnull){return;}//把x结点的key放入到keys中keys.add(x.key);//递归遍历x结点的左子树if(x.left!null){preErgodic(x.left,keys);}//递归遍历x结点的右子树if(x.right!null){preErgodic(x.right,keys);}}测试Testpublicvoidtest01(){//创建树对象BinaryTreeString,StringtreenewBinaryTree();//往树中添加数据tree.put(E,5);tree.put(B,2);tree.put(G,7);tree.put(A,1);tree.put(D,4);tree.put(F,6);tree.put(H,8);tree.put(C,3);//遍历QueueStringkeystree.preErgodic();for(Stringkey:keys){Stringvaluetree.get(key);System.out.println(key----value);}}2.中序遍历中序遍历是按照Key从小到大遍历,最为重要中序遍历的API实现步骤找到当前结点的左子树如果不为空递归遍历左子树把当前结点的key放入到队列中;找到当前结点的右子树如果不为空递归遍历右子树代码//使用中序遍历获取树中所有的键publicQueueKeymidErgodic(){QueueKeykeysnewLinkedBlockingDeque();midErgodic(root,keys);returnkeys;}//使用中序遍历获取指定树x中所有的键并存放到key中privatevoidmidErgodic(Nodex,QueueKeykeys){if(xnull){return;}//先递归把左子树中的键放到keys中if(x.left!null){midErgodic(x.left,keys);}//把当前结点x的键放到keys中keys.add(x.key);//在递归把右子树中的键放到keys中if(x.right!null){midErgodic(x.right,keys);}}测试:Testpublicvoidtest02(){//创建树对象BinaryTreeString,StringtreenewBinaryTree();//往树中添加数据tree.put(E,5);tree.put(B,2);tree.put(G,7);tree.put(A,1);tree.put(D,4);tree.put(F,6);tree.put(H,8);tree.put(C,3);//遍历QueueStringkeystree.midErgodic();for(Stringkey:keys){Stringvaluetree.get(key);System.out.println(key----value);}}3. 后序遍历遍历的API实现步骤找到当前结点的左子树如果不为空递归遍历左子树找到当前结点的右子树如果不为空递归遍历右子树把当前结点的key放入到队列中;代码//使用后序遍历把整个树中所有的键返回publicQueueKeyafterErgodic(){QueueKeykeysnewLinkedBlockingDeque();afterErgodic(root,keys);returnkeys;}//使用后序遍历把指定树x中所有的键放入到keys中privatevoidafterErgodic(Nodex,QueueKeykeys){if(xnull){return;}//通过递归把左子树中所有的键放入到keys中if(x.left!null){afterErgodic(x.left,keys);}//通过递归把右子树中所有的键放入到keys中if(x.right!null){afterErgodic(x.right,keys);}//把x结点的键放入到keys中keys.add(x.key);}测试:Testpublicvoidtest03(){//创建树对象BinaryTreeString,StringtreenewBinaryTree();//往树中添加数据tree.put(E,5);tree.put(B,2);tree.put(G,7);tree.put(A,1);tree.put(D,4);tree.put(F,6);tree.put(H,8);tree.put(C,3);//遍历QueueStringkeystree.afterErgodic();for(Stringkey:keys){Stringvaluetree.get(key);System.out.println(key----value);}}二叉树的层序遍历----广度优先所谓的层序遍历就是从根节点第一层开始依次向下获取每一层所有结点的值有二叉树如下那么层序遍历的结果是EBGADFHC层序遍历的API实现步骤创建队列存储每一层的结点使用循环从队列中弹出一个结点获取当前结点的key如果当前结点的左子结点不为空则把左子结点放入到队列中如果当前结点的右子结点不为空则把右子结点放入到队列中代码实现://使用层序遍历获取整个树中所有的键publicQueueKeylayerErgodic(){//定义两个队列分别存储树中的键和树中的结点QueueKeykeysnewLinkedBlockingDeque();QueueNodenodesnewLinkedBlockingDeque();//默认往队列中放入根结点nodes.add(root);while(!nodes.isEmpty()){//从队列中弹出一个结点把key放入到keys中Nodennodes.poll();keys.add(n.key);//判断当前结点还有没有左子结点如果有则放入到nodes中if(n.left!null){nodes.add(n.left);}//判断当前结点还有没有右子结点如果有则放入到nodes中if(n.right!null){nodes.add(n.right);}}returnkeys;}测试:Testpublicvoidtest01(){//创建树对象BinaryTreeString,StringtreenewBinaryTree();//往树中添加数据tree.put(E,5);tree.put(B,2);tree.put(G,7);tree.put(A,1);tree.put(D,4);tree.put(F,6);tree.put(H,8);tree.put(C,3);//遍历QueueStringkeystree.layerErgodic();for(Stringkey:keys){Stringvaluetree.get(key);System.out.println(key----value);}}