数据结构与算法分析 -- 二叉树的实现，遍历，与应用

 

 1.此篇文章，仅作为《数据结构与算法分析》第四章--树

    中的二叉树一节的读书笔记，发出来供大家共同学习。

 

 2.在开始之前，极力向大家推荐Google Docs. 并非做广告，而是google的产品，不得不让人喜欢。 本文中的插图就是用google docs中的编辑器画的。 很好用。 大家可以试一试

 

 3.本文使用图片方式记录，结合图片与文字，能更加容易理解。 文中涉及到 后缀表达式，关于此方面的内容，可以参考我之前的读书笔记 -- 数据结构与算法分析 读书笔记 --栈的应用

 

 4.最后附上，本文中示例。 树表达式的简单实现代码， 由于数据结构整处于学习中，难免代码丑陋，请更位牛人拍砖，赐教。

 

 关于树的一些基本概念的图片（虽丑陋，但是本人一笔笔画的）：

 

 关于此实例的代码：

 

package com.base.tree;

import java.util.Stack;

public class MyTreeTest {
	public static void main(String[] args) {
		MyStack mystack=new MyStack();
		MyTree tree=mystack.postfixhandler("ab+cde+**");
		MyTree.preorder(tree);//先序输出
	}
}

class MyTree {
	private String data;
	private MyTree left;
	private MyTree right;

	public MyTree(String data) {
		this.data = data;
	}

	public void setLeft(MyTree left) {
		this.left = left;
	}

	public void setRight(MyTree right) {
		this.right = right;
	}
	
	public MyTree getLeft() {
		return left;
	}

	public MyTree getRight() {
		return right;
	}

	public String getData() {
		return data;
	}
	
	/**
	 * 先序遍历 左-中-右
	 */
	public static void preorder(MyTree tree){
		if(tree==null)return;
		System.out.println(tree.getData());
		preorder(tree.getLeft());
		preorder(tree.getRight());
	}
	
	/**
	 * 后序遍历 左-右-中(data)
	 */
	public static void postorder(MyTree tree){
		if(tree==null)return;
		postorder(tree.getLeft());
		postorder(tree.getRight());
		System.out.println(tree.getData());
	}
	
	/**
	 * 中序遍历 左-中-右
	 */
	public static void inorder(MyTree tree){
		if(tree==null)return;
		postorder(tree.getRight());
		System.out.println(tree.getData());
		postorder(tree.getLeft());
	}
}

class MyStack {
	/**
	 * 后缀表达式处理方法
	 * 
	 * @param postfix
	 */
	public MyTree postfixhandler(String str) {
		Stack<MyTree> result = new Stack<MyTree>();// 栈对象
		for (int i = 0; i < str.length(); i++) {
			// 是否为运算符
			if ("+-*/".indexOf(str.charAt(i) + "") == -1) {
				result.push(new MyTree(str.charAt(i) + ""));
			} else {
				// 栈为空，则无法后续操作
				if (!result.isEmpty()) {
					// 将之前的树出栈,构造新的树，并入栈操作
					MyTree root = new MyTree(str.charAt(i) + "");					
					root.setRight(result.pop());
					root.setLeft(result.pop());
					result.push(root);
				}
			}
		}
		return result.pop();
	}
}

 

 

   最后输出结果：

 

*
+
a
b
*
c
+
d
e