二叉树实现复杂运算

 

                                                  二叉树

        树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树，完全二叉树，排序二叉树。

  利用二叉树，我们可以实现计算器的复杂运算，一下代码仅支持单数字运算，多位还需要添加判断语句。

package twotree;

public class Node {
	Node left;
	Node right;
	Node parent;
	int data;
	String str;
}

 以上是我们定义的的树左节点，右节点，父节点，数据，及符号
接下来就是关键代码：

 

 

 

public class Tree {
	Node root;//定义根节点
	public void add(String str,int data){
		Node node=new Node();//创建一个新结点
		node.data=data;//接受加入数据
		node.str=str;//接受加入数据
		//判断如果根节点为空
		if(root==null){
			//第一个添加的节点为根
			root=node;
		}
		else{
			if(root.parent==null){
				//父节点为空，指向node
				root.parent=node;
				//将node的左节点插入到root上
				node.left=node;
				
			}
		
		else{
			//右节点为空，指向node
			root.parent.right=node;
			//将根节点指向父节点，将root节点向上移动一层
			root=root.parent;
		}
	}

	}
	public int cal(Node node){
		//如果节点不为空，右节点不为空
		if(node!=null&&node.right!=null){
			//判断运算符
			if(node.str.equals("-")){
				//调用递归函数
				return cal(node.left)-node.right.data;
			}
			if(node.str.equals("+")){
				//调用递归函数
				return cal(node.left)+node.right.data;
			}
		}
		else{
			//如果左节点为空，就返回当前元素
			if(node.left==null){
				return node.data;
			}
		}
		return 0;
	}
	
	//打印树
	public void printTree(){
		//定义节点指向根节点
		Node temp=root;
		//当节点不为空
		while(temp!=null){
			//打印节点所带的运算符和计算的数字
			System.out.print("str="+temp.str+",data="+temp.data);
			//父节点不为空时
			if(temp.parent != null){
				//父节点右子树不为空时
				if(temp.parent.right != null){
					System.out.print(" right:str="+temp.parent.right.str+",data="+temp.parent.right.data);
				}
			}
			System.out.println();
			temp=temp.left;//下移节点到左边
			
		}
	}
	public static void main(String args[]){
		//实例化一个树的对象
		Tree tree=new Tree();
		//定义复合运算
		String str="1+4-5-8+9-5";
		//得到每一个字符
		for(int i=0;i<str.length();i++){
			char c=str.charAt(i);
			if(c=='+'||c=='-'){
				tree.add(""+c, 0);
			}
			else{
				//将数字转化为字符型
				tree.add("", Integer.parseInt(""+c));
			}
		}
		//打印树
		tree.printTree();
		//输出计算结果
		System.out.println(tree.cal(tree.root));
	}
}

 出来结果如下：