根据一些名字画出二叉树

Question

我有一个使用 nextjs 和 typescript 的项目。在这个迷你项目中，我实现了一个二进制级别的订单树。我想在浏览器中像树一样显示它，如下所示

我在 tree.ts 文件中有两个类。一类用于我的 treeNodes 和一类用于实现插入和 levelOrderTraverse 逻辑。

这是我的 tree.ts 文件

class Node<T> {
    public val: T;
    public left: Node<T> | null;
    public right: Node<T> | null;

    constructor(val: T) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

export class LevelOrderBinaryTree<T> {
    private root: Node<T> | null;

    constructor() {
        this.root = null;
    }

    getRootNode() {
        return this.root;
    }

    insert(data: T) {
        const q: Node<T>[] = [];
        if (this.root === null) {
            this.root = new Node(data);
        } else {
            q.push(this.root);
            while (q.length) {
                const node = q.shift()!;
                if (node.left === null) {
                    node.left = new Node(data);
                    break;
                } else {
                    q.push(node.left);
                }
                if (node.right === null) {
                    node.right = new Node(data);
                    break;
                } else {
                    q.push(node.right);
                }
            }
        }
    }

    levelOrderTraverse(root: Node<T>) {
        const result: T[][] = [];
        const queue: Node<T>[] = [];
        queue.push(root);

        while (queue.length) {
            const lvlSize = queue.length;
            const currentLvl: T[] = [];

            for (let i = 0; i < lvlSize; i++) {
                const currentNode = queue.shift()!;
                currentLvl.push(currentNode.val);
                if (currentNode.left) {
                    queue.push(currentNode.left);
                }
                if (currentNode.right) {
                    queue.push(currentNode.right);
                }
            }

            result.push(currentLvl);
        }
        return result;
    }
}

这是我的 Tree.tsx 组件

import React, { useEffect, useState } from 'react';
import classes from './Tree.module.scss';
import { LevelOrderBinaryTree } from '../../utils/tree';

const Tree = () => {
    const [nodes, setNodes] = useState<null | string[][]>(null);

    useEffect(() => {
        const LBT = new LevelOrderBinaryTree<string>();
        LBT.insert('Mike');
        LBT.insert('Daniel');
        LBT.insert('Christin');
        LBT.insert('Sara');
        LBT.insert('Ben');
        LBT.insert('Leo');
        const sequenceNodes = LBT.levelOrderTraverse(LBT.getRootNode()!);
        setNodes(sequenceNodes);
    }, []);
    if (!nodes) {
        return;
    }

    return (
        <div>
            <ul className={`${classes.tree} ${classes.vertical}`}>
                <li>
                    <div>Node</div>
                    <ul>
                        <li>
                            <div>node</div>
                            <ul>
                                <li>
                                    <div>node</div>
                                </li>
                                <li>
                                    <div>node</div>
                                </li>
                            </ul>
                        </li>
                        <li>
                            <div>node</div>
                            <ul>
                                <li>
                                    <div>node</div>
                                </li>
                                <li>
                                    <div>node</div>
                                </li>
                            </ul>
                        </li>
                    </ul>
                </li>
            </ul>
        </div>
    );
};

export default Tree;

这是我创建这棵树的风格

.tree {
  $color: #222;
  $border-color: #ddd;
  $background-color: #eee;
  $border-weight: 1px;
  $margin: 12px;

  margin: $margin * 1.5;
  padding: 0;

  &:not(:empty):before, &:not(:empty):after,
  ul:not(:empty):before, ul:not(:empty):after,
  li:not(:empty):before, li:not(:empty):after {
    display:block;
    position:absolute;
    content:"";
  }

  ul, li {
    position: relative;
    margin:0;
    padding:0;
  }



  li>div {
    background-color:$background-color;
    color:$color;
    padding:5px;
    display:inline-block;
  }

  &.vertical {
    display:flex;

    ul {
      display:flex;
      justify-content: center;
    }

    li {
      display:flex;
      flex-direction: column;
      align-items: center;

      div {
        margin: $margin $margin/2;
      }

      &:before {
        border-left: $border-weight solid $border-color;
        height: $margin;
        width: 0;
        top: 0;
      }

      &:after {
        border-top: $border-weight solid $border-color;
        height: 0;
        width: 100%;
      }

      &:first-child:after {
        border-top: $border-weight solid $border-color;
        height: 0;
        width: 50%;
        left: 50%;
      }

      &:last-child:after {
        border-top: $border-weight solid $border-color;
        height: 0;
        width: 50%;
        right: 50%;
      }

      &:only-child:after {
        content:none;
      }

      ul:before {
        border-left: $border-weight solid $border-color;
        height: $margin;
        width: 0;
        top: -$margin;
      }
    }

    &>li {
      &:only-child:before, &:only-child:after {
        content:none;
      }
    }
  }

}

当 levelOrderTraverse 方法被这个输入调用时，输出是这样的

        [
  ['Mike'],
['Daniel', 'Christin'],
['Sara', 'Ben', 'Leo']
]

我想根据这个结果创建我的树。应该是这样

但我找不到任何解决方案来创建它。

在此先感谢您的努力

Answer 1

要使用从 levelOrderTraverse 方法获得的数据动态生成树结构，可以使用递归。以下是如何修改 Tree.tsx 组件以动态生成树结构：

import React, { useEffect, useState } from 'react';
import classes from './Tree.module.scss';
import { LevelOrderBinaryTree, Node } from '../../utils/tree';

interface Props {
  node: Node<string>;
}

const TreeNode = ({ node }: Props) => {
  const [showChildren, setShowChildren] = useState(false);

  const hasChildren = node.left || node.right;

  const toggleChildren = () => setShowChildren(!showChildren);

  return (
    <li>
      <div onClick={toggleChildren}>{node.val}</div>
      {hasChildren && (
        <ul style={{ display: showChildren ? 'block' : 'none' }}>
          {node.left && <TreeNode node={node.left} />}
          {node.right && <TreeNode node={node.right} />}
        </ul>
      )}
    </li>
  );
};

const Tree = () => {
  const [root, setRoot] = useState<Node<string> | null>(null);

  useEffect(() => {
    const LBT = new LevelOrderBinaryTree<string>();
    LBT.insert('Mike');
    LBT.insert('Daniel');
    LBT.insert('Christin');
    LBT.insert('Sara');
    LBT.insert('Ben');
    LBT.insert('Leo');
    const rootNode = LBT.getRootNode();
    if (rootNode) {
      setRoot(rootNode);
    }
  }, []);

  if (!root) {
    return null;
  }

  return (
    <div>
      <ul className={`${classes.tree} ${classes.vertical}`}>
        <TreeNode node={root} />
      </ul>
    </div>
  );
};

export default Tree;

这里的TreeNode组件是一个递归组件，它以一个Node为prop，生成对应的树结构。如果该节点有子节点，它会呈现另一个带有子 TreeNode 组件的 ul 元素。 toggleChildren 函数用于在用户点击父节点时显示/隐藏子节点。

Tree 组件现在只维护根节点，并以根节点作为 prop 渲染单个 TreeNode 组件。

请注意，需要从 tree.ts 文件中导出 Node 类才能正常工作。