【数据结构】【二叉树】二叉树的创建和遍历

二叉树的创建有两种方式，一种是递归方式创建，另外一种是非递归方式创建，其中后者比较难，这里使用递归方式创建二叉树。

要求：使用前序序列的方式输入若干个字符，如"

abc,,de,g,,f,,,

"，其中，','表示是空节点，根据该字符序列输出前序遍历字符串，中续遍历字符串,后序遍历字符串。

 

分析问题，如果使用C语言比较方便实现，使用java稍微麻烦一点，需要手动结束输入，这里使用了标识变量flag判断输入的结束。

 

package com.kdyzm.bittree;

class Node {
	char data;
	Node lchild;
	Node rchid;
}

public class Main {
	private static boolean flag = false;

	public static void main(String[] args) throws Exception {
		Node root = createPreBitTree();
		preOderTraverse(root);
		System.out.println();
		inOrderTraverse(root);
		System.out.println();
		endOrderTraverse(root);
	}

	private static void preOderTraverse(Node root) {
		if (root != null) {
			System.out.print(root.data);
			preOderTraverse(root.lchild);
			preOderTraverse(root.rchid);
		}
	}

	private static void endOrderTraverse(Node root) {
		if (root != null) {
			endOrderTraverse(root.lchild);
			endOrderTraverse(root.rchid);
			System.out.print(root.data);
		}
	}

	private static void inOrderTraverse(Node node) {
		if (node != null) {
			inOrderTraverse(node.lchild);
			System.out.print(node.data);
			inOrderTraverse(node.rchid);
		}
	}

	private static Node createPreBitTree() throws Exception {
		if (flag == true) {
			return null;
		}
		Node node = null;
		char ch = (char) System.in.read();
		if (ch == '\n') {
			flag = true;
			return null;
		}
		if (ch == ',') {
			node = null;
		} else {
			node = new Node();
			node.data = ch;
			node.lchild = createPreBitTree();
			node.rchid = createPreBitTree();
		}
		return node;
	}
}

测试用例：

输入
abc,,de,g,,f,,,

输出
abcdegf
cbegdfa
cgefdba

 输出分别是前序遍历、中序遍历、后序遍历的结果。