二叉树的建立及其基本操作

  • 更新时间:
  • 9252人关注
  • 点击下载

这是一个不错的二叉树类学习资源,由焦金文提供,主要知识点是关于二叉树、二叉树建立、二叉树基本操作、二叉树的内容,已被834人关注,同类资源中评分为9.3分。

精选笔记:JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

23小时33分钟前回答

本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法。分享给大家供大家参考,具体如下:

javascript数据结构与算法--二叉树遍历(先序)

先序遍历先访问根节点, 然后以同样方式访问左子树和右子树

JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

代码如下:

/*
 *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中
 *
 *
 * */
/*用来生成一个节点*/
function Node(data, left, right) {
  this.data = data;//节点存储的数据
  this.left = left;
  this.right = right;
  this.show = show;
}
function show() {
  return this.data;
}
/*用来生成一个二叉树*/
function BST() {
  this.root = null;
  this.insert = insert;
}
/*将数据插入二叉树
 (1)设根节点为当前节点。
 (2)如果待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点;反
 之,执行第4步。
 (3)如果当前节点的左节点为null,就将新的节点插入这个位置,退出循环;反之,继续
 执行下一次循环。
 (4)设新的当前节点为原节点的右节点。
 (5)如果当前节点的右节点为null,就将新的节点插入这个位置,退出循环;反之,继续
 执行下一次循环。
 * */
