CodingBetter

Publish Date: 2019-06-04

Word Count: 695

Read Times: 3 Min

Read Count:

Tree

Volcabulary

Tree: A connected, acycinc, undirected graph.

Degree of node: The number of children of a node

External node: leaves

Internal node: other nodes

Path: a unique, non-repeating path from r to n (we can use this sequence to define descendents and ancestors)

Depth(level)

Maximum depth = height

Path length: the sum of the levels of all nodes

External path length: the sum of the levels of external nodes

Internal path length: the sum of the levels of internal nodes

Representations

Root - down

key implementation: siblings and children (degree!)

static int treeSum(Tree<T> tree) {
  int sum;
  sum = tree.label();
  for(int i = 0; i < tree.degree(); i+= 1)
    sum += treeSum(T.child(i));
  return sum;
}

Leaf - up

key implementation: parent

Array representation (binary tree):

parent for k-th node: (k-1)/2
left child for k-th node: 2k + 1
right child for k-th node: 2k + 2

Tree Traversals

Traversals in an iterative way

In Java, we implement tree by an array. Thus, we must visit the root firstly, then, we visit its left child and its right child. (If one child is null, it will show null.)

If the array has the length n, we know the height of the tree is logn.

Preorder (DFS)

Used to create a copy of the tree

Root - Left -Right

It is in the same order of the array.

对于每一次visit：

1.首先将其value加入到输出队列中

2.检查left child，如果不为空，visit left

3.检查right child，如果不为空，visit right

while(!stack.empty()) {
  TreeNode node = stack.pop();
  preorder.add(node.val);

  if(node.right != null) {stack.add(node.right);}
  if(node.left != null) {stack.add(node.left);}
}

N-ary

        while(!stack.empty()) {
            Node node = stack.pop();
            preorder.add(node.val);

            Collections.reverse(node.children);
            for(Node c : node.children) {
                stack.add(c);
            }
        }

Inorder

In inorder sequence, we can find out all elements on left side of ‘Root’ are in left subtree and elements onright side of ‘Root’ are in right subtree.

In BST, the inorder sequence gives nodes in non-decreasing order.

Left - Root - Right

对于每一次visit:

1.如果有left child，将left child加入到stack中，visit left child，直到没有left child

2.将value加入到array中

3.如果有right child，visit right child（然后重复第一步）

while(node != null || !stack.empty()) {
  while(node != null) {
    stack.add(node);
    node = node.left;
  }

     TreeNode visitedNode = stack.pop();
  inorder.add(visitedNode.val);
  node = visitedNode.right;
}

Postorder (reverse of preorder)

Used to delete the tree

Left - Right - Root

对于每一次visit：

1.当node不为空时，将node.right和node加入到stack中，node = node.left

2.从stack中取第一个node，如果node.right != null并且node.right = stack.peek()，使node等于stack的第一个node，并且将原node放回到stack；否则，把node加入到输出队列中并使其为空

while(node != null || !stack.empty()) {
            while(node != null) {
                if(node.right != null) {
                    stack.push(node.right);
                }
                stack.push(node);

                node = node.left;
            }

            TreeNode visited = stack.pop();
            TreeNode tmp = null;
            if(!stack.empty()) {tmp = stack.peek();} 

            if(visited.right != null && visited.right == tmp) {
                node = stack.pop();
                stack.push(visited);     
            } else {
                postorder.add(visited.val);
            }
        }

Reverse of preorder

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.empty()) {
            TreeNode node = stack.pop();
            postorder.add(node.val);

            if(node.left != null) {
                stack.add(node.left);
            }

            if(node.right != null) {
                stack.add(node.right);
            }
        }

        Collections.reverse(postorder);

N-ary

        Stack<Node> stack = new Stack<>();
        stack.add(root);

        while(!stack.empty()) {
            Node node = stack.pop();
            postorder.add(node.val);

            for(Node c : node.children) {
                stack.add(c);
            }
        }

        Collections.reverse(postorder);