Java实现二叉树三种遍历算法

时间：2021-06-26 17:32:14

</pre><p></p><p>参考网上一些资料测试整理了一下二叉树遍历的Java实现代码。</p>二叉树三种遍历方式：先序遍历、中序遍历、后序遍历。<p>首先定义二叉树类：</p><p></p><pre code_snippet_id="422510" snippet_file_name="blog_20140708_2_1633299" name="code" class="java">package mm.test.tree;

public class BinaryTree {

	char data;					//根节点
	BinaryTree leftChild;		//左孩子
	BinaryTree rightChild;		//右孩子
	
	public BinaryTree() {
		
	}
	
	public void visit() {
		System.out.println(this.data);
	}
	
	public BinaryTree(char data) {
		this.data = data;
		this.leftChild = null;
		this.rightChild = null;
	}

	public BinaryTree getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(BinaryTree leftChild) {
		this.leftChild = leftChild;
	}

	public BinaryTree getRightChild() {
		return rightChild;
	}

	public void setRightChild(BinaryTree rightChild) {
		this.rightChild = rightChild;
	}

	public char getData() {
		return data;
	}

	public void setData(char data) {
		this.data = data;
	}

}

先序遍历思想：根左右。首先遍历根节点，然后遍历左子树和右子树。

package mm.test.tree;

import java.util.Stack;

public class VisitBinaryTree {

	//先序遍历非递归算法
	private void preOrder(BinaryTree root) {

		if(root!=null) {
			
			Stack<BinaryTree> stack = new Stack<BinaryTree>();
			
			for (BinaryTree node = root; !stack.empty() || node != null;) {
				
				//当遍历至节点位空的时候出栈
				if(node == null) {
					node = stack.pop();
				}
				
				node.visit();
				
				//遍历右孩子存入栈内
				if(node.getRightChild()!=null) {
					stack.push(node.getRightChild());
				}
				
				//遍历左子树节点
				node = node.getLeftChild();
				
			}
			
		}
		
	}
	
	//先序遍历递归算法
	public void preOrderRecursion(BinaryTree root) {
		if(root!=null) {
			root.visit();
			preOrderRecursion(root.getLeftChild());
			preOrderRecursion(root.getRightChild());
		}
	}
}

测试代码： 

public static void main(String args[]) {
		
		 BinaryTree node = new BinaryTree('A');  
       <span style="white-space:pre">		</span> BinaryTree root = node;  
        <span style="white-space:pre">	</span> BinaryTree nodeL1;
       <span style="white-space:pre">		</span> BinaryTree nodeL;
       <span style="white-space:pre">		</span> BinaryTree nodeR;
       <span style="white-space:pre">		</span> node.setLeftChild(new BinaryTree('B'));  
       <span style="white-space:pre">		</span> node.setRightChild(new BinaryTree('C'));  
          
       <span style="white-space:pre">		</span> nodeL1 = node.getLeftChild();  
      <span style="white-space:pre">		</span> nodeL1.setLeftChild(new BinaryTree('D'));  
       <span style="white-space:pre">		</span> nodeL1.setRightChild(new BinaryTree('E')); 
        
       <span style="white-space:pre">		</span> nodeL = nodeL1.getLeftChild();  
       <span style="white-space:pre">		</span> nodeL.setLeftChild(new BinaryTree('F'));
        
       <span style="white-space:pre">		</span> node = node.getRightChild();  
        <span style="white-space:pre">	</span> node.setLeftChild(new BinaryTree('G'));  
        <span style="white-space:pre">	</span> node.setRightChild(new BinaryTree('H'));  
        
        <span style="white-space:pre">	</span> nodeR = node.getLeftChild();  
        <span style="white-space:pre">	</span> nodeR.setLeftChild(new BinaryTree('I'));  
        <span style="white-space:pre">	</span> nodeR.setRightChild(new BinaryTree('J')); 
        
        <span style="white-space:pre">	</span> VisitBinaryTree vt= new VisitBinaryTree();  
		
		//先序遍历递归和非递归测试
		vt.preOrder(root);
		vt.preOrderRecursion(root);

	}