function insert(data) {
  var n = new Node(data, null, null);
  if (this.root == null) {
    this.root = n;
  }
  else {
    var current = this.root;
    var parent;
    while (true) {
      parent = current;
      if (data < current.data) {
        current = current.left;//待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点
        if (current == null) {//如果当前节点的左节点为null,就将新的节点插入这个位置,退出循环;反之,继续执行下一次while循环。
          parent.left = n;
          break;
        }
      }
      else {
        current = current.right;//待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点
        if (current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}
/*先序遍历
 *用递归的方法
 */
function preOrder(node) {
  if (!(node == null)) {
    console.log(node.show() + " ");
    preOrder(node.left);
    preOrder(node.right);
  }
}
/* 测试代码 */
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log("先序遍历: ");
preOrder(nums.root);

运行结果:

JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

javascript数据结构与算法--二叉树遍历(中序)

中序遍历按照节点上的键值,以升序访问BST上的所有节点

JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

代码如下:

/*
 *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中
 *
 *
 * */
/*用来生成一个节点*/
function Node(data, left, right) {
  this.data = data;//节点存储的数据
  this.left = left;
  this.right = right;
  this.show = show;
}
function show() {
  return this.data;
}
/*用来生成一个二叉树*/
function BST() {
  this.root = null;
  this.insert = insert;
}
/*将数据插入二叉树
 (1)设根节点为当前节点。
 (2)如果待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点;反
 之,执行第4步。
 (3)如果当前节点的左节点为null,就将新的节点插入这个位置,退出循环;反之,继续
 执行下一次循环。
 (4)设新的当前节点为原节点的右节点。
 (5)如果当前节点的右节点为null,就将新的节点插入这个位置,退出循环;反之,继续
 执行下一次循环。
 * */
function insert(data) {
  var n = new Node(data, null, null);
  if (this.root == null) {
    this.root = n;
  }
  else {
    var current = this.root;
    var parent;
    while (true) {
      parent = current;
      if (data < current.data) {
        current = current.left;//待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点
        if (current == null) {//如果当前节点的左节点为null,就将新的节点插入这个位置,退出循环;反之,继续执行下一次while循环。
          parent.left = n;
          break;
        }
      }
      else {
        current = current.right;//待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点
        if (current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}
/*中序遍历
*用递归的方法
*/
function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.left);
    console.log(node.show() + " ");
    inOrder(node.right);
  }
}
/* 测试代码 */
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log("中序遍历: ");
inOrder(nums.root);

运行结果:

JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

javascript数据结构与算法--二叉树遍历(后序)

后序遍历先访问叶子节点,从左子树到右子树,再到根节点。

/*
 *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中
 *
 *
 * */
/*用来生成一个节点*/
function Node(data, left, right) {
  this.data = data;//节点存储的数据
  this.left = left;
  this.right = right;
  this.show = show;
}
function show() {
  return this.data;
}
/*用来生成一个二叉树*/
function BST() {
  this.root = null;
  this.insert = insert;
}
/*将数据插入二叉树
 (1)设根节点为当前节点。
 (2)如果待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点;反
 之,执行第4步。
 (3)如果当前节点的左节点为null,就将新的节点插入这个位置,退出循环;反之,继续
 执行下一次循环。
 (4)设新的当前节点为原节点的右节点。
 (5)如果当前节点的右节点为null,就将新的节点插入这个位置,退出循环;反之,继续
 执行下一次循环。
 * */
function insert(data) {
  var n = new Node(data, null, null);
  if (this.root == null) {
    this.root = n;
  }
  else {
    var current = this.root;
    var parent;
    while (true) {
      parent = current;
      if (data < current.data) {
        current = current.left;//待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点
        if (current == null) {//如果当前节点的左节点为null,就将新的节点插入这个位置,退出循环;反之,继续执行下一次while循环。
          parent.left = n;
          break;
        }
      }
      else {
        current = current.right;//待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点
        if (current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}
/*后序遍历
 *用递归的方法
 */
function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.left);
    postOrder(node.right);
    console.log(node.show() + " ");
  }
}
/* 测试代码 */
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log("后序遍历: ");
postOrder(nums.root);

运行结果:

JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

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

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

展开阅读

相关资源

  • 操作系统教程(第4版)

    操作系统教程(第4版)

    《操作系统教程(第四版)》是2008年高等教育出版社出版的图书,作者是孙钟秀、费翔林、骆斌。 操作系统是计算机系统的核心和灵魂,是计算机系统必不可少的组成部分,因而操作系统课程成为计算机相关专业的必修课,也是计算机应用从业人员必备的专业知识。本书在前三版的基础上进行全面修订,系统地介绍操作系统的经典内容和最新发展,选择当代具有代表性的主流操作系统Linux 和windows 2003作为实例贯穿全书。 本书共分八章,覆盖操作系统的基本概念

    大小:5.23 MB操作系统

    立即下载
  • 【Python标准库之字符串处理库、文件及目录操作、时间日期】知识点结构图

    大小:1.69 MBPython

    立即下载
  • 操作系统真象还原

    操作系统真象还原

    操作系统真象还原 共分16章,讲解了开发一个操作系统需要的技术和知识,主要内容有:操作系统基础、部署工作环境、编写MBR主引导记录、完善MBR错误、保护模式入门、保护模式进阶和向内

    大小:351.9 MB操作系统

    立即下载
  • 微机操作维护基本技术

    微机操作维护基本技术 作者:李荣先编 广东科技 出版时间:1994.5 丛编项:职业技术培训丛书

    大小:1.90MB微机

    立即下载
  • 现代操作系统(第3版)

    现代操作系统(第3版)

    《现代操作系统》内容为:Tanenbaum教授作为三个操作系统的设计师或联合设计师,具有长期设计开发操作系统的经验,从而把其对理论的深入理解和具体实践融入书中,使《现代操作系统(英文版第3版)》成为操作系统领域的经典之作。在《现代操作系统(英文版第3版)》第3版中,作者深入讨论了许多主题,包括:进程,线程,存储管理,文件系统,I/O死锁,接口设计,多媒体,性能权衡。以及有关操作系统设计的最新趋势。书中不仅涵盖了现代操作系统的

    大小:18.2 MB操作系统

    立即下载

学习笔记

18小时49分钟前回答

C语言实现二叉树遍历的迭代算法

本文实例讲述了C语言实现二叉树遍历的迭代算法,是数据结构算法中非常经典的一类算法。分享给大家供大家参考。 具体实现方法如下: 二叉树中序遍历的迭代算法: #include iostream#include stackusing namespace std;struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* left; Node* right; }; Node* construct() { Node* node6 = new Node(16); Node* node5 = new Node(12); Node* node4 = new Node(8); Node* node3 = new Node(4); Node* node2 = new Node(14, node5, node6); Node* node1 = new Node(6, node3, node4); Node* node0 = new Node(10, node1, node2); return node0; }//递归算法void inorder(Node *root){ if (root == NULL) return; inorder(root-left); cout root-item " "; inorder(root-right);}v……

23小时52分钟前回答

Java二叉树递归算法,初学者入门收藏

Java算法:递归二叉树算法 二叉树的本质是递归结构,很多可以使用递归分治法完成的,推广了遍历算法。 在只给定指向树的一个指针的前提下,经常需要找到树的各种结构参数的值。 例1:树参数的计算,树的结点树和高度 private static int count(Node h){       if(h == null){           reutrn 0;       }       return count(h.l) + count(h.r) + 1;   }   int count(){       return count(root);   }   private static int height(Node h){       if(h == null){           return -1;       }       int u = height(h.l), v = height(h.r);       if(u  v){           return u + 1;       }else{    ……