您的位置:永利集团登录网址 > 计算机教学 > 后序式运算代码实例,运算实例

后序式运算代码实例,运算实例

2019-11-09 02:43

后序式运算代码实例,运算实例

JavaScript实现二叉树的先序、中序及后序遍历方法详解,javascript二叉树

本文实例讲述了JavaScript实现二叉树的先序、中序及后序遍历方法。分享给大家供大家参考,具体如下:

之前学数据结构的时候,学了二叉树的先序、中序、后序遍历的方法,并用C语言实现了,下文是用js实现二叉树的3种遍历,并以动画的形式展现出遍历的过程。

整个遍历过程还是采用递归的思想,原理很粗暴也很简单

先序遍历的函数:

function preOrder(node){
  if(!(node==null)){
    divList.push(node);
    preOrder(node.firstElementChild);
    preOrder(node.lastElementChild);
  }
}

中序遍历的函数:

function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.firstElementChild);
    divList.push(node);
    inOrder(node.lastElementChild);
  }
}

后序遍历的函数:

function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.firstElementChild);
    postOrder(node.lastElementChild);
    divList.push(node);
  }
}

颜色变化函数:

function changeColor(){
  var i=0;
  divList[i].style.backgroundColor = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i<divList.length){
      divList[i-1].style.backgroundColor="#fff";
      divList[i].style.backgroundColor="blue";
    }
    else{
      divList[divList.length-1].style.backgroundColor="#fff";
    }
  },500)
}

核心代码如上,本来想写深度优先遍历和广度优先遍历。后来发现二叉树深度优先遍历和先序遍历相同。改日总结一下树的BFS和DFS。

全部代码如下:

<!DOCTYPE html>
<html>
<head lang="en">
  <meta charset="UTF-8">
  <title></title>
  <style>
    .root{
      display: flex;
      padding: 20px;
      width: 1000px;
      height: 300px;border: 1px solid #000000;
      margin: 100px auto;
      margin-bottom: 10px;
      justify-content: space-between;
    }
    .child_1{
      display: flex;
      padding: 20px;
      width: 450px;
      height: 260px;border: 1px solid red;
      justify-content: space-between;
    }
    .child_2{
      display: flex;
      padding: 20px;
      width: 170px;
      height: 220px;border: 1px solid green;
      justify-content: space-between;
    }
    .child_3{
      display: flex;
      padding: 20px;
      width: 35px;
      height: 180px;border: 1px solid blue;
      justify-content: space-between;
    }
    input{
      margin-left: 100px;
      width: 60px;
      height: 40px;
      font:20px italic;
    }
  </style>
</head>
<body>
<div class="root">
  <div class="child_1">
    <div class="child_2">
      <div class="child_3"></div>
      <div class="child_3"></div>
    </div>
    <div class="child_2">
      <div class="child_3"></div>
      <div class="child_3"></div>
    </div>
  </div>
  <div class="child_1">
    <div class="child_2">
      <div class="child_3"></div>
      <div class="child_3"></div>
    </div>
    <div class="child_2">
      <div class="child_3"></div>
      <div class="child_3"></div>
    </div>
  </div>
</div>
<input type="button" value="先序">
<input type="button" value="中序">
<input type="button" value="后序">
<script type="text/javascript" src="遍历.js"></script>
</body>
</html>

js:

/**
 * Created by hp on 2016/12/22.
 */
var btn = document.getElementsByTagName('input'),
  preBtn = btn[0],
  inBtn = btn[1],
  postBtn = btn[2],
  treeRoot = document.getElementsByClassName('root')[0],
  divList = [],
  timer = null;
window.onload=function(){
  preBtn.onclick = function () {
    reset();
    preOrder(treeRoot);
    changeColor();
  }
  inBtn.onclick = function () {
    reset();
    inOrder(treeRoot);
    changeColor();
  }
  postBtn.onclick = function () {
    reset();
    postOrder(treeRoot);
    changeColor();
  }
}
/*先序遍历*/
function preOrder(node){
  if(!(node==null)){
    divList.push(node);
    preOrder(node.firstElementChild);
    preOrder(node.lastElementChild);
  }
}
/*中序遍历*/
function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.firstElementChild);
    divList.push(node);
    inOrder(node.lastElementChild);
  }
}
/*后序遍历*/
function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.firstElementChild);
    postOrder(node.lastElementChild);
    divList.push(node);
  }
}
/*颜色变化函数*/
function changeColor(){
  var i=0;
  divList[i].style.backgroundColor = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i<divList.length){
      divList[i-1].style.backgroundColor="#fff";
      divList[i].style.backgroundColor="blue";
    }
    else{
      divList[divList.length-1].style.backgroundColor="#fff";
    }
  },500)
}
function reset(){
  divList=[];
  clearInterval(timer);
  var divs=document.getElementsByTagName("div");
  for(var i=0;i<divs.length;i++){
    divs[i].style.backgroundColor="#fff";
  }
}

