【数据结构与算法】二叉树广度遍历

喜欢ヅ旅行 2022-08-11 09:59 493阅读 0赞

二叉树的广度遍历想想还是比较简单的，利用队列存储当前结点的左儿子和右儿子用作未来的访问。

*  代码实现

/**
     * 源码名称：TreeBFS.java 
     * 日期：2014-08-25 
     * 程序功能：二叉树广度遍历 
     * 版权：CopyRight@A2BGeek 
     * 作者：A2BGeek
     */
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class TreeBFS {
    	class TreeNode<T> {
    		private T mNodeData;
    		private TreeNode<T> mLeftChild;
    		private TreeNode<T> mRightChild;
    
    		public TreeNode(T data, TreeNode<T> left, TreeNode<T> right) {
    			// TODO Auto-generated constructor stub
    			mNodeData = data;
    			mLeftChild = left;
    			mRightChild = right;
    		}
    
    		public T getData() {
    			return mNodeData;
    		}
    
    		public void setData(T data) {
    			mNodeData = data;
    		}
    
    		public TreeNode<T> getLeft() {
    			return mLeftChild;
    		}
    
    		public void setLeft(TreeNode<T> left) {
    			mLeftChild = left;
    		}
    
    		public TreeNode<T> getRight() {
    			return mRightChild;
    		}
    
    		public void setRight(TreeNode<T> right) {
    			mRightChild = right;
    		}
    	}
    
    	public TreeNode<String> createTree() {
    		TreeNode<String> h = new TreeNode<String>("h", null, null);
    		TreeNode<String> g = new TreeNode<String>("g", null, null);
    		TreeNode<String> f = new TreeNode<String>("f", null, null);
    		TreeNode<String> e = new TreeNode<String>("e", null, null);
    		TreeNode<String> d = new TreeNode<String>("d", null, h);
    		TreeNode<String> c = new TreeNode<String>("c", f, g);
    		TreeNode<String> b = new TreeNode<String>("b", d, e);
    		TreeNode<String> a = new TreeNode<String>("a", b, c);
    		return a;
    	}
    
    	public void BFSIterate(TreeNode<String> root) {
    		Queue<TreeNode<String>> queue = new LinkedList<TreeNode<String>>();
    		queue.offer(root);
    		while (!queue.isEmpty()) {
    			TreeNode<String> node = queue.poll();
    			System.out.print(node.getData() + " ");
    			if (node.getLeft() != null) {
    				queue.offer(node.getLeft());
    			}
    			if (node.getRight() != null) {
    				queue.offer(node.getRight());
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		TreeBFS treeBFS = new TreeBFS();
    		TreeNode<String> root = treeBFS.createTree();
    		treeBFS.BFSIterate(root);
    	}
    }