在此二进制搜索树（JavaScript）代码中，有序，前序和后序的递归如何工作？

Question

我想想像一下深度优先遍历函数是如何工作的？我正在学习递归，并且我了解了insert和contains函数。但是，当涉及深度优先遍历时，我无法理解程序的流程？

 function bst(value){
 this.value = value;
 this.left = null;
 this.right = null;
 };

 bst.prototype.insert = function(value){

 if(value <= this.value){
   if(!this.left) this.left = new bst(value);
   else this.left.insert(value);
 }
 else if (value > this.value){
   if(!this.right) this.right = new bst(value);
   else this.right.insert(value);
 }
 };

 bst.prototype.contains = function(value){
   if (value === this.value) return true;
   if (value < this.value){
     if(!this.left) return false;
     else return this.left.contains(value);
   }
   if (value > this.value){
     if(!this.right) return false;
     else return this.right.contains(value);
   }
 };

 bst.prototype.depthFirstTraversal = function(iteratorFunc, order){
   if(order === 'pre-order') iteratorFunc(this.value);
   if(this.left) this.left.depthFirstTraversal(iteratorFunc, order);
   if(order === 'in-order') iteratorFunc(this.value);
   if(this.right)this.right.depthFirstTraversal(iteratorFunc, order);
   if(order === 'post-order') iteratorFunc(this.value);
 };

 function log(value){
 console.log(value);
 }
 var mybst = new bst(50);
 mybst.insert(40);
 mybst.insert(30);
 mybst.insert(60);
 mybst.insert(10);
 mybst.insert(70);
 mybst.insert(80);
 mybst.insert(55);
 console.log(mybst);
 console.log(mybst.contains(30));
 mybst.depthFirstTraversal(log, "in-order");

Answer 1

您可以排序类型以按想要的顺序获取输出：

order  nodes
-----  -----  -----  -----
in     left   root   right
pre    root   left   right
post   left   right   root

function bst(value) {
  this.value = value;
  this.left = null;
  this.right = null;
};

bst.prototype.insert = function(value) {

  if (value <= this.value) {
    if (!this.left) this.left = new bst(value);
    else this.left.insert(value);
  } else if (value > this.value) {
    if (!this.right) this.right = new bst(value);
    else this.right.insert(value);
  }
};

bst.prototype.contains = function(value) {
  if (value === this.value) return true;
  if (value < this.value) {
    if (!this.left) return false;
    else return this.left.contains(value);
  }
  if (value > this.value) {
    if (!this.right) return false;
    else return this.right.contains(value);
  }
};

bst.prototype.depthFirstTraversal = function(iteratorFunc, order) {
  if (order === 'pre-order') iteratorFunc(this.value);
   
  if (this.left) this.left.depthFirstTraversal(iteratorFunc, order);

  if (order === 'in-order') iteratorFunc(this.value);

  if (this.right) this.right.depthFirstTraversal(iteratorFunc, order);

  if (order === 'post-order') iteratorFunc(this.value);
};

function log(value) {
  console.log(value);
}
var mybst = new bst(50);
mybst.insert(40);
mybst.insert(30);
mybst.insert(60);
mybst.insert(10);
mybst.insert(70);
mybst.insert(80);
mybst.insert(55);
//console.log(mybst);
//console.log(mybst.contains(30));

mybst.depthFirstTraversal(log, "in-order"); console.log('');
mybst.depthFirstTraversal(log, "pre-order"); console.log('');
mybst.depthFirstTraversal(log, "post-order");

.as-console-wrapper { max-height: 100% !important; top: 0; }