由此可见,二叉树的遍历思想是一样的。之前一直把JS看做是写各种特效的语言,现在向来是too naive了。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

本文实例讲述了JavaScript实现二叉树的先序、中序及后序遍历方法。分...

1.中序表达式

中序表达式对我们而言是很直观的(我们平时接触的就是这个),但计算机处理起来比较麻烦(括号、优先级之类的),如2*3/(2-1)+3*(4-1)。前序和后序表达式中没有括号,而且在计算中只需单向扫描,不需要考虑运算符的优先级。

C代码(理论可参考中序式转后序)

#define _CRT_SECURE_NO_WARNINGS
#include
#include

void jisuan(char *);
float cal(float, float, char);
void main()
{
    char input[80];
    printf("中序式:");
    scanf("%s", input);
    jisuan(input);
    system("pause");
}

void jisuan(char *arr)
{
    float stack[80] = { 0.0 };
    int top = 0;
    int i = 0;
    char op;
    char temp[2];
    while (1)
    {
        op = arr[i];
        switch (op)
        {
        case '':
            printf("%fn", stack[top]);
            return;
        case '+':
        case '-':
        case '*':
        case '/':

            stack[top - 1] = cal(stack[top],stack[top - 1],op);
            top--;
            break;
        default:
            if (top < sizeof(stack) / sizeof(float))
            {
                temp[0] = op;
                top++;
                stack[top] = atof(temp);  //字符转float
            }
            break;
        }
        i++;
    }
}

float cal(float A, float B, char op)
{
    if (op == '+')
    {
        return A + B;
    }
    if (op == '-')
    {
        return A - B;
    }
    if (op == '*')
    {
        return A*B;
    }
    if (op == '/')
    {
        return A / B;
    }
}

C代码(理论可参考中序式转后序) #define _CRT_SECURE_NO_WARNINGS#include #include void jisuan(char *);float cal(float, floa...

2.前序表达式

前序表达式就是前缀表达式,不含括号的算术表达式,而且它是将运算符写在前面,操作数写在后面的表达式,也称为“波兰式”。

2.1优点

前序表达式是一种十分有用的表达式,它将中序表达式转换为可以依靠简单的操作就能得到运算结果的表达式。例如,(a+b)*(c+d)转换为*,+,a,b,+,c,d。它的优势在于只用两种简单的操作,入栈和出栈就可以解决任何中序表达式的运算。其运算方式为:如果当前字符(或字符串)为数字或变量,则压入栈内;如果是运算符,则将栈顶两个元素弹出栈外并作相应运算,再将结果压入栈内。当前序表达式扫描结束时,栈里的就是中序表达式运算的最终结果。

2.2如何求值

对于一个前序表达式的求值而言,首先要从右至左扫描表达式,从右边第一个字符开始判断,如果当前字符是数字则一直到数字串的末尾再记录下来,如果是运算符,则将右边离得最近的两个“数字串”作相应的运算,以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时,最后运算的值也就是表达式的值。例如,前序表达式“- 1 + 2 3“的求值,扫描到3时,记录下这个数字串,扫描到2时,记录下这个数字串,当扫描到+时,将+右移做相邻两数字串的运算符,记为2+3,结果为5,记录下这个新数字串,并继续向左扫描,扫描到1时,记录下这个数字串,扫描到-时,将-右移做相邻两数字串的运算符,记为1-5,结果为-4,所以表达式的值为-4。

2.3中序转前序例子

