【数据结构与算法】二叉树深度遍历（递归）

小咪咪 2022-08-11 08:29 149阅读 0赞

二叉树的深度遍历用递归的话就没有什么好说的了。

*  代码实现

/**
     * 源码名称：TreeIteratorRecursion.java 
     * 日期：2014-08-23 
     * 程序功能：二叉树深度遍历 
     * 版权：CopyRight@A2BGeek 
     * 作者：A2BGeek
     */
    public class TreeIteratorRecursion {
    	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", h, null);
    		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 preIterate(TreeNode<String> root) {
    		if (root == null) {
    			return;
    		} else {
    			System.out.print(root.getData() + " ");
    			preIterate(root.getLeft());
    			preIterate(root.getRight());
    		}
    	}
    
    	public void midIterate(TreeNode<String> root) {
    		if (root == null) {
    			return;
    		} else {
    			midIterate(root.getLeft());
    			System.out.print(root.getData() + " ");
    			midIterate(root.getRight());
    		}
    	}
    
    	public void postIterate(TreeNode<String> root) {
    		if (root == null) {
    			return;
    		} else {
    			postIterate(root.getLeft());
    			postIterate(root.getRight());
    			System.out.print(root.getData() + " ");
    		}
    	}
    
    	public static void main(String[] args) {
    		TreeIteratorRecursion treeIteratorRecursion = new TreeIteratorRecursion();
    		TreeNode<String> root = treeIteratorRecursion.createTree();
    		treeIteratorRecursion.preIterate(root);
    		System.out.println();
    		treeIteratorRecursion.midIterate(root);
    		System.out.println();
    		treeIteratorRecursion.postIterate(root);
    	}
    }