## Introduction to tree

• An abstract model of hierarchical data
• Common trees in front-end work include ： DOM Trees 、 Cascade selection （ Provincial and urban three levels , date ...）、 Tree control ...
• JS There are no trees in the forest , But you can use Object and Array Building tree , as follows ：

``````{
value: " Anhui Province ",
label: 'anhui',
children: [
{
value: " Hefei ",
label: 'hefei',
children: [
{
value: " Baohe district ",
label: 'baohe',
children: null
},
{
value: ' Lakeside area ',
label: 'binghu',
children: null
}
]
},
{
{
value: " Anqing City ",
label: 'anqing',
children: [
{
value: " Yuexiu District ",
label: 'yuexiu',
children: null
}
]
},
}
]
}``````
• Common operations of trees ： depth / Breadth Traverse first 、 First in order to traverse

## Depth and breadth first traversal

### 1. Depth-first traversal ： Search the branches of the tree as deep as possible

#### Algorithm formula ：

• Access the root node
• For the root node children Depth first traversal one by one

#### Code implementation

``````const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: []
},
{
val: 'e',
children: []
}
]
},
{
val: 'c',
children: [
{
val: 'f',
children: []
},
{
val: 'g',
children: []
}
]
}
]
}

const dfs = (root) => {
console.log(root.val)
// root.children.map((child)=> dfs(child))
root.children.map(dfs)
}
//  Perform depth first traversal functions
dfs(tree)
//  After execution, output in turn ： a b d e c f g
``````

### 2. Breadth first traversal ： First visit the node closest to the root node

#### Algorithm formula

• Create a new queue , Put the root node in the queue
• Get the team leader out of the team and interview
• Take the leader of the team children Join the team one by one
• Repeat the second 、 The three step , Until the queue is empty

#### Code implementation

``````const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: []
},
{
val: 'e',
children: []
}
]
},
{
val: 'c',
children: [
{
val: 'f',
children: []
},
{
val: 'g',
children: []
}
]
}
]
}

const bfs = (root) => {
// step1:  Create a new queue
let queue = []
// step2:  Put the root node in the queue
queue.push(root)
while(queue.length > 0) {
// step3:  Take out the team leader and interview
let n = queue.shift()
console.log(n.val)
// step4:  Take the leader of the team  children  Join the team one by one and repeat the above steps
n.children.map(child=> {
queue.push(child)
})
}
}
//  Perform breadth first traversal functions
bfs(tree)
//  Output... In sequence ：a b c d e f g``````

### 3. Traversal of binary tree in the first middle and then order

• Binary tree concept ：

Each node in the tree can have at most two child nodes ;

stay JS Zhongtong common Object To simulate a binary tree

Code emulation

``````// bt.js
const bt = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null,
},
right: {
val: 5,
left: null,
right: null,
},
},
right: {
val: 3,
left: {
val: 6,
left: null,
right: null,
},
right: {
val: 7,
left: null,
right: null,
},
},
};

module.exports = bt;``````

#### The first sequence traversal

Algorithm formula

• Access the root node
• The left subtree of the root node is traversed in order
• First traverse the right subtree of the root node

Code practice

``````const bt = require('./bt')
const preOrder = (root) => {
if(!root) return
console.log(root.val)
preOrder(root.left)
preOrder(root.right)
}
//  perform
preOrder(bt)
//  Output... In sequence ：1 2 4 5 3 6 7``````

#### In the sequence traversal

Algorithm formula

• The left subtree of the root node is traversed in the middle order
• Access the root node
• The right subtree of the root node is traversed in the middle order

Code practice

``````const bt = require('./bt')

const inOrder = (root) => {
if(!root) return
inOrder(root.left)
console.log(root.val)
inOrder(root.right)
}

inOrder(bt)
//  Output... In sequence  4 2 5 1 6 3 7``````

#### After the sequence traversal

Algorithm formula

• The left subtree of the root node is traversed posteriorly
• The right subtree of the root node is traversed posteriorly
• Access the root node

Code practice

``````const bt = require('./bt')
const postOrder = (root) => {
if(!root) return
postOrder(root.left)
postOrder(root.right)
console.log(root.val)
}
postOrder(bt)
//  Output... In sequence ：4 5 2 6 7 3 1``````

https://cdmana.com/2020/12/20201224104311384C.html

Scroll to Top