数据结构实验——表达式二叉树（以递归方式建立表达式的二叉树状结构，再分别输出前序、中序及后序遍历结果，并计算表达式的结果。）

绝地灬酷狼 2022-12-22 00:45 66阅读 0赞

## 实验要求 ##

![在这里插入图片描述][20201117085620344.png_pic_center]

## 实验实现语言 ##

Javascript + HTML + CSS

## index.html ##

<!DOCTYPE html>
    <html lang="en">
    
    <head>
        <meta charset="UTF-8">
        <meta name="viewport" content="width=device-width, initial-scale=1.0">
        <title>表达式二叉树</title>
        <link rel="stylesheet" href="index.css">
    </head>
    
    <body>
        <div class="input-box">
            <input type="text">
            <button>生成</button>
        </div>
    
        <div id="display">
    
        </div>
    
        <div class="layer" id="pre-order-traversal"></div>
        <div class="layer" id="middle-order-traversal"></div>
        <div class="layer" id="post-order-traversal"></div>
    
        <div id="answer" class="layer"></div>
    
        <script src="index.js"></script>
    </body>
    
    </html>

## index.css ##

* {
        
        margin: 0;
        padding: 0;
    }
    
    .input-box {
        
        margin-top: 20px;
        text-align: center;
    }
    
    #display {
        
        margin-top: 30px;
        width: 100%;
        text-align: center;
        font-weight: bolder;
        box-sizing: border-box;
    }
    
    #display::after {
        
        content: '';
        display: block;
        clear: both;
    }
    
    .node {
        
        height: 40px;
        line-height: 40px;
        float: left;
        box-sizing: border-box;
        border: 1px solid rgba(99, 99, 99, .7);
    }
    
    .level0 {
        
        width: 100%;
        background-color: green;
        font-size: 28px;
    }
    
    .level1 {
        
        width: 50%;
        background-color: pink;
        font-size: 26px;
    }
    
    .level2 {
        
        width: 25%;
        background-color: red;
        font-size: 24px;
    }
    
    .level3 {
        
        width: 12.5%;
        background-color: blue;
        font-size: 22px;
    }
    
    .level4 {
        
        width: 6.25%;
        background-color: aqua;
        font-size: 20px;
    }
    
    .level5 {
        
        width: 3.125%;
        background-color: yellow;
        font-size: 18px;
    }
    
    .level6 {
        
        width: 1.5625%;
        background-color: rgb(241, 12, 230);
        font-size: 12px;
    }
    
    .layer {
        
        margin: 20px 0;
        width: 100%;
        text-align: center;
        height: 30px;
    }

## index.js ##

