利⽤算术表达式构建⼆叉树（java实现）
⼤学学习数据结构的时候做过⼀个计算算术表达式字符串结果的⼩程序，最近学习java接触到了类似的问题，不过不是计算结果，⽽是利⽤它来构造⼆叉树，难度稍微⼤了⼀些。我在这⾥提供两种解决⽅案。相信很多⼈都知道怎么计算表达式的值，利⽤两个栈（符号栈和数字栈）根据运算符优先级进⾏出栈⼊栈操作，我们知道将栈中的运算符和数字替换为⼆叉树的节点就可以在这个过程中顺利的构造⼀个⼆叉树出来。第⼆种⽅法利⽤了递归的思想，我们构造⼆叉树的难点其实主要在于括号的存在，假设⼀个没有括号的算数表达式，如1+2*3-
8/4，我们取得第⼀个运算符+的时候，将其作为⼀个树节点，将1和2分别作为左孩⼦和右孩⼦；当我们取得*时，将2和3分别作为它的左右孩⼦，由于*优先于+，所以*将成为+的右孩⼦；当我们取得-时，将3和8作为其左右孩⼦，由于-优先级低于*，所以要往上*的⽗亲+，由于-的优先级低于+，所以继续+的⽗亲，由于+已经没有⽗亲，+将成为-的孩⼦；最后取得/时，由于/优先级⾼于-，所以直接作为-的右孩⼦。个⼈感觉这两种⽅法都⽐较好理解。第⼆种⽅法的⼆叉树构造顺序如下（直线上的数字代表构造的次序，⽐较有趣的是⽤第⼀种⽅法和第⼆种⽅法构造出来的⼆叉树好像是⼀样的）：
其中⽤到了基本的数据结构树节点TreeNode<E>，使⽤时应该⽤TreeNode<Character>，特别注意第⼀种⽅法不要求树节点中保存⽗指针，但第⼆种要求要保留⽗指针。两种⽅法的核⼼代码列在下⾯了：
第⼀种：
* 将part解析为⼆叉树
* @param part
* @return 返回⼆叉树的根节点，解析失败返回null
*/
public TreeNode<Character> createBinaryTree(String part){
//定义数字栈和操作符栈
Stack<TreeNode<Character>> numStack=new Stack<TreeNode<Character>>();
Stack<TreeNode<Character>> operStack=new Stack<TreeNode<Character>>();
operStack.push(new TreeNode<Character>('#',null,null,null));
for(int i=0;i<part.length();i++){
/
有趣的java小程序/是数字则直接压⼊数字栈
if(isNumber(part.charAt(i))){
numStack.push(new TreeNode<Character>(part.charAt(i),null,
null,null));
continue;
}
//是操作符（注意这⾥没有把左右括号当做操作符）或者左括号，则尝试压⼊ //符号栈
if(isOperator(part.charAt(i))||part.charAt(i)=='('){
Character (operStack.size()-1).getData();
//如果准备压⼊的符号⽐栈顶端的符号优先级低，则栈顶段的符号
//和数字栈中的数字应该弹出，两个数字是符号节点的左右孩⼦，
/
/再将符号节点压⼊数字栈（此时该符号节点已经代表⼀个数字了，
//所以要压⼊数字栈）
while(getPriority(top, part.charAt(i))<0){
//如果符号栈只剩下#，说明算术表达式已经解析完了，返
//回数字栈中的节点
if(top=='#'){
return numStack.pop();
}
TreeNode<Character> temp=operStack.pop();
TreeNode<Character> right=numStack.pop();
TreeNode<Character> left=numStack.pop();
temp.setLefChild(left);
temp.setRigChild(right);
numStack.push(temp);
(operStack.size()-1).getData();
}
operStack.push(new TreeNode<Character>(part.charAt(i),null,null,null));
continue;
}
//如果将⼊栈的是右括号，则符号栈弹出符号并和数字栈弹出的数字组建树节 //点，知道碰到左括号。
if(part.charAt(i)==')'){
Character (operStack.size()-1).getData();
while(top!='('){
TreeNode<Character> temp=operStack.pop();
TreeNode<Character> right=numStack.pop();
TreeNode<Character> left=numStack.pop();
temp.setLefChild(left);
temp.setRigChild(right);
numStack.push(temp);
(operStack.size()-1).getData();
}
operStack.pop();
continue;
}
}
return null;
}
第⼆种⽅法：
* 利⽤算数字符串content构造⼆叉树binaryTree
*/
public TreeNode<Character> CreateBinaryTree(String part){
//先将表达式转换为由不含括号的节点组成的链表结构
List<TreeNode<Character>> list=new ArrayList<TreeNode<Character>>(); for(int i=0;i<part.length();i++){
if(isNumber(part.charAt(i)) || isOperator(part.charAt(i))){
list.add(new TreeNode<Character>(part.charAt(i),null,null,
null));
}else {
//如果不是操作数和操作符，那肯定是括号，如果表达式正确，
//第⼀碰到的括号肯定是左括号
int right=findFitBracket(part, i);
String subPart=new String(part.substring(i+1, right));
list.add(CreateBinaryTree(subPart));
i=right;
}
}
/
/根据这个不含括号的链表结构构造⼆叉树
TreeNode<Character> cur=null;
for(int i=0;i<list.size();i++){
if((i).getData()) && (i).getLefChild()
==null){
<(i).(i-1));
<(i).(i+1));
<(i-1).(i));
<(i+1).(i));
if(cur==null)
(i);
else {
while(Data(),(i).getData())<0
&& Father()!=null)
Father();
Father()==null &&
Data(),
<(i).getData())<0){
<(i).setLefChild(cur);
cur.(i));
}
else {
if(Data(),
<(i).getData())>0){
cur.(i));
<(i).setFather(cur);
}
}
}
(i);
}
}
Father()!=null)
Father();
return cur;
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论