二叉樹in JavaScript

1946 ワード

function Node(data, left, right) {
      this.data = data
      this.left = left
      this.right = right
    }
    Node.prototype = {
      constructor: Node,
      show: function () {
        return this.data
      }
    }

    function BSTree() {
      this.root = null
    }
    BSTree.prototype = {
      constructor: BSTree,
      //     
      insert: function (data) {
        var node = new Node(data, null, null)
        if (this.root == null) {
          this.root = node
        } else {
          //     
          // current           
          var current = this.root
          var parent
          while (1) {
            parent = current
            if (data < current.data) {
              // current   
              current = current.left
              //       null
              if (!current) {
                //     
                parent.left = node
                break
              }
            } else {
              current = current.right
              if (!current) {
                parent.right = node
                break
              }
            }
          }
        }
      },
      //     
      inOrder: function (node) {
        if (node) {
          this.inOrder(node.left)
          console.log(node.show())
          this.inOrder(node.right)
        }
      },
      //     
      preOrder: function (node) {
        if (node) {
          console.log(node.show())
          this.inOrder(node.left)
          this.inOrder(node.right)
        }
      },
      //     
      postOrder: function (node) {
        if (node) {
          this.inOrder(node.left)
          this.inOrder(node.right)
          console.log(node.show())
        }
      }
    }

    var nums = new BSTree()
    nums.insert(23)
    nums.insert(45)
    nums.insert(16)
    nums.insert(37)
    nums.insert(3)
    nums.insert(99)
    nums.insert(22)
    nums.inOrder(nums.root)
    console.log(nums)