中序遍历算法： 
//中序遍历的非递归算法
	public void inOrder(BinaryTree root) {
		
		if(root!=null) {
			
			Stack<BinaryTree> stack = new Stack<BinaryTree>();
			
			for (BinaryTree node = root; !stack.empty() || node != null; ) {
				
				//寻找最左的左子树节点,并将遍历的左节点进栈
				while(node!=null) {
					stack.push(node);
					node = node.getLeftChild();
				}
				
				if(!stack.empty()) {
					node = stack.pop();  	 //出栈
					node.visit();			 //读取节点值
					node = node.getRightChild();
				}
			}
		}
	}
	
	//中序遍历的递归算法
	public void inOrderRecursion (BinaryTree root) {
			
			if(root!=null) {
				inOrderRecursion(root.getLeftChild());
				root.visit();
				inOrderRecursion(root.getRightChild());
			}
			
	}
测试代码： 
public static void main(String args[]) {
		
	BinaryTree node = new BinaryTree('A');  
        BinaryTree root = node;  
        BinaryTree nodeL1;
        BinaryTree nodeL;
        BinaryTree nodeR;
        node.setLeftChild(new BinaryTree('B'));  
        node.setRightChild(new BinaryTree('C'));  
          
        nodeL1 = node.getLeftChild();  
        nodeL1.setLeftChild(new BinaryTree('D'));  
        nodeL1.setRightChild(new BinaryTree('E')); 
        
        nodeL = nodeL1.getLeftChild();  
        nodeL.setLeftChild(new BinaryTree('F'));
        
        node = node.getRightChild();  
        node.setLeftChild(new BinaryTree('G'));  
        node.setRightChild(new BinaryTree('H'));  
        
        nodeR = node.getLeftChild();  
        nodeR.setLeftChild(new BinaryTree('I'));  
        nodeR.setRightChild(new BinaryTree('J')); 
        
        VisitBinaryTree vt= new VisitBinaryTree();  
		
		//中序遍历递归和非递归测试
		vt.inOrder(root);
		vt.inOrderRecursion(root);

	}
后序遍历： 

//后序遍历非递归算法
	private void postOrder(BinaryTree root) {
		if(root!=null) {
			Stack<BinaryTree> stack = new Stack<BinaryTree>();
			
			for (BinaryTree node = root; !stack.empty() || node != null;) {
				while(root!=null) {
					stack.push(root);
					root = root.getLeftChild();
				}
				
				while(!stack.empty() && root == stack.peek().getRightChild()) {
					root = stack.pop();  
					root.visit();  
				}
				
				if (stack.empty()) {  
	                return;  
	            } else {  
	            	root = stack.peek().getRightChild();  
	            }  
			}
		}
	}
	
	//后序遍历递归算法
	private void postOrderRecursion(BinaryTree root) {
		if(root!=null) {
			postOrderRecursion(root.getLeftChild());
			postOrderRecursion(root.getRightChild());
			root.visit();
		}
	}

测试方法： 

public static void main(String args[]) {
		
	BinaryTree node = new BinaryTree('A');  
        BinaryTree root = node;  
        BinaryTree nodeL1;
        BinaryTree nodeL;
        BinaryTree nodeR;
        node.setLeftChild(new BinaryTree('B'));  
        node.setRightChild(new BinaryTree('C'));  
          
        nodeL1 = node.getLeftChild();  
        nodeL1.setLeftChild(new BinaryTree('D'));  
        nodeL1.setRightChild(new BinaryTree('E')); 
        
        nodeL = nodeL1.getLeftChild();  
        nodeL.setLeftChild(new BinaryTree('F'));
        
        node = node.getRightChild();  
        node.setLeftChild(new BinaryTree('G'));  
        node.setRightChild(new BinaryTree('H'));  
        
        nodeR = node.getLeftChild();  
        nodeR.setLeftChild(new BinaryTree('I'));  
        nodeR.setRightChild(new BinaryTree('J')); 
        
        VisitBinaryTree vt= new VisitBinaryTree();  
		
		//后序遍历递归和非递归测试
		vt.postOrder(root);
		vt.postOrderRecursion(root);

	}




标签：

相关文章