一.遍历
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。
1.先序遍历:首先访问根，再先序遍历左子树，最后先序遍历右子树。
2.中序遍历:首先中序遍历左子树，再访问根，最后中序遍历右子树。
3.后序便利:首先后序遍历左子树，再后序遍历右子树，最后访问根。
二.二叉树的字符串表达式
String expression = "A(B(D(,G)),C(E,F))";与该广义表对应的二叉树为：
写代码前，我们通过观察二叉树和广义表，先得出一些结论：
每当遇到字母，将要创建节点
每当遇到“（”，表面要创建左孩子节点
每当遇到“，”，表明要创建又孩子节点
每当遇到“）”，表明要返回上一层节点
广义表中“（”的数量正好是二叉树的层数
三.代码
1.树的每个节点
1 public class Node { 2 //节点的数据
3 private char data;
4 //节点的左子节点
5 private Node lchild;
6 //节点的右子节点
7 private Node rchild;
8
9 public Node() {
10 super();
11 }
12
13 public Node(char data, Node lchild, Node rchild) {
14 super();
15 this.data = data;
16 this.lchild = lchild;
17 this.rchild = rchild;
18 }
19
20 public char getData() {
21 return data;
22 }
23
24 public void setData(char data) {
25 this.data = data;
26 }
27
28 public Node getLchild() {
29 return lchild;
30 }
31
32 public void setLchild(Node lchild) {
33 this.lchild = lchild;
34 }
35
36 public Node getRchild() {
37 return rchild;
38 }
39
40 public void setRchild(Node rchild) {
41 this.rchild = rchild;
42 }
43
44 public String toString(){
45 return ""+getData();
46 }
47
48 }
2.二叉树
1 /**2 * 二叉树，包含有创建二叉树，遍历二叉树的方法
3 * @author phase1
4 *
5 */
6 public class BinaryTree {
7 //二叉树的字符串表达式
8 private String tree;
9 //树的节点表式
10 private Node treeNode;
11 //构造方法
12 public BinaryTree(String tree){
13 this.tree = tree;
14 }
15 public BinaryTree(Node treeNode){
16 this.treeNode = treeNode;
17 }
18 public String getTree() {
19 return tree;
20 }
21 public void setTree(String tree) {
22 this.tree = tree;
23 }
24 public Node getTreeNode() {
25 return treeNode;
26 }
27 public void setTreeNode(Node treeNode) {
28 this.treeNode = treeNode;
29 }
30
31 /**
32 * 根据二叉树的字符串表式创建二叉树的节点表示法
33 * @return
34 */
35 public Node createTree(){
36 //将树的字符串表示转换成char数组
37 char[] data = tree.toCharArray();
38 //根节点，有了根节点所有节点都能获取
39 Node root = null;
40 //用于存放每一层的根节点，值动态的
41 List<Node> nodes = new LinkedList<Node>();
42 int level = -1;
43 //控制创建左右子节点（L,R）
44 char child = 'N';
45 //当前节点
46 Node now = null;
47 for(int i=0;i<data.length;i++){
48 switch(data[i]){
49 case '(':
50 level++;
51 //此时nodes.get(level)与now对应
52 nodes.add(now);
53 child = 'L';
54 break;
55 case ',':
56 child = 'R';
57 break;
58 case ')':
59 nodes.remove(level);
60 level--;
61 break;
62 default:
63 now = new Node(data[i], null, null);
64 if(root == null){
65 root = now;
66 }else{
67 switch(child){//此时nodes.get(leve)为now的父节点
68 case 'L':
69 nodes.get(level).setLchild(now);
70 break;
71 case 'R':
72 nodes.get(level).setRchild(now);
73 }
74 }
75 }
76
77 }
78 return root;
79 }
80
81 /**
82 * 先序遍历
83 * @param node
84 */
85 public String beforeOrder(Node node){
86 StringBuilder nodes = new StringBuilder();
87 if(node != null){
88 //根节点
89 nodes.append(node.getData());
90 //先序遍历左子节点
91 nodes.append(beforeOrder(node.getLchild()));
92 //先序遍历右子节点
93 nodes.append(beforeOrder(node.getRchild()));
94 }
95 return nodes.toString();
96 }
97
98 /**
99 * 中序遍历
100 * @param node
101 */
102 public String inOrder(Node node){
103 StringBuilder nodes = new StringBuilder();
104 if(node != null){
105 //中序遍历左子节点
106 nodes.append(inOrder(node.getLchild()));
107 //根节点
108 nodes.append(node.getData());
109 //中序遍历右子节点
110 nodes.append(inOrder(node.getRchild()));
111 }
112 return nodes.toString();
113 }
114
115 /**
116 * 后序遍历
117 * @param node
118 */
119 public String afterOrder(Node node){
120 StringBuilder nodes = new StringBuilder();
121 if(node != null){
122 //后序遍历左子节点
123 nodes.append(afterOrder(node.getLchild()));
124 //后序遍历右子节点
125 nodes.append(afterOrder(node.getRchild()));
126 //根节点
127 nodes.append((node.getData()));
128 }
129 return nodes.toString();
130 }
131
132 public static void main(String[] args) {
133 String expression = "A(B(D(,G)),C(E,F))";
134 BinaryTree tree = new BinaryTree(expression);
135 Node node = tree.createTree();
136 System.out.println(tree.beforeOrder(node));//ABDGCEF
137 System.out.println(tree.inOrder(node)); //DGBAECF
138 System.out.println(tree.afterOrder(node));//GDBEFCA
139 }
140 }
还没有评论，来说两句吧...