Java实现二叉树的递归和非递归遍历

- 日理万妓 2023-07-14 08:21 29阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

## 1.1 递归前序遍历 ##

//递归前序遍历
    public void preOrderRec(Node temp) {
        
    	if(temp == null) {
        
    		System.out.println("BinaryTree is empty.");
    	}else {
        
    		System.out.print(temp.data + " ");
    		if(temp.left != null) {
        
    			preOrderRec(temp.left);
    		}
    		if(temp.right != null) {
        
    			preOrderRec(temp.right);
    		}
    	}
    }

## 1.2 非递归前序遍历算法一 ##

算法思路：先遍历到二叉树的最左边的子节点，过程中同时打印数据被遍历的子节点并将其压栈，到末尾时依次出栈遍历右子节点。该方法将子二叉树的根节点压栈，利用根节点寻找它的右子节点。

//非递归前序遍历算法一，压栈的是每个二叉子树的根节点，利用这个根节点来找右子节点
    public void preOrderNotRec2() {
        
    	Node temp = root;
    	Stack<Node> stack = new Stack<Node>();
    	while(!stack.isEmpty() || temp != null) {
        
    		if(temp != null) {
        
    			System.out.print( temp.data + " ");
    			stack.push(temp);
    			temp = temp.left;
    		}else {
        
    			temp = stack.pop();
    			temp = temp.right;
    		}
    	}
    }

## 1.3 非递归前序遍历算法二 ##

算法思路：  
1，将根节点压栈。  
2，从栈顶弹出节点，记为temp，打印temp数据，然后再将temp的右子节点和左子节点分别入栈。  
3，重复步骤2直至栈空。  
该算法与算法一不同之处是栈里存储的是每个子二叉树的右子节点，而不是根节点。

//非递归前序遍历算法一，压栈的是右子节点，
    public void preOrderNotRec1() {
        
    	Node temp = root;
    	Stack<Node> stack = new Stack<Node>();
    	stack.push(temp);
    	while(!stack.isEmpty()) {
        
    		temp = stack.pop();
    		System.out.print( temp.data + " ");
    		if(temp.right != null) {
        
    			stack.push(temp.right);
    		}
    		if(temp.left != null) {
        
    			stack.push(temp.left);
    		}
    	}
    }

## 2.1 递归中序遍历 ##

//递归中序遍历
    public void inOrderRec(Node temp) {
        
    	if(temp == null) {
        
    		System.out.println("BinaryTree is empty.");
    	}else {
        
    		if(temp.left != null) {
        
    			inOrderRec(temp.left);
    		}
    		System.out.print(temp.data + " ");
    		if(temp.right != null) {
        
    			inOrderRec(temp.right);
    		}
    	}
    }

## 2.2 非递归中序遍历 ##

和非递归前序遍历算法一类似，只是输出数据的位置不同。

//非递归中序遍历
    public void inOrderNotRec() {
        
    	Stack<Node> stack = new Stack<Node>();
    	Node temp = root;
    	while(!stack.isEmpty() || temp != null) {
        
    		if(temp != null) {
        
    			stack.push(temp);
    			temp = temp.left;
    		}else {
        
    			temp = stack.pop();
    			System.out.print(temp.data + " ");
    			temp = temp.right;
    		}
    	}
    }

## 3.1 递归后序遍历 ##

//递归后序遍历
    public void postOrderRec(Node temp) {
        
    	if(temp == null) {
        
    		System.out.println("BinaryTree is empty.");
    	}else {
        
    		if(temp.left != null) {
        
    			postOrderRec(temp.left);
    		}
    		if(temp.right != null) {
        
    			postOrderRec(temp.right);
    		}
    		System.out.print(temp.data + " ");
    		}
    }

## 3.2 非递归后序遍历算法一 ##

算法思路：后序遍历的难点在于需要判断是从左子树返回还是从右子树返回。若从左子树返回则先遍历右子树，若从右子树返回直接输出。因此我们用里一个栈记录是从左子树返回还是从右子树返回。

具体思路参考：https://www.bilibili.com/video/av23885544

//非递归后序遍历算法一
    public void postOrderNotRec2() {
        
    	Stack<Node> s1 = new Stack<Node>();
    	//用另一个栈记录是从左子树返回还是从右子树返回
    	Stack<Boolean> s2 = new Stack<Boolean>();
    	Node temp = root;
    	boolean flag;
    	while(!s1.isEmpty() || temp != null) {
        
    		if(temp != null) {
        
    			s1.push(temp);
    			s2.push(false);
    			temp = temp.left;
    		}else {
        
    			temp = s1.pop();
    			flag = s2.pop();
    			//false代表从左子树返回，此时需要先到右子树，并将tag改为true
    			if(!flag) {
        
    				s1.push(temp);
    				s2.push(true);
    				temp = temp.right;
    			}else {
        //从右子树返回说明该节点的左右子树的遍历过了，直接输出
    				System.out.print(temp.data + " ");
    				//此时temp位于子二叉树的根节点，不为空，将其手动置空，否则出现死循环
    				temp = null;
    			}
    			
    		}
    	}
    }

## 3.3 非递归后序遍历算法二 ##

非常巧妙，也是用两个栈。  
算法思路：  
1，将根节点压入栈s1。  
2，从s1中弹出节点记为temp，并将temp压入栈s2。然后将temp的左子节点和右子节点分别入栈。  
3，重复步骤2直至栈s1为空。  
4，从栈s2中取出数据并打印，打印的顺序就是后序遍历的顺序。

//非递归后序遍历算法二
    public void postOrderNotRec1() {
        
    	Stack<Node> s1 = new Stack<Node>();
    	Stack<Node> s2 = new Stack<Node>();
    	Node temp = root;
    	s1.push(temp);
    	while(!s1.isEmpty()) {
        
    		temp = s1.pop();
    		s2.push(temp);
    		if(temp.left != null) {
        
    			s1.push(temp.left);
    		}
    		if(temp.right != null) {
        
    			s1.push(temp.right);
    		}
    	}
    	while(!s2.isEmpty()) {
        
    		System.out.print(s2.pop().data + " ");
    	}
    }

## 4 层次遍历 ##

//层次遍历
    public void levelOrder() {
        
    	ArrayDeque<Node> quene = new ArrayDeque<Node>();
    	Node temp = this.root;
    	quene.add(temp);
    	while(!quene.isEmpty()) {
        
    		temp = quene.poll();
    		System.out.print(temp.data + " ");
    		if(temp.left != null) {
        
    			quene.add(temp.left);
    		}
    		if(temp.right != null) {
        
    			quene.add(temp.right);
    		}
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982