在Javascript上显示二叉搜索树遍历（递归方式）

问题描述 投票：0回答：5

我正在尝试控制台二叉树中的每个数据。我的主要问题是我想以递归方式实现。到目前为止我基本上有这个代码：

this.levelOrder = function (root) {
    if (root.data != null) {
        console.log(root.data);

        if (root.left != null) {
            this.levelOrder(root.left);
        }

        if (root.right != null) {
            this.levelOrder(root.right)
        }
    } else {
        return;
    }
};

输出是

3 2 1 5 4 7

但是应该是

3 2 5 1 4 7
。所以基本上我正在访问节点的第一个子节点，而不是首先打印所有子节点。

javascript binary-tree binary-search-tree
5个回答
5
投票

假设有一棵这样的树，

      4
  2       6
1   3   5   7

和一个对象字面量 

tree = {
    data: 4,
    left: {
        data: 2,
        left: {
            data: 1,
            left: null,
            right: null
        },
        right: {
            data: 3,
            left: null,
            right: null
        }
    },
    right: {
        data: 6,
        left: {
            data: 5,
            left: null,
            right: null
        },
        right: {
            data: 7,
            left: null,
            right: null
        }
    }
};

您可以递归调用该函数，首先获取树的左侧部分，然后获取右侧部分。该算法称为深度优先搜索。

此函数使用单次检查，因为这足以先检查然后继续。

var depthFirst = function (node) {
        if (node) {
            console.log(node.data);
            depthFirst(node.left);
            depthFirst(node.right)
        }
    },
    tree = { data: 4, left: { data: 2, left: { data: 1, left: null, right: null }, right: { data: 3, left: null, right: null } }, right: { data: 6, left: { data: 5, left: null, right: null }, right: { data: 7, left: null, right: null } } };

depthFirst(tree); // 4 2 1 3 6 5 7

对于广度优先搜索，一种首先迭代树的每个级别的算法，您可以将此代码与上面相同的树数据一起使用。

var breadthFirst = function (node) {

        function bf(queue) {
            var newQueue = [];
            queue.forEach(function (node) {
                console.log(node.data);
                node.left && newQueue.push(node.left);
                node.right && newQueue.push(node.right);
            });
            newQueue.length && bf(newQueue);
        }

        bf([node]);
    },
    tree = { data: 4, left: { data: 2, left: { data: 1, left: null, right: null }, right: { data: 3, left: null, right: null } }, right: { data: 6, left: { data: 5, left: null, right: null }, right: { data: 7, left: null, right: null } } };

breadthFirst(tree); // 4 2 6 1 3 5 7

2
投票

假设 Node 定义是这样的：

export default class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

树的定义是这样的：

import Node from './Node.js';

export default class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    //methods such as search, traversal, insert, etc...
}

您可以像这样执行遍历（最好作为 BinarySearchTree 的方法） :

inorder(node) {
    if (node !== null) {
        this.inorder(node.left);
        console.log(node.data);
        this.inorder(node.right);
    }
}

postorder(node) {
    if (node !== null) {
        this.postorder(node.left);
        this.postorder(node.right);
        console.log(node.data);
    }
}

preorder(node) {
    if (node !== null) {
        console.log(node.data);
        this.preorder(node.left);
        this.preorder(node.right);
    }
}

如果您想存储遍历的结果，您可以传递一些方法将附加值的对象。

--

奖金

如果您想以某种令人愉悦的方式显示整个树，我建议使用存储在节点和应用程序状态中的一些附加信息。 首先，我会向每个节点定义 (x,y) 添加一些附加信息：

export default class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.x = 0;
        this.y = 0;
    }
}

然后根据当前树数据创建一个空网格（矩阵），

createMatrix = (minX, maxX, depth) => {
        let displayMatrix = [];
        for (let i = 0; i <= depth; i++) {
            let line = [];
            for (let j = 0; j <= maxX - minX; j++) {
                line.push(' ');
            }
            displayMatrix.push(line);
        }
        return displayMatrix;
}

其中minX是所有节点中最小的X值，maxX是最大的（这些值可以在将节点插入树时获得，或者通过遍历树并比较节点属性来获得），然后用节点数据以及节点之间的“\”、“/”字符：

    fillMatrix(node, matrix, minX, side = "root") {
      if(node !== null){
        matrix[node.y][node.x + Math.abs(minX)] = node.data;
        if(side === "left"){
            matrix[node.y-1][node.x + Math.abs(minX)+1] = '/';
        }
        else if (side === "right"){
            matrix[node.y - 1][node.x + Math.abs(minX) - 1] = '\\';
        }
        this.fillMatrix(node.left, matrix, minX, "left");
        this.fillMatrix(node.right, matrix, minX, "right");
      }
      return matrix;
    }

