Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Trees and the basic concepts of trees

Tree structure is a kind of nonlinear storage structure, n nodes form a finite set with hierarchical relationship, where n >= 0 is called empty tree when n = 0

Stores a collection of data elements that specify a one-to-many relationship

  • node
  • The degree of
  • The root node
  • subtree

The nature of the tree

  • There is one and only one root, and the root has no parent

Trees and linked list

  • A linked list can be viewed as a tree that triggers a path from the root node to the leaf node

Binary tree

  • Nonlinear data structure
  • The structure of data elements (nodes) organized in branch relationships
  • An ordered tree with at most two subtrees per node

Perfect Binary tree

The leaf nodes are all in the same layer and all nodes except the leaf node have two child nodes

Complete Binary tree

For a binary tree, if depth D (d>1) all nodes except layer D form a full binary tree, and all nodes of layer D are arranged continuously and closely from left to right

  • Leaf nodes can only occur in the largest two layers
  • For any node, if the maximum level of the right subtree is L, the maximum level of the left subtree is L or L+1(the subtree must be aligned to the left).
  • There are only zero or one nodes of degree one
Complete binary tree properties
  • Leaf node (node with degree 0)


n = n 0 + n 1 + n 2 n = n_0 + n_1 + n_2
n 0 = n 2 + 1 n_0 = n_2 + 1


n = 2 n 0 + n 1 – 1 n = 2n_0 + n_1 – 1

Incomplete binary tree

Binary tree storage mode

  • Chain storage
  • Linear storage (graph)

Traversal of binary trees

BFS(Breadth First Search)
  • Sequence traversal
DFS(Depth-first search)

Pre -, mid -, or post-sequential implementations can be implemented using recursion and iteration respectively

  • Foreword (middle left)
  • Middle sequence (left middle right)
  • Rear preface (middle left and right)

Binary search tree

Binary search for tree structure,

The dictionary tree

Balanced binary trees

The absolute value of the difference between the height of an empty tree or the left and right subtrees is no more than 1, and both subtrees are a balanced binary tree. At the same time, the balanced binary tree must be a binary search tree

Code implementation

function node(value){
    return{
        value,
        children: [].}}const a = node('a');
const b = node('b');
const c = node('c');
const d = node('d');
const e = node('e');
const f = node('f');
const g = node('g');
const h = node('h');
const i = node('i');
const j = node('j');
const k = node('k');
const l = node('l');
const m = node('m');

a.children.push(b,c,d);
b.children.push(e);
e.children.push(k,l);
c.children.push(f,g,h);
h.children.push(m);
d.children.push(i,j);

Copy the code
// Recursive function arguments and return values
// Termination conditions
// Single-layer recursive logic

const breathFirst = (startNode,cb) = >{
    // console.log(startNode)
    let queue = [startNode];
    // console.log(queue.shift())
    while(queue.length>0) {let node = queue.shift();
        // console.log(node)cb(node); queue.push(... node.children) } }Copy the code
breathFirst(a,function(node){
    console.log(node.value)
})

Copy the code
/ * * * *@param {*} node 
 * @param {*} cb 
 */
const depthFirstPreOrder = (node,cb) = >{
    cb(node);
    node.children.forEach(node= >{
        depthFirstPreOrder(node,cb)
    })
}

Copy the code
const depthFirstPostOder = (node,cb) = >{
    node.children.forEach(node= >{
        depthFirstPostOder(node,cb)
    });
    cb(node)
}


// depthFirstPreOrder(a,function(node){
// console.log(node.value)
// })

// depthFirstPostOder(a,function(node){
// console.log(node.value)
// })
Copy the code