直击算法:Dart 中二叉树的构建与遍历

时间:2021-7-3 作者:qvyue

前言

二叉树最基础且最重要的数据结构之一,其他非常多数据结构都是基于二叉树的基础演变而来。 本文主要实现使用 Dart 语言构建和遍历二叉树。

我是 一名Android开发工程师,下面代码中我添加了非常详细的注释,可以收藏慢慢看哦

定义

///二叉树实体定义
class TreeNode {
  //值
  var value;

  //左子节点
  TreeNode leftNode;

  //右子节点
  TreeNode rightNode;

  //构造函数
  TreeNode(this.value, [this.leftNode, this.rightNode]);
}

[图片上传失败…(image-6b17fe-1625057062237)]

构建

第一种构建方法

//第一种构建方法
TreeNode treeNode1 = TreeNode(10);
treeNode1.leftNode = TreeNode(9);
TreeNode subNode = TreeNode(20);
treeNode1.rightNode = subNode;
subNode.leftNode = TreeNode(15);
subNode.rightNode = TreeNode(35);

第二种构建方法

//第二种构建方法
TreeNode treeNode2 = TreeNode(10)
  ..leftNode = TreeNode(9)
  ..rightNode = TreeNode(20)
  ..rightNode.leftNode = TreeNode(15)
  ..rightNode.rightNode = TreeNode(35);

第三种构建方法

//第三种构建方法
TreeNode treeNode3 =
  TreeNode(10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(35)));

遍历

前序遍历

口诀:根>左>右

///先序遍历(根>左>右)
void preTraversingTree(TreeNode treeNode, List list) {
  if (treeNode != null) {
    //获取根节点值
    var value = treeNode.value;
    //添加到数组中
    list.add(value);
    //遍历左子节点
    preTraversingTree(treeNode.leftNode, list);
    //遍历右子节点
    preTraversingTree(treeNode.rightNode, list);
  }
}
// 遍历结果
List result = [];
/// 单元测试
test('先序遍历(根>左>右)', () {
  result.clear();
  preTraversingTree(treeNode2, result);
  print('先序遍历(根>左>右) result:${result.toString()}');
  expect(result, equals([10, 9, 20, 15, 35]));
});
结果:[10, 9, 20, 15, 35]

中序遍历

口诀:左>根>右

直击算法:Dart 中二叉树的构建与遍历
///中序遍历(左>根>右)
void inTraversingTree(TreeNode treeNode, List list) {
  if (treeNode != null) {
    //遍历左子节点
    inTraversingTree(treeNode.leftNode, list);
    //获取根节点值
    var value = treeNode.value;
    //添加到数组中
    list.add(value);
    //遍历左子节点
    inTraversingTree(treeNode.rightNode, list);
  }
}
/// 单元测试
test('中序遍历(左>根>右)', () {
  result.clear();
  inTraversingTree(treeNode2, result);
  print('中序遍历(左>根>右) result:${result.toString()}');
  expect(result, equals([9, 10, 15, 20, 35]));
});
结果:[9, 10, 15, 20, 35]

后续遍历

口诀:左>右>根

///后序遍历(左>右>根)
void rearTraversingTree(TreeNode treeNode, List list) {
  if (treeNode != null) {
    //先遍历左子节点
    rearTraversingTree(treeNode.leftNode, list);
    //后遍历右子节点
    rearTraversingTree(treeNode.rightNode, list);
    //获取根节点值
    var value = treeNode.value;
    //添加到数组中
    list.add(value);
  }
}
/// 单元测试
test('后序遍历(左>右>根)', () {
  result.clear();
  rearTraversingTree(treeNode2, result);
  print('后序遍历(左>右>根) result:${result.toString()}');
  expect(result, equals([9, 15, 35, 20, 10]));
});
结果:[9, 15, 35, 20, 10]

层序遍历

自上而下,从左到右(与先序遍历类似,注重层级结构展示)

///层序遍历(自上而下,从左至右)
List> leveTraversingTree(TreeNode treeNode) {
  var result = >[[]];
  if (treeNode != null) {
    _dfs(treeNode, result, 0);
  }
  return result;
}

///dfs 与先序遍历类似
void _dfs(TreeNode treeNode, List> list, int level) {
  if (treeNode != null) {
    // 在 level 与 list.length 相等时添加一个新的空 list 到 list 里
    if (level == list.length) {
      list.add([]);
    }
    // 添加到列表里
    list[level].add(treeNode.value);
    // 遍历左边
    _dfs(treeNode.leftNode, list, level + 1);
    // 遍历右边边
    _dfs(treeNode.rightNode, list, level + 1);
  }
}
/// 单元测试
test('层序遍历', () {
  var result = leveTraversingTree(treeNode3);
  print('层序遍历 result:${result.toString()}');
  expect(
    result,
    equals([
      [10],
      [9, 20],
      [15, 35]
    ]));
});
结果:[[10], [9, 20], [15, 35]]

总结

本文通过 Dart 实现简单的二叉树构建与遍历,从细节可以看出 Dart 是非常优秀的现代型语言,比如可选位置参数 [] 的使用、.. 连级操作的使用、还有本文未展示但之后会经常使用的 {} 可选参数,对开发者而言都是非常简洁且友好的。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。