Esta es una implementación java de clasificación de árbol binario que escribí antes. Debería ser útil para futuras entrevistas. Guárdalo primero.
Prototipo de árbol binario:
En primer lugar, defina la clase de nodo, los datos son los datos del nodo, lchild y rchild son las ramas izquierda y derecha del nodo:
package com.lin.tree;
/**
* @author Author Lin Youqing
* @version Creation time: 2016-8-11 02:46:52 PM
* Class description:
*/
public class Node {
private char data;
private Node lchild;
private Node rchild;
public Node() {
}
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public Node getLchild() {
return lchild;
}
public void setLchild(Node lchild) {
this.lchild = lchild;
}
public Node getRchild() {
return rchild;
}
public void setRchild(Node rchild) {
this.rchild = rchild;
}
public Node(char data, Node lchild, Node rchild) {
super();
this.data = data;
this.lchild = lchild;
this.rchild = rchild;
}
@Override
public String toString() {
return " " + getData() ;
}
}
Clase de árbol:
package com.lin.tree;
/**
* @author Author Lin Youqing
* @version Creation time: 2016-8-11 02:50:03 PM
* Class description:
*/
public class Tree {
public Node createTree(String exp){
Node[] nodes=new Node[3];
Node b,p=null;
int top=-1,k=0,j=0;
char[] exps=exp.toCharArray();
char data=exps[j];
b=null;
while(j<exps.length-1){
switch (data) {
case '(':
top++;
nodes[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
p=new Node(data, null, null);
if(b==null){
b=p;
}else{
switch (k) {
case 1:
nodes[top].setLchild(p);
break;
case 2:
nodes[top].setRchild(p);
break;
}
}
}
j++;
data=exps[j];
}
return b;
}
/**
* pre order recursive
*@author: Lin Youqing
*@date：2016-8-11
*@param
*@param
*/
public void PreOrder(Node node){
if(node==null){
return;
}else{
System.out.print(node.getData()+" ");
PreOrder(node.getLchild());
PreOrder(node.getRchild());
}
}
/**
*in order recursive
*@author: Lin Youqing
*@date：2016-8-11
*@param
*@param
*/
public void InOrder(Node node){
if(node==null){
return;
}else{
InOrder(node.getLchild());
System.out.print(node.getData()+" ");
InOrder(node.getRchild());
}
}
/**
*post order recursive
*@author: Lin Youqing
*@date：2016-8-11
*@param
*@param
*/
public void PostOrder(Node node){
if(node==null){
return;
}else{
PostOrder(node.getLchild());
PostOrder(node.getRchild());
System.out.print(node.getData()+" ");
}
}
}
Categoría de prueba:
package com.lin.tree;
/**
* @author Author Lin Youqing
* @version Creation time: 2016-8-11 03:14:18 PM
* Class description:
*/
public class Test {
public static void main(String[] args) {
String str="A(B(D(,G)),C(E,F))";
Tree tree=new Tree();
Node node=tree.createTree(str);
System.out.println("First Order:");
tree.PreOrder(node);
System.out.println();
System.out.println("Middle Order:");
tree.InOrder(node);
System.out.println();
System.out.println("Post Sequence:");
tree.PostOrder(node);
}
}
Resultados de las pruebas:
First order:
A B D G C E F
Middle order:
D G B A E C F
After sequence:
G D B E F C A .
