二叉树学习笔记

二叉树

定义

• 最多两个子节点
• 有且只有一个Root节点
• 根节点到任何节点只有一条路径

父节点：拥有Children的节点称为父节点

叶子节点： 没有Children节点称为leaf节点

深度优先搜索(==DFS==)

• 代码实现

class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// recusive method
const depthFirstValues = (root) => {
    if (root === null) return [];
    const leftValues = depthFirstValues(root.left);
    const rightValues = depthFirstValues(root.right);
    return [root.val, ...leftValues, ...rightValues];
}

// const depthFirstValues = (root) => {
//     if (root === null)
//         return [];
//     const result = [];
//     const stack = [root];
//     while (stack.length > 0) {
//         const current = stack.pop();
//         // console.log(current.val);
//         result.push(current.valueOf())
//         // if (current.left)
//         //   stack.push(current.left);
//         if (current.right)
//             stack.push(current.right);
//         if (current.left)
//             stack.push(current.left);
//     }
//     return result;
// };

const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const e = new Node('e');
const d = new Node('d');
const f = new Node('f');

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

// depthFirstValues(a);

// a
// b
// d
// e
// c
// f
const result = depthFirstValues(a);
console.log(result) //[ 'a', 'b', 'd', 'e', 'c', 'f' ]

广度优先搜索(==BFS==)

const breadthFirstValues = (root) => {
    if(root === null) return [];
    const values = [];
    const queue = [root];

    while (queue.length > 0){
        const current = queue.shift();
        values.push(current.val);

        if (current.left !== null) queue.push(current.left);
        if (current.right !==null) queue.push(current.right);
    }

    return values;
};
class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const e = new Node('e');
const d = new Node('d');
const f = new Node('f');

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
const result = breadthFirstValues(a);
console.log(result); //[ 'a', 'b', 'c', 'd', 'e', 'f' ]

获取节点的值

• DFS Implements

const treeInclude = (root, target) => {
  if (root === null) return false;
    const queue = [root];
    while (queue.length > 0) {
        const current = queue.shift();
        if (current.val === target) {
            return true;
        } else {
            return false;
        }
        if (current.left) queue.push(current.left);
        if (current.right) queue.push(current.right);
    }
    return false;
}
//recrusive
const treeInclude = (root,target) => {
  if (root === null) return false;
  if (root.val === target) return true;
  return treeInclude(root.left,target) || treeInclude(root.right,target);
}

class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const e = new Node('e');
const d = new Node('d');
const f = new Node('f');

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

treeInclude(a,e);