Chqx Playground

Appearance

树的遍历 ​

广度优先 ​

有兄弟节点时优先遍历兄弟节点

while写法 ​

ts
/**
 * 广度优先
 * 获取节点及子节点 by while
 * @param node 当前节点
 */
export function getScopeNodeList1<T extends ITreeNode<T>>(node: T) {
  const nodeList: T[] = [];
  const queue: T[] = [node];
  while (queue.length) {
    const item = queue.shift() as T;
    nodeList.push(item);
    for (let i = 0; i < item.children.length; i++) {
      queue.push(item.children[i]);
    }
  }
  return nodeList;
}

/**
 * 广度优先
 * 遍历节点及子节点 by while
 * @param callback 遍历时执行的回调
 * @param node 当前节点
 */
export function forScopeEachTree1<T extends ITreeNode<T>>(
  callback: IForEachNode<T>,
  node: T
) {
  const nodeList: IWarpperNode<T>[] = [];
  const stack: IWarpperNode<T>[] = [{ current: node, index: 0 }];
  while (stack.length) {
    const item = stack.shift()!;
    nodeList.push(item);
    callback(item.current, item.index, item.parent);
    for (let i = 0; i < item.current.children.length; i++) {
      stack.push({
        current: item.current.children[i],
        index: i,
        parent: item.current
      });
    }
  }
}
/**
 * 广度优先
 * 获取节点及子节点 by while
 * @param node 当前节点
 */
export function getScopeNodeList1<T extends ITreeNode<T>>(node: T) {
  const nodeList: T[] = [];
  const queue: T[] = [node];
  while (queue.length) {
    const item = queue.shift() as T;
    nodeList.push(item);
    for (let i = 0; i < item.children.length; i++) {
      queue.push(item.children[i]);
    }
  }
  return nodeList;
}

/**
 * 广度优先
 * 遍历节点及子节点 by while
 * @param callback 遍历时执行的回调
 * @param node 当前节点
 */
export function forScopeEachTree1<T extends ITreeNode<T>>(
  callback: IForEachNode<T>,
  node: T
) {
  const nodeList: IWarpperNode<T>[] = [];
  const stack: IWarpperNode<T>[] = [{ current: node, index: 0 }];
  while (stack.length) {
    const item = stack.shift()!;
    nodeList.push(item);
    callback(item.current, item.index, item.parent);
    for (let i = 0; i < item.current.children.length; i++) {
      stack.push({
        current: item.current.children[i],
        index: i,
        parent: item.current
      });
    }
  }
}

回调函数写法 ​

ts
/**
 * 广度优先
 * 获取节点及子节点 by callback TODO!!!
 * @param node 当前节点
 */
export function getScopeNodeList2<T extends ITreeNode<T>>(node: T): T[] {
  const nodeList: T[] = [];
  const queue: T[] = [node];

  while (queue.length) {
    const item = queue.shift()!;
    nodeList.push(item);
    for (let i = 0; i < item.children.length; i++) {
      queue.push(item.children[i]);
    }
  }
  return nodeList;
}

/**
 * 广度优先
 * 遍历节点及子节点 by callback
 * @param callback 遍历时执行的回调
 * @param nodeTree 当前节点的数组
 * @param parentNode 父节点
 */
export function forScopeEachTree2<T extends ITreeNode<T>>(
  callback: IForEachNode<T>,
  nodeTree: T[],
  parentNode?: T
) {
  const nodeList: T[] = [];
  nodeTree.forEach((item, index) => {
    callback(item, index, parentNode);
    nodeList.push(item);
  });
  nodeList.forEach(item => {
    forScopeEachTree2(callback, item.children, item);
  });
}
/**
 * 广度优先
 * 获取节点及子节点 by callback TODO!!!
 * @param node 当前节点
 */
export function getScopeNodeList2<T extends ITreeNode<T>>(node: T): T[] {
  const nodeList: T[] = [];
  const queue: T[] = [node];

  while (queue.length) {
    const item = queue.shift()!;
    nodeList.push(item);
    for (let i = 0; i < item.children.length; i++) {
      queue.push(item.children[i]);
    }
  }
  return nodeList;
}

/**
 * 广度优先
 * 遍历节点及子节点 by callback
 * @param callback 遍历时执行的回调
 * @param nodeTree 当前节点的数组
 * @param parentNode 父节点
 */
export function forScopeEachTree2<T extends ITreeNode<T>>(
  callback: IForEachNode<T>,
  nodeTree: T[],
  parentNode?: T
) {
  const nodeList: T[] = [];
  nodeTree.forEach((item, index) => {
    callback(item, index, parentNode);
    nodeList.push(item);
  });
  nodeList.forEach(item => {
    forScopeEachTree2(callback, item.children, item);
  });
}

深度优先 ​

有子节点时优先遍历子节点

while写法 ​