var treeArr = []; // 树形结构的 存储数组
    var levelNum = 0; // 树形结构含有多少层级
    var domArr; // dom 结构数组 用于方便生成 树形 dom结构
    
    // 三种遍历 得到的结果 存放于三个数组中
    var pre_order_traversal_arr = [];
    var middle_order_traversal_arr = [];
    var post_order_traversal_arr = [];
    
    var btn = document.getElementsByTagName('button')[0];
    var input = document.getElementsByTagName('input')[0];
    var display = document.getElementById('display');
    var pre_order_traversal = document.getElementById('pre-order-traversal');
    var middle_order_traversal = document.getElementById('middle-order-traversal');
    var post_order_traversal = document.getElementById('post-order-traversal');
    var answer = document.getElementById('answer');
    
    // 初始化domArr
    function initDomArr(node) {
        
        domArr = new Array(7);
        for (var i = 0; i < 7; i++) {
        
            domArr[i] = new Array(2 ** i);
            var len = domArr[i].length;
            for (var j = 0; j < len; j++) {
        
                domArr[i][j] = '<div class="node level' + i + '"></div>';
            }
        }
    }
    
    //  节点构造函数
    function Node(data, left, right, level, floorIndex) {
        
        this.data = data;
        this.left = left;
        this.right = right;
        this.level = level;
        this.floorIndex = floorIndex;
        // floorIndex 用于获知该节点位于 同一层级上的 第几个位置（从左往右）
    }
    
    // 递归 构造树形结构
    function buildTree(arr, x, y) {
        
        var c1 = -1,
            c2 = -1,
            flag = 0,
            u;
    
        // 如果只有一个节点，可以看出，这个节点必定是数字节点，那么左右置为空
        if (y - x == 1) {
        
            var temp = new Node(arr[x], null, null);
            treeArr.push(temp);
            return temp;
        }
    
        // 循环遍历数据数组 找出最后一次计算（逻辑上）的 运算符号
        for (var i = x; i < y; i++) {
        
            switch (arr[i]) {
        
                case '(':
                    flag++;
                    break;
                case ')':
                    flag--;
                    break;
                case '+':
                case '-':
                    if (!flag)
                        c1 = i;
                    break;
                case '*':
                case '/':
                    if (!flag)
                        c2 = i;
                    break;
                default:
                    break;
            }
        }
    
        // 如果最后一次运算符号不是加、减号  那么最后一次符号（可能）是 乘、除号
        if (c1 < 0) {
        
            c1 = c2;
        }
    
        // 当c1，c2都未改变时，说明为括号
        if (c1 < 0) {
        
            // 括号就左右往里递归
            return buildTree(arr, x + 1, y - 1);
        }
    
        var tempObj = new Node(arr[c1], null, null);
        treeArr.push(tempObj);
        tempObj.left = buildTree(arr, x, c1);
        tempObj.right = buildTree(arr, c1 + 1, y);
    
        // 如果不 return 会报错 因为函数没有返回值就赋值给 对象是 不行的
        return tempObj;
    }
    
    // 递归 填充每个节点所在的层级  以及每个节点在同一层级的 第几个位置
    function initLevel(node, num, index) {
        
    
        // 递归出口
        if (!node) {
        
            return;
        }
    
        domArr[num][index - 1] = '<div class="node level' + num + '">' + node.data + '</div>';
        node.floorIndex = index;
        node.level = num;
        initLevel(node.left, num + 1, index * 2 - 1);
        initLevel(node.right, num + 1, index * 2);
    }
    
    // 递归 前序遍历
    function preOrderTraversal(node) {
        
        if (node) {
        
            pre_order_traversal_arr.push(node.data);
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        } else {
        
            return;
        }
    }
    
    // 递归 中序遍历
    function middleOrderTraversal(node) {
        
        if (node) {
        
            middleOrderTraversal(node.left);
            middle_order_traversal_arr.push(node.data);
            middleOrderTraversal(node.right);
        } else {
        
            return;
        }
    }
    
    // 递归 后序遍历
    function postOrderTraversal(node) {
        
        if (node) {
        
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            post_order_traversal_arr.push(node.data);
        }
    }
    
    // 生成前、中、后 序 遍历结果的 dom结构
    function traversalAnswer(arr, div, str) {
        
        div.innerHTML = '';
        arr.forEach(function(value) {
        
            str = str + " " + value;
        });
        div.innerHTML = str;
    }
    
    // 生成 dom 结构
    function createDom() {
        
        // 每个 节点 为其添加 level 属性 和 floorIndex 属性
        initLevel(treeArr[0], 0, 1);
        levelNum = 0;
        treeArr.forEach(function(value) {
        
            if (value.level > levelNum) {
        
                levelNum = value.level;
            }
        });
        // 计算 有多少层
        var str = '';
        for (var i = 0; i <= levelNum; i++) {
        
            var floorNodeNum = 2 ** i;
            for (var j = 0; j < floorNodeNum; j++) {
        
                str += domArr[i][j];
            }
        }
        display.innerHTML = str;
        traversalAnswer(pre_order_traversal_arr, pre_order_traversal, '前序遍历输出结果为： ');
        traversalAnswer(middle_order_traversal_arr, middle_order_traversal, '中序遍历输出结果为： ');
        traversalAnswer(post_order_traversal_arr, post_order_traversal, '后序遍历输出结果为： ');
        answer.innerHTML = '算数表达式的答案为 ： ' + getAnswer();
    }
    
    // 获取 表达式的计算结果
    // 思路 结合逆波兰表达式 和 栈的思想   
    function getAnswer() {
        
        // 栈思想 按位存放逆波兰表达式，遇到符号，进行计算，计算结果重新压入栈中
        var stack = [];
        post_order_traversal_arr.forEach(function(value) {
        
            if (typeof(value) == 'number') {
        
                stack.push(value);
            } else {
        
                var temp;
                switch (value) {
        
                    case '+':
                        temp = stack.pop() + stack.pop();
                        break;
                    case '-':
                        var num1 = stack.pop();
                        var num2 = stack.pop();
                        temp = num2 - num1;
                        break;
                    case '*':
                        temp = stack.pop() * stack.pop();
                        break;
                    case '/':
                        var num1 = stack.pop();
                        var num2 = stack.pop();
                        temp = num2 / num1;
                        break;
                    default:
                        break;
                }
                stack.push(temp);
            }
        });
        return stack.pop();
    }
    
    // 点击生成按钮 的操作
    btn.onclick = function() {
        
        initDomArr();
        var temp = input.value.split("");
        var arr = [];
        var t = '';
        temp.forEach(function(value) {
        
            if ((value >= '0' && value <= '9') || value == '.') {
        
                t += value;
            } else {
        
                if (t) {
        
                    arr.push(Number(t));
                    t = '';
                }
                arr.push(value);
    
            }
        });
        if (t) {
        
            arr.push(Number(t));
        }
    
        // 获取 输入框的数据 数组
    
        // 重置 treeArr
        treeArr = [];
        buildTree(arr, 0, arr.length); // 构建树形结构
    
        // 每次点击 重置遍历结果
        pre_order_traversal_arr = [];
        middle_order_traversal_arr = [];
        post_order_traversal_arr = [];
    
        preOrderTraversal(treeArr[0]);
        middleOrderTraversal(treeArr[0]);
        postOrderTraversal(treeArr[0]);
        createDom();
    }