然后这个结果矩阵将在没有“线”和值的地方保存一个“”，保存node.data所在的数字，并保存“/”或“\”作为节点之间的线。 然后您可以使用它将其显示在画布上或控制台中。

例如，这里我动态创建了一个表格，每个元素中都有一个 div，根据它所包含的字符类型，其格式有所不同：

0
投票
/*                    |
                      h
          /                     \
         d                       l
    /         \             /         \
   b           f           j           n
 /   \       /   \       /   \       /   \
a     c     e     g     i     k     m     o

bt.insert("d");
bt.insert("l");
bt.insert("b");
bt.insert("f");
bt.insert("j");
bt.insert("n");
bt.insert("a");
bt.insert("c");
bt.insert("e");
bt.insert("g");
bt.insert("i");
bt.insert("k");
bt.insert("m");
bt.insert("o");
      

*/
function printTree(inorder, bredthOrder, size) {
   size = size || 2;
   const total = inorder.length;
   const numberOfLevels = Math.ceil(Math.log2(total));
   let pointerBOrder = 0;
   let blank = " ";
   for (let level = 0; level < numberOfLevels; level++) {
      let itemPerLevel = Math.pow(2, level);
      let out = [];
      let branches = [];
      let slantDirection = true;//up
      for (let itemNumber = 0; itemNumber < itemPerLevel; itemNumber++) {
         let item = bredthOrder[pointerBOrder++];
         for (let x = 1; x <= inorder.length; x++) {
            const ino = inorder[x - 1];
            let nInd = size * (x - 1);
            if (item == ino) {
               out[nInd] = item;
               if (item) {
                  if (bredthOrder[0] == item) {
                     branches[nInd] = "|";
                  } else if (slantDirection) {
                     branches[nInd + 1] = "/";
                  } else {
                     if (nInd - 1 >= 0) {
                        branches[nInd - 1] = "\\";
                     }
                  }
                  slantDirection = !slantDirection;
               }
            } else {
               out[nInd] = out[nInd] || blank;
            }
            branches[nInd] = branches[nInd] || blank;
            for (let fill = 1; fill <= size - 1; fill++) {
               out[nInd + fill] = blank;
               branches[nInd + fill] = branches[nInd + fill] || blank;
            }
         }
      }
      console.log(branches.join(''));
      console.log(out.join(''));
      out = [];
   }
}
class Node {
   constructor(value) {
      this.left = null;
      this.right = null;
      this.value = value;
   }
}
class BinaryTree {
   constructor(value) {
      this.root = value == null ? null : new Node(value);
   }

   insert(value, node) {
      if (node == null) {
         node = this.root;
      }
      if (node == null) {
         node = new Node(value);
         return;
      }
      if (node.value >= value) {
         if (node.left == null) {
            node.left = new Node(value);
            return;
         } else {
            this.insert(value, node.left);
            return;
         }
      } else {
         if (node.right == null) {
            node.right = new Node(value);
            return;
         } else {
            this.insert(value, node.right);
            return;
         }
      }
   }
   print(node, acc) {
      if (node == null) {
         return acc;
      } else {
         if (node.left != null) {
            acc = this.print(node.left, acc);
         }
         acc.push(node.value);
         if (node.right != null) {
            acc = this.print(node.right, acc);
         }
         return acc;
      }
   }
   printInOrder() {
      return this.print(this.root, []);
   }
   getSiblings(node) {
      if (node == null) {
         return [];
      }
      let acc = [];
      if (node.left != null) {
         acc.push(node.left);
      }
      if (node.right != null) {
         acc.push(node.right);
      }
      return acc;
   }
   printBredthOrder() {
      let result = [];
      if (this.root == null) {

      } else {
         let acc = [this.root];
         let workingAcc = [this.root];
         let tmpAcc = [];
         do {
            tmpAcc = [];
            for (let i = 0; i < workingAcc.length; i++) {
               acc = [...acc, workingAcc[i].left];
               acc = [...acc, workingAcc[i].right];
               let left = this.getSiblings(workingAcc[i].left);
               let right = this.getSiblings(workingAcc[i].right);
               tmpAcc = [...tmpAcc, ...left];
               tmpAcc = [...tmpAcc, ...right];
            }
            acc = [...acc, ...tmpAcc];
            workingAcc = tmpAcc;
         } while (tmpAcc.length != 0);
         for (let i = 0; i < acc.length; i++) {
            result.push(acc[i].value);
         }
      }

      return result;
   }
}
let bt = new BinaryTree("h");
bt.insert("d");
bt.insert("l");
bt.insert("b");
bt.insert("f");
bt.insert("j");
bt.insert("n");
bt.insert("a");
bt.insert("c");
bt.insert("e");
bt.insert("g");
bt.insert("i");
bt.insert("k");
bt.insert("m");
bt.insert("o");
let io = bt.printInOrder();
let bo = bt.printBredthOrder();
printTree(io, bo);
0
投票

