刚开始学树的时候，觉得树这种数据结构很复杂，看到就惧怕，但是仔细分析下它的结构，
发现也没多复杂，当然这只是基本操作，对于树的进一步的运用，确实还是需要花时间去掌握，这里只是关于树的基本操作。
广义表对树的表示非常形象，比如a(b,c(d,e))表示的就是a是根节点，它有b，c两个孩子结点，而c又有两个孩子结点。
在构造树的时候，遇到（表示左孩子开始，遇到，表示右孩子开始，）表示该结点的相关数据结束。即遇到字符便进栈，如果后面跟着的是（，则设置k=1，表示后面跟着的字符是它的左孩子，如果遇到的是，，表示右孩子信息开始，如果是）则表示栈顶元素的结点信息结束，此时执行出栈操作，直到字符串结束。
关于树的遍历，就是
递归的运用，递归也是用栈来实现的，但是没有必要去关注他的细节，重点是它的思想。
1.前序 先输出根，再遍历左子树，再遍历右子树
2.中序 先遍历左子树，再输出根，再遍历右子树
3.后续 先遍历左子树，再遍历右子树，再输出根
结点类代码
class="java" name="code">
package BTree;
public class Node {
private Object data;
private Node left;
private Node right;
public Node(){}
public Node(Object data,Node left,Node right){
this.data=data;
this.left=left;
this.right=right;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
树的基本操作的代码
package BTree;
public class BTree {
private int Stack_size=30;
private int Queue_size=30;
Node createTree(Node bt,String a){ //Node是树的根节点，a是树的广义表的表示
Node p=null; //临时节点，用来存放待放入的树的结点
Node []s=new Node[Stack_size];
int top=-1;
int k=0,i=0;
while(i<a.length()-1){
//System.out.println(a.charAt(i));
switch(a.charAt(i)){
case ' ':break;
case '(':
if(top==Stack_size-1){
System.out.println("stack is too small");
}
top++;
s[top]=p;
k=1; //表示该节点是左子树
break;
case ')':
if(top==-1){
System.out.println("error!");
}
top--;
break;
case ',':k=2;break; //表示该节点是右子树
default:
p=new Node(a.charAt(i),null,null);
if(bt==null){
bt=p; //树为空，将该结点定为初始结点
}
else{
if(k==1)
s[top].setLeft(p);
// System.out.println(s[top].getLeft().getData());
if(k==2)
s[top].setRight(p);
}
}
i++;
}
return bt;
}
/** public Node createTree1(String exp) {
Node[] nodes = new Node[3];//node数目是层数，当遇到）回溯找到父节点
Node b, p = null;//b为根节点，p为当前创造的节点
int top = -1, k = 0, j = 0;//j当前广义表的位置,k左子树还是右子树
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) {//如果root为空
b = p;
} else {
switch (k) {
case 1:
nodes[top].setLeft(p);
break;
case 2:
nodes[top].setRight(p);
break;
}
}
}
j++;
data = exps[j];
}
return b;
} */
void preOrder(Node bt){ //前序遍历结果
if(bt!=null){
System.out.print(" "+bt.getData());
preOrder(bt.getLeft());
preOrder(bt.getRight());
}
//return;
}
void inOrder(Node bt){ //中序遍历结果
if(bt!=null){
inOrder(bt.getLeft());
System.out.print(" "+bt.getData());
inOrder(bt.getRight());
}
}
void postOrder(Node bt){ //后续遍历结果
if(bt!=null){
postOrder(bt.getLeft());
postOrder(bt.getRight());
System.out.print(" "+bt.getData());
}
}
public int isEmpty(Node bt){ //返回树是否为空
if(bt!=null)
return 0;
else
return 1;
}
public int getDepth(Node bt){ //求树的深度
int ldepth,rdepth;
if(bt==null)
return 0;
else{
ldepth=getDepth(bt.getLeft());
rdepth=getDepth(bt.getRight());
if(ldepth>rdepth)
return ldepth+1;
else
return rdepth+1;
}
}
public Node find(Node bt,Object x){ //在书中查找某个元素，返回该结点
Node f=null;
if(bt==null)
return null;
else
if(bt.getData()==x)
return bt;
else{
if((f=find(bt.getLeft(),x))!=null) //递归查找左子树
return f;
if((f=find(bt.getRight(),x))!=null)//递归查找右子树
return f;
}
return null;
}
public void print(Node bt){ //以广义表的形式输出树的结构
if(bt!=null){
System.out.print(bt.getData());
if(bt.getLeft()!=null||bt.getRight()!=null){
System.out.print("(");
print(bt.getLeft());
if(bt.getRight()!=null)
System.out.print(",");
}
print(bt.getRight());
System.out.print(")");
}
}
public void clearTree(Node bt){ //清空树
if(bt!=null)
{
clearTree(bt.getLeft());
clearTree(bt.getLeft());
bt=null;
}
}
public void levelOrder(Node bt){ //以层次顺序输出树，借助队列来实现
Node p;
Node nodes[]=new Node[Queue_size];
int front=0,rear=0;
if(bt!=null){
rear=(rear+1)%Queue_size;
nodes[rear]=bt;
}
while(rear!=front){
front=(front+1)%Queue_size;
p=nodes[front];
System.out.print(" "+p.getData());
if(p.getLeft()!=null){
rear=(rear+1)%Queue_size;
nodes[rear]=p.getLeft();
}
if(p.getRight()!=null){
rear=(rear+1)%Queue_size;
nodes[rear]=p.getRight();
}
}
}
}
以下便是测试代码：
package BTree;
public class Test {
public static void main(String[] args) {
BTree bt=new BTree();
Node node=null;
String a="a(b(c),d(e(f,g),h(,i)))";
Node root=bt.createTree(node,a);
System.out.print("preorder ouput is: ");
bt.preOrder(root);
System.out.print("\ninorder ouput is: ");
bt.inOrder(root);
System.out.print("\npostorder ouput is: ");
bt.postOrder(root);
System.out.println("\nthe result of the research: "+bt.find(root, 'c').getData());
System.out.print("the tree is: ");
bt.print(root);
System.out.print("\nthe depth is: "+bt.getDepth(root));
System.out.print("\nthe levelorder ouput is: ");
bt.levelOrder(root);
}
}
相关文章