[20201117085620344.png_pic_center]: /images/20221120/811115e0876c41f68d56b486a892cbb5.png

发表评论取消回复

表情：

评论列表（有 0 条评论，66人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构 - 树(二叉树的前序、中序、后序遍历)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

缺乏、安全感/ 2023年07月03日 03:30/ 0 赞/ 112 阅读

相关二叉树的前序、中序、后序遍历（非递归）

二叉树的前序、中序、后序遍历（非递归）非递归写法前序遍历（先序遍历）中序遍历后序遍历如需递归写法，可以参考：[h

- 日理万妓/ 2022年12月30日 08:27/ 0 赞/ 153 阅读

相关数据结构实验——表达式二叉树（以递归方式建立表达式的二叉树状结构，再分别输出前序、中序及后序遍历结果，并计算表达式的结果。）

实验要求 ![在这里插入图片描述][20201117085620344.png_pic_center] 实验实现语言 Javascript + HTML + CS

绝地灬酷狼/ 2022年12月22日 00:45/ 0 赞/ 67 阅读

相关二叉树遍历(递归实现前序/中序/后序遍历)

1. 准备工作我们先定义一棵普通的二叉树，如下图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10

你的名字/ 2022年10月07日 08:56/ 0 赞/ 158 阅读

相关二叉树遍历，前序，中序，后序，递归版本

Java实现。 package bigo; class Node{ int data; Node left;

超、凢脫俗/ 2022年08月20日 14:25/ 0 赞/ 167 阅读

相关二叉树的非递归遍历（前序、中序、后序）

先序遍历 void PreOrder_Nonrecursive1(BiTree T) //先序遍历的非递归 { if(!T)

悠悠/ 2022年08月02日 10:47/ 0 赞/ 207 阅读

相关【数据结构】二叉树前中后序遍历、层序遍历（递归实现）

这里使用C++模板、前序遍历方式建立二叉树主要介绍：递归实现二叉树建立，前序、中序、后续、层序遍历，求二叉树深度及节点个数本文使用序列：array\[10\] =

ゝ一世哀愁。/ 2022年06月13日 10:39/ 0 赞/ 112 阅读

相关数据结构 — 实现二叉树的前序，中序，后序遍历(非递归)

实现二叉树的前序，中序，后序遍历 ————————————————————————————— 相信大家对二叉树已经很了解了，

痛定思痛。/ 2022年06月11日 00:55/ 0 赞/ 99 阅读

相关二叉树的遍历前序中序后序分别实现递归和非递归遍历方式

开始复习下数据结构，学习二叉树将二叉树的遍历方式实现了一遍，非递归相对有点难度，通过收集资料最终完成了二叉树的所有遍历方式，做个记录以备后用。废话不说了，贴代码！ 1. Bi

水深无声/ 2022年05月14日 04:48/ 0 赞/ 146 阅读

相关数据结构—二叉树的前中后序非递归遍历及层序遍历

数据结构—二叉树的前中后序非递归遍历及层序遍历之前已经写过一篇关于二叉树的文章,当时是用C语言实现了二叉树的建立以及前中后序递归遍历. 递归有一个好处就是:实现代码

约定不等于承诺〃/ 2022年04月06日 06:13/ 0 赞/ 129 阅读