有点晚了，但这很好用。

function PrettyPrintTree(tree: Tree) {
  const nodes = nodeData(tree.root, 0, 0);

  const leftMost = nodes.reduce((acc, n) => {
    return n.x * 2 < acc ? n.x * 2 : acc;
  }, 0);
  const rightMost = nodes.reduce((acc, n) => {
    return n.x * 2 > acc ? n.x * 2 : acc;
  }, 0);
  const heightDown = nodes.reduce((acc, n) => {
    return n.y * 2 < acc ? n.y * 2 : acc;
  }, 0);

  for (let y = 0; y >= heightDown; y--) {
    let line = "";

    for (let x = leftMost; x <= rightMost; x++) {
      const node = nodes.find(n => {
        return n.x * 2 === x && n.y * 2 === y;
      });

      if (node) line += node.data;
      else {
        if (
          nodes.find(n => n.x * 2 === x - 1 && n.y * 2 === y - 1) &&
          nodes.find(n => n.x * 2 === x + 1 && n.y * 2 === y + 1)
        )
          line += "/";
        else if (
          nodes.find(n => n.x * 2 === x + 1 && n.y * 2 === y - 1) &&
          nodes.find(n => n.x * 2 === x - 1 && n.y * 2 === y + 1)
        )
          line += "\\";
        else line += " ";
      }
    }

    console.log(line);
  }
}

function nodeData(node: TreeNode, x: number, y: number) {
  let nodes = [
    {
      data: node.data.data,
      x: x,
      y: y,
    },
  ];

  if (node.left) nodes.push(...nodeData(node.left, x - 1, y - 1));
  if (node.right) nodes.push(...nodeData(node.right, x + 1, y - 1));

  return nodes;
}
-2
投票
// Node Class
class Node {
  constructor (val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Binary Tree
const head = new Node(20, 
  new Node(10, 
  new Node(5, 
  new Node(3, 
  new Node(2, 
  new Node(1)), 
  new Node(4)), 
  new Node(8, 
  new Node(7, 
  new Node(6)), 
  new Node(9))), 
  new Node(15, 
  new Node(13, 
  new Node(11, 
  null, 
  new Node(12)), 
  new Node(14)), 
  new Node(18, 
  new Node(16, 
  null, 
  new Node(17)), 
  new Node(19)))), 
  new Node(30, new Node(25, 
  new Node(23, 
  new Node(22, 
  new Node(21)), 
  new Node(24)), 
  new Node(28, 
  new Node(27, 
  new Node(26)), 
  new Node(29))), 
  new Node(35, 
  new Node(33, 
  new Node(31, 
  null, 
  new Node(32)), 
  new Node(34)), 
  new Node(38, 
  new Node(36, 
  null, 
  new Node(37)), 
  new Node(39, 
  null, 
  new Node(40))))), 
  );

// VIEW
//                                                      20
//                                                     10 30
//                        5 15                           |                          25 35
//          3 8            |           13 18            ||           23 28            |            33 38
//   2 4     |    7 9     ||    11 14    |    16 19    |||    22 24    |    27 29    ||     31 34    |    36 39
//1 n | n n || 6 n | n n ||| n 12 | n n || 17 n | n n |||| 21 n | n n || 26 n | n n |||| n 32 | n n || n 37 | n 40

// In Order Tree Traversal
const inOrder = (node) => {
  if(node.left !== null) {
    inOrder(node.left);
  }
  console.log(node.val);
  if(node.right !== null) {
    inOrder(node.right);
  }
}

// Pre Order Tree Traversal
const preOrder = (node) => {
  console.log(node.val);
  if(node.left !== null) {
    preOrder(node.left);
  }
  if(node.right !== null) {
    preOrder(node.right);
  }
}

// Post Order Tree Traversal
const postOrder = (node) => {
  if(node.left !== null) {
    postOrder(node.left);
  }
  if(node.right !== null) {
    postOrder(node.right);
  }
  console.log(node.val);
}

// Node Count Recursively
const nodeCount = (node) => {
  if(node.left !== null) {
    nodeCount(node.left);
  }
  if(node.right !== null) {
    nodeCount(node.right);
  }
  count++;
}

// Sum of all Nodes Recursively
const totalValue = (node) => {
  if(node.left !== null) {
    totalValue(node.left);
  }
  if(node.right !== null) {
    totalValue(node.right);
  }
  total += node.val;
}

// inOrder(head);
// preOrder(head);
// postOrder(head);

let count = 0;
nodeCount(head)
console.log(count);

let total = 0;
totalValue(head)
console.log(total);
// NOTE
// if the values are continuous between 1/0 and n then the total is simply (n*(n+!))/2
// if the values are continuous between m and n then the total is simply ((n*(n+!))/2) - ((m*(m+!))/2)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.