ts
/**
 * 深度遍历
 * 获取节点及子节点 by while
 * @param node 遍历的节点树
 * @returns 得到的节点list
 */
export function getDeepNodeList1<T extends ITreeNode<T>>(node: T) {
  const nodeList: T[] = [];
  const stack: T[] = [node];
  while (stack.length) {
    const item = stack.pop()!;
    nodeList.push(item);
    for (let i = item.children.length - 1; i > -1; i--) {
      stack.push(item.children[i]);
    }
  }
  return nodeList;
}

/**
 * 深度遍历
 * 遍历节点及子节点 by while
 * @param callback 遍历时执行的回调
 * @param node 遍历的节点树
 */
export function forDeepEachTree1<T extends ITreeNode<T>>(
  callback: IForEachNode<T>,
  node: T
) {
  const stack: IWarpperNode<T>[] = [{ current: node, index: 0 }];
  while (stack.length) {
    const item = stack.pop()!;
    callback(item.current, item.index, item.parent);
    for (let i = item.current.children.length - 1; i > -1; i--) {
      stack.push({
        current: item.current.children[i],
        index: i,
        parent: item.current
      });
    }
  }
}
/**
 * 深度遍历
 * 获取节点及子节点 by while
 * @param node 遍历的节点树
 * @returns 得到的节点list
 */
export function getDeepNodeList1<T extends ITreeNode<T>>(node: T) {
  const nodeList: T[] = [];
  const stack: T[] = [node];
  while (stack.length) {
    const item = stack.pop()!;
    nodeList.push(item);
    for (let i = item.children.length - 1; i > -1; i--) {
      stack.push(item.children[i]);
    }
  }
  return nodeList;
}

/**
 * 深度遍历
 * 遍历节点及子节点 by while
 * @param callback 遍历时执行的回调
 * @param node 遍历的节点树
 */
export function forDeepEachTree1<T extends ITreeNode<T>>(
  callback: IForEachNode<T>,
  node: T
) {
  const stack: IWarpperNode<T>[] = [{ current: node, index: 0 }];
  while (stack.length) {
    const item = stack.pop()!;
    callback(item.current, item.index, item.parent);
    for (let i = item.current.children.length - 1; i > -1; i--) {
      stack.push({
        current: item.current.children[i],
        index: i,
        parent: item.current
      });
    }
  }
}

回调函数写法 ​

ts
/**
 * 深度遍历
 * 获取节点及子节点 by callback
 * @param node 遍历的节点树
 */
export function getDeepNodeList2<T extends ITreeNode<T>>(node: T): T[] {
  return node.children.reduce(
    (total, current) => {
      return total.concat(getDeepNodeList2(current));
    },
    [node]
  );
}

/**
 * 深度遍历
 * 遍历节点及子节点 by callback
 * @param callback 遍历时执行的回调
 * @param node 遍历的节点树
 * @param index 当前index
 * @param parentNode 父节点
 */
export function forDeepEachTree2<T extends ITreeNode<T>>(
  callback: IForEachNode<T>,
  node: T,
  index: number,
  parentNode?: T
) {
  callback(node, index, parentNode);
  node.children.forEach((item, idx) => {
    forDeepEachTree2(callback, item, idx, node);
  });
}
/**
 * 深度遍历
 * 获取节点及子节点 by callback
 * @param node 遍历的节点树
 */
export function getDeepNodeList2<T extends ITreeNode<T>>(node: T): T[] {
  return node.children.reduce(
    (total, current) => {
      return total.concat(getDeepNodeList2(current));
    },
    [node]
  );
}

/**
 * 深度遍历
 * 遍历节点及子节点 by callback
 * @param callback 遍历时执行的回调
 * @param node 遍历的节点树
 * @param index 当前index
 * @param parentNode 父节点
 */
export function forDeepEachTree2<T extends ITreeNode<T>>(
  callback: IForEachNode<T>,
  node: T,
  index: number,
  parentNode?: T
) {
  callback(node, index, parentNode);
  node.children.forEach((item, idx) => {
    forDeepEachTree2(callback, item, idx, node);
  });
}

类型定义 ​

ts
// 树的节点item
interface ITreeNode<T> {
  id?: any;
  children: T[];
  [key: string]: any;
}

// 包装节点
interface IWarpperNode<T> {
  current: T;
  index: number;
  parent?: T;
}

// 遍历节点
type IForEachNode<T> = (node: T, index: number, parentNode?: T) => void;
// 树的节点item
interface ITreeNode<T> {
  id?: any;
  children: T[];
  [key: string]: any;
}

// 包装节点
interface IWarpperNode<T> {
  current: T;
  index: number;
  parent?: T;
}

// 遍历节点
type IForEachNode<T> = (node: T, index: number, parentNode?: T) => void;

Released under the MIT License.

Copyright © 2022-present Chqx Playground