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

68 阅读 0 评论 45 点赞

我是靠谱客的博主帅气玉米，最近开发中收集的这篇文章主要介绍【数据结构与算法】二叉树深度遍历（递归），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

代码实现

/**
 * 源码名称：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);
	}
}