中序表达式 前序表达式
2*3/(2-1)+3*(4-1) +/*23-21*3-41

2.4中序转前序算法

1、反转输入字符串,如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”,
2、从字符串中取出下一个字符
  2.1.如果是操作数,则直接输出
  2.2.如果是“)”,压入栈中
  2.3.如果是运算符但不是“(”,“)”,则不断循环进行以下处理
    2.3.1.如果栈为空,则此运算符进栈,结束此步骤
    2.3.2.如果栈顶是“)”,则此运算符进栈,结束此步骤
    2.3.2.如果此运算符与栈顶优先级相同或者更高,此运算符进栈,结束此步骤
    2.3.4.否则,运算符连续出栈输出,直到满足上述三个条件之一,然后此运算符进栈
  2.4、如果是“(”,则运算符连续出栈输出,直到遇见“)”为止,将“)”出栈且丢弃之
3、如果还有更多的字符串,则转到第2步
4、不在有未处理的字符串了,输出栈中剩余元素
5、再次反转字符串得到最终结果

代码如下:

public class InfixToPrefix {
    public static void main(String[] args) {
        Stack<String> reverseStack = new Stack<String>();
        Stack<String> operatorStack = new Stack<String>();
        Stack<String> resultStack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String str = StdIn.readString();
            reverseStack.push(str);
        }
        while (!reverseStack.isEmpty()) {
            String str = reverseStack.pop();
            if (str.equals(")"))
                operatorStack.push(str);
            else if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
                boolean isEmpty;
                boolean isRightParen;
                boolean isHigherOperator;
                int i = 0;
                do {
                    if(i!=0){
                        resultStack.push(operatorStack.pop());
                    }
                    i++;
                    isEmpty = operatorStack.isEmpty();
                    isRightParen = false;
                    isHigherOperator = false;
                    if (!isEmpty) {
                        String stackTop = operatorStack.peek();
                        isRightParen = operatorStack.peek().equals(")");
                        if (stackTop.equals("+") || stackTop.equals("-")) {
                            isHigherOperator = true;
                        } else if ((stackTop.equals("*") || stackTop.equals("/"))
                                && (str.equals("*") || str.equals("/"))) {
                            isHigherOperator = true;
                        }
                    }
                    if(isEmpty||isRightParen||isHigherOperator){
                        operatorStack.push(str);
                        break;
                    }
                } while (!(isEmpty || isRightParen || isHigherOperator));
            }else if(str.equals("(")){
                String pop = operatorStack.pop();
                while(!pop.equals(")")){
                    resultStack.push(pop);
                    pop = operatorStack.pop();
                }
            }else{
                resultStack.push(str);
            }
        }
        for(String str:operatorStack){
            resultStack.push(str);
        }

        for(String str:resultStack){
            System.out.print(str);
        }
    }
}

注:此段代码所用的Stack数据结构来自算法(第四版)

3.后序表达式

后序表达式与前序表达式扫描方式正好相反

中序表达式 后序表达式
2*3/(2-1)+3*(4-1) 23*21-/341-*+

3.1中序转后序算法

1、当输入的是操作数时候,直接输出
2、当输入开括号时候,把它压栈
3、当输入的是闭括号时候,先判断栈是否为空,若为空,则发生错误并进行相关处理。若非空,把栈中元素依次出栈输出,直到遇到第一个开括号,若没有遇到开括号,也发生错误,进行相关处理
4、当输入是运算符op(+、- 、×、/)时候
a)循环,当(栈非空and栈顶不是开括号and栈顶运算符的优先级不低于输入的运算符的优先级)时,反复操作:将栈顶元素出栈输出
b)把输入的运算符op压栈
5、当中序表达式的符号序列全部读入后,若栈内仍有元素,把他们依次出栈输出。若弹出的元素遇到空括号,则说明不匹配,发生错误,并进行相关处理

代码如下:

public class InfixToPostfix {
    public static void main(String[] args) {
        Stack<String> operatorStack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String str = StdIn.readString();
            if (str.equals("("))
                operatorStack.push(str);
            else if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
                boolean isEmpty;
                boolean isLeftParen;
                boolean isLowerOperator;
                isEmpty = operatorStack.isEmpty();
                isLeftParen = false;
                isLowerOperator = false;
                if (!isEmpty) {
                    String stackTop = operatorStack.peek();
                    isLeftParen = operatorStack.peek().equals("(");
                    if ((stackTop.equals("+") || stackTop.equals("-")) && (str.equals("*") || str.equals("/"))) {
                        isLowerOperator = true;
                    }
                }
                if (!(isEmpty || isLeftParen || isLowerOperator)) {
                    for (int i = 0; i < operatorStack.size(); i++) {
                        StdOut.print(operatorStack.pop());
                    }
                }
                operatorStack.push(str);
            } else if (str.equals(")")) {
                String pop = operatorStack.pop();
                while (!pop.equals("(")) {
                    StdOut.print(pop);
                    pop = operatorStack.pop();
                }
            } else {
                StdOut.print(str);
            }
        }
        for (String str : operatorStack) {
            StdOut.print(str);
        }

    }
}

另外欢迎关注我的:
Github
微博
掘金
微信公众号

图片 1

蛋妞码农

本文由永利集团登录网址发布于计算机教学,转载请注明出处:后序式运算代码实例,运算实例

关键词:

  • 上一篇:没有了
  • 下一篇:没有了