二分搜索树的遍历和二叉树的遍历是一致的(二分搜索树的实质本身就是一棵二叉树),直接使用二叉树的遍历即可.
大一的时候数据结构学的还可以,感觉不是特别复杂
二叉树的遍历方式:
- 深度优先遍历
1.前序遍历
2.中序遍历
3.后序遍历
- 广度优先遍历
层序遍历
前序遍历
根节点->左孩子->右孩子
前序遍历
递归实现
/**
* 对二叉树进行前序遍历
*/
public void preOrder(){
preOrder(root);
}
/**
* 前序遍历的递归方式,深度优先
* 当前节点->左孩子->右孩子
* @param node 传入的节点
*/
private void preOrder(Node node){
//遍历到叶子节点时,退出当前的路线
if (node == null){
return;
}
//1.遍历当前节点
System.out.print(node.data+"->");
//2.遍历左孩子
preOrder(node.left);
//3.遍历右孩子
preOrder(node.right);
}
非递归实现
/**
* 前序遍历的非递归实现方式
*/
public void preOrderNr(){
//使用栈辅助实现前序遍历
Stack<Node> stack = new Stack<>();
/*
前序遍历的过程就是先访问当前节点,然后再访问左子树,然后再右子树
使用栈实现的时候,可以先将当前的节点入栈
当前节点出站的时候,分别将右孩子,左孩子入(栈的特点:先进后出)
*/
stack.push(root);
//栈不为空时
while (!stack.isEmpty()){
Node node = stack.pop();
//前序遍历当前的节点
System.out.print(node.data + "->");
//先进后出
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
中序遍历
左孩子->根节点->右孩子
中序遍历
递归实现
/**
* 对中序遍历进行中序遍历
*/
public void midOrder(){
midOrder(root);
}
/**
* 中序遍历的递归方式,深度优先
* 左孩子->当前节点->右孩子
* @param node 传入的节点
*/
private void midOrder(Node node){
if (node == null){
return;
}
//1.中序遍历左孩子
midOrder(node.left);
//2.遍历根节点
System.out.print(node.data+"->");
//3.遍历右孩子
midOrder(node.right);
}
非递归实现
/**
* 中序遍历的非递归实现方式
*/
public void midOrderNr(){
//使用栈辅助实现前序遍历
Stack<Node> stack = new Stack<>();
//辅助节点
Node p = root;
stack.add(p);
System.err.println();
//只要存在左孩子,就将左孩子入栈
while (!stack.isEmpty()){
if (p != null && p.left != null){
stack.add(p.left);
p = p.left;
}else {
p = stack.pop();
System.out.print(p.data+"->");
if (p != null && p.right != null){
//将右孩子入栈
stack.add(p.right);
p = p.right;
}else {
p = null;
}
}
}
后序遍历
左孩子->右孩子->根节点
后序遍历
递归实现
/**
* 二叉树的后序遍历
*/
public void afterOrder(){
afterOrder(root);
}
/**
* 左孩子->右孩子->父节点
* @param node 父节点
*/
private void afterOrder(Node node) {
if (node == null){
return;
}
afterOrder(node.left);
afterOrder(node.right);
System.out.print(node.data+"->");
}
非递归实现
/**
* 后序遍历的非递归实现方式
*/
public void afterOrderNr(){
if (root != null){
Stack<Node> stack = new Stack<>();
stack.push(root);
Node p;
while (!stack.isEmpty()){
p = stack.peek();
if (p.left != null && root != p.left && root != p.right){
stack.push(p.left);
}else if (p.right != null && root!= p.right){
stack.push(p.right);
}else {
System.err.print(stack.pop().data+"->");
root = p;
}
}
}
}
层序遍历
从左到右,从上到下
层序遍历
/**
* 层序遍历,从左到右,从上到下,一次遍历
* 借助队列实现
*/
public void levelOrder(){
Queue<Node> queue = new LinkedList<>();
/*
* 遍历过程:
* 1. 首先根节点入队
* 2. 每次出队时, 都将当前节点的左右孩子先后入队
* 3. 如果队列为空的话, 则表示层序遍历结束
* 5
* / \
* 3 6
* / \ \
* 2 4 8
* 针对上面的二分搜索树, 详细描述一下层序遍历步骤
* 1. 5入队, 队列元素 : head->[5]<-tail
* 2. 5出队, 5的左子树3, 6入队, 由于队列是先入先出(FIFO), 所以先左后右, 队列元素 : head->[3, 6]<-tail
* 3. 3出队, 2, 4入队, 队列元素 : head->[6, 2, 4]<-tail
* 4. 6出队, 左孩子为空,所以8入队, 队列元素 : head->[2, 4, 8]<-tail
* 5. 2,4,8依次出队, 由于这三个节点都是叶子节点, 无子节点, 所以这三个节点出队后队列为空, 层序遍历完成
* 6. 按照出队的顺序演示的遍历结果为 : 5 3 6 2 4 8
*/
queue.add(root);
while (!queue.isEmpty()){
Node p = queue.poll();
System.err.print(p.data+"->");
if (p.left != null){
queue.add(p.left);
}
if (p.right != null){
queue.add(p.right);
}
}
小结:
相对来说非递归方式的效率会更高,但是递归方式实现逻辑更加清晰
参考博客:
https://blog.csdn.net/davidddl/article/details/75667092
https://blog.csdn.net/love905661433/article/details/82981527
网友评论