javascript实现二叉树遍历的代码

网络编程 2024/9/1 佚名

3 2 1

前言：

紧接着上篇二叉树的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;
}
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) {
        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);
  }
}

// 给BST类添加先序遍历的成员方法
function BST() {
  this.root = null;
  this.insert = insert;
  this.preOrder = preOrder;
}

preOrder函数是递归实现的，应该说二叉树的遍历都是递归实现的。可能有些人会因为先序遍历的特征：“先打印父节点，然后是左子节点（左子树），然后再打印右子节点（子树）” 而陷入一个错误的想法，这想法是什么请看下图：

注意红框部分，父节点是10，左子节点是3，右子节点是18，因为上面的结论，可能会错误地认为打印的顺序是10 → 3 → 18，然而事实并非如此[捂脸]，真是的顺序是：先打印10，然后是打印左子树，打印完左子树的全部节点后，才开始打印以10位父节点的右子树：

这个时候，你的脑海就该这样想：

然后是这样想：

如此类推打印完以10为父节点的左子树，然后也是以这样的方式打印以10为父节点的右子树，按着这种拆分代替的思想来理解会更好明白二叉树的遍历。

然后最终，先序遍历改二叉树的顺序是：

按图的输出顺序是：10 -> 3 -> 2 -> 4 -> 9 -> 8 -> 9 -> 18 -> 13 -> 21

最后来实践一下，先序遍历：

var bst = new BST();
var nums = [10, 3, 18, 2, 4, 13, 21, 9, 8, 9];
for(var i = 0; i < nums.length; i++) {
  bst.insert(nums[i]);
}
bst.preOrder(bst.root);

这里强调一下，输出顺序和插入顺序有关的，因为你插入顺序不同生成的二叉树也是不同的。有疑问的可以去二叉树的javascript实现细看一下，有比较明白的说明了二叉树，也可以实验一下：

中序遍历

看完先序遍历，已经可以类推到很多和中序、后序遍历相关的知识点。中序遍历的特征是：先打印左子树（左子节点），接着打印父节点，最后打印右子树（右子节点）。

function inOrder(node) {
  if (!(node == null)) {
   inOrder(node.left);
   console.log(node.show() + " ");
   inOrder(node.right);
  }
}

// 给BST类添加该成员方法
function BST() {
  this.root = null;
  this.insert = insert;
  this.preOrder = preOrder;
  this.inOrder = inOrder;
}

中序遍历的打印顺序：

按上图的输出顺序是：2 -> 3 -> 4 -> 8 -> 9 -> 9 -> 10 -> 13 -> 18 -> 21

接着是，实践一下中序遍历：

后序遍历

function postOrder(node) {
  if (!(node == null)) {
   postOrder(node.left);
   postOrder(node.right);
   console.log(node.show() + " ");
  }
}

// 给BST类添加该成员方法
function BST() {
  this.root = null;
  this.insert = insert;
  this.preOrder = preOrder;
  this.inOrder = inOrder;
  this.postOrder = postOrder;
}

后序遍历的打印顺序

按上图的输出顺序是：2 -> 8 -> 9 -> 9 -> 4 -> 3 -> 13 -> 21 -> 18 -> 10

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

javascript实现二叉树遍历,javascript二叉树遍历,JS,二叉树遍历

标签：

javascript实现二叉树遍历,javascript二叉树遍历,JS,二叉树遍历

免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com

评论“javascript实现二叉树遍历的代码”

javascript实现二叉树遍历的代码

暂无“javascript实现二叉树遍历的代码”评论...

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒经典版》的玩家都可以获得奖励。

更新动态

20240901

javascript实现二叉树遍历的代码

javascript实现二叉树遍历,javascript二叉树遍历,JS,二叉树遍历

微信小程序开发之toast等弹框提示使用教程

微信小程序tabbar不显示解决办法

评论“javascript实现二叉树遍历的代码”

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

更新动态

友情链接