Construction and traversal of binary tree in Dart

This is the second day of my participation in Gwen Challenge

preface

Binary trees are one of the most basic and important data structures, and many other data structures have evolved from the basis of binary trees. This paper mainly uses Dart language to construct and traverse binary trees.

I am Zero. I have added a very detailed comment to the code below, which can be saved and read slowly

define

///Binary tree entity definition
class TreeNode {
  / / value
  var value;

  // Left child node
  TreeNode leftNode;

  // Right child node
  TreeNode rightNode;
  
  // constructor
  TreeNode(this.value, [this.leftNode, this.rightNode]);
}
Copy the code

build

The first build method

// The first build method
TreeNode treeNode1 = TreeNode(10);
treeNode1.leftNode = TreeNode(9);
TreeNode subNode = TreeNode(20);
treeNode1.rightNode = subNode;
subNode.leftNode = TreeNode(15);
subNode.rightNode = TreeNode(35);
Copy the code

Second build method

// The second build method
TreeNode treeNode2 = TreeNode(10)
  ..leftNode = TreeNode(9)
  ..rightNode = TreeNode(20)
  ..rightNode.leftNode = TreeNode(15)
  ..rightNode.rightNode = TreeNode(35);
Copy the code

Third build method

// The third build method
TreeNode treeNode3 =
  TreeNode(10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(35)));
Copy the code

traverse

The former sequence traversal

Formula: root > left > right

///Sequential traversal (root > left > Right)
void preTraversingTree(TreeNode treeNode, List list) {
  if(treeNode ! =null) {
    // Get the root node value
    var value = treeNode.value;
    // Add to array
    list.add(value);
    // Iterate over the left child node
    preTraversingTree(treeNode.leftNode, list);
    // Iterate over the right child nodepreTraversingTree(treeNode.rightNode, list); }}Copy the code

// Iterate over the result
List result = [];
/// Unit testing
test('Sequential traversal (root > left > Right)', () {
  result.clear();
  preTraversingTree(treeNode2, result);
  print('(root > left > right) result:${result.toString()}');
  expect(result, equals([10.9.20.15.35])); }); Results: [10.9.20.15.35]
Copy the code

In the sequence traversal

Formula: left > root > right

///Middle order traversal (left > root > right)
void inTraversingTree(TreeNode treeNode, List list) {
  if(treeNode ! =null) {
    // Iterate over the left child node
    inTraversingTree(treeNode.leftNode, list);
    // Get the root node value
    var value = treeNode.value;
    // Add to array
    list.add(value);
    // Iterate over the left child nodeinTraversingTree(treeNode.rightNode, list); }}Copy the code

/// Unit testing
test('Middle order traversal (left > root > Right)', () {
  result.clear();
  inTraversingTree(treeNode2, result);
  print('(left > root > right)${result.toString()}');
  expect(result, equals([9.10.15.20.35])); }); Results: [9.10.15.20.35]
Copy the code

Subsequent traversal

Formula: left > right > root

///Post-order traversal (left > right > root)
void rearTraversingTree(TreeNode treeNode, List list) {
  if(treeNode ! =null) {
    // Iterate through the left child node
    rearTraversingTree(treeNode.leftNode, list);
    // walk through the right child node
    rearTraversingTree(treeNode.rightNode, list);
    // Get the root node value
    var value = treeNode.value;
    // Add to arraylist.add(value); }}Copy the code

/// Unit testing
test('Post-order traversal (left > Right > root)', () {
  result.clear();
  rearTraversingTree(treeNode2, result);
  print(Result: (left > right > root)${result.toString()}');
  expect(result, equals([9.15.35.20.10])); }); Results: [9.15.35.20.10]
Copy the code

Sequence traversal

Top down, left to right (similar to sequential traversal, with emphasis on hierarchical presentation)

///Sequence traversal (top down, left to right)
List<List<int>> leveTraversingTree(TreeNode treeNode) {
  var result = <List<int> > [[]].if(treeNode ! =null) {
    _dfs(treeNode, result, 0);
  }
  return result;
}

///DFS is similar to sequential traversal
void _dfs(TreeNode treeNode, List<List<int>> list, int level) {
  if(treeNode ! =null) {
    // Add a new empty list to list when level equals list.length
    if (level == list.length) {
      list.add([]);
    }
    // Add to the list
    list[level].add(treeNode.value);
    // Iterate over the left side
    _dfs(treeNode.leftNode, list, level + 1);
    // Iterate over the right side
    _dfs(treeNode.rightNode, list, level + 1); }}Copy the code

/// Unit testing
test('Sequence traversal', () {
  var result = leveTraversingTree(treeNode3);
  print(Result:${result.toString()}');
  expect(
    result,
    equals([
      [10],
      [9.20],
      [15.35]])); }); Results: the [[10], [9.20], [15.35]]
Copy the code

conclusion

Dart is an excellent modern language, as you can see from the details, such as the use of optional position parameters [],.. The use of successive level operations, as well as the {} optional argument, which is not shown in this article but will be used a lot later, are very concise and friendly to developers.