자바스크립트 데이터 구조 이진 검색 트리 구현 방법_자바스크립트 기술

본 글의 예시에서는 자바스크립트에서 이진 검색 트리를 구현하는 방법을 설명합니다. 참고하실 수 있도록 모든 사람과 공유하세요. 자세한 내용은 다음과 같습니다.

이진 검색 트리: 이름에서 알 수 있듯이 트리의 각 노드는 최대 두 개의 포크를 가지며 왼쪽 포크 노드의 값은 < 입니다.

특징: 노드 삽입, 최대/최소 노드 찾기, 노드 값 정렬이 매우 편리합니다

이진 검색 트리-자바스크립트 구현

<script type="text/javascript">
// <![CDATA[
 //打印输出
 function println(msg) {
  document.write(msg + " ");
 }
 //节点类
 var Node = function (v) {
  this.data = v; //节点值
  this.left = null; //左节点
  this.right = null; //右节点
 }
 //二叉搜索树类
 var BinarySearchTree = function () {
  this.root = null; //初始化时,根节点为空
  //插入节点
  //参数：v 为节点的值
  this.insert = function (v) {
   var newNode = new Node(v);
   if (this.root == null) {
    //树为空时，新节点，直接成为根节点
    this.root = newNode;
    return;
   }
   var currentNode = this.root; //工作“指针”节点（从根开始向下找）
   var parentNode = null;
   while (true) {
    parentNode = currentNode;
    if (v < currentNode.data) {
     //当前节点的值 > 目标节点的值     
     //应该向左插，工作节点移到左节点
     currentNode = currentNode.left;
     if (currentNode == null) {
      //没有左节点，则新节点，直接成为左节点
      parentNode.left = newNode;
      return; //退出循环
     }
    }
    else {
     //否则向右插，工作节点移到右节点
     currentNode = currentNode.right;
     if (currentNode == null) {
      parentNode.right = newNode;
      return;
     }
    }
   }
  }
  //查找最小节点
  this.min = function () {
   var p = this.root; //工作节点 
   while (p != null && p.left != null) {
    p = p.left;
   }
   return p;
  }
  //查找最大节点
  this.max = function () {
   var p = this.root; //工作节点 
   while (p != null && p.right != null) {
    p = p.right;
   }
   return p;
  }
  //中序遍历
  this.inOrder = function (rootNode) {
   if (rootNode != null) {
    this.inOrder(rootNode.left); //先左节点
    println(rootNode.data); //再根节点
    this.inOrder(rootNode.right); //再右节点
   }
  }
  //先序遍历
  this.preOrder = function (rootNode) {
   if (rootNode != null) {
    println(rootNode.data); //先根
    this.preOrder(rootNode.left); //再左节点
    this.preOrder(rootNode.right); //再右节点
   }
  }
  //后序遍历
  this.postOrder = function (rootNode) {
   if (rootNode != null) {
    this.postOrder(rootNode.left); //先左节点
    this.postOrder(rootNode.right); //再右节点
    println(rootNode.data); //再根节点
   }
  }
 }
 //以下是测试
 var bTree = new BinarySearchTree();
 //《沙特.算法设计技巧与分析》书上图3.9 左侧的树
 bTree.insert(6);
 bTree.insert(3);
 bTree.insert(8);
 bTree.insert(1);
 bTree.insert(4);
 bTree.insert(9);
 println('中序遍历：')
 bTree.inOrder(bTree.root);
 println("<br/>");
 println("先序遍历：");
 bTree.preOrder(bTree.root);
 println("<br/>");
 println("后序遍历：");
 bTree.postOrder(bTree.root);
 println("<br/>");
 var minNode = bTree.min();
 println("最小节点：" + (minNode == null &#63; "不存在" : minNode.data));
 println("<br/>");
 var maxNode = bTree.max();
 println("最大节点：" + (maxNode == null &#63; "不存在" : maxNode.data));
// ]]>
</script>
<!--中序遍历： 1 3 4 6 8 9 <br> 先序遍历： 6 3 1 4 8 9 <br> 后序遍历： 1 4 3 9 8 6 <br> 最小节点：1 <br> 最大节点：9-->

출력 결과:

中序遍历： 1 3 4 6 8 9 
先序遍历： 6 3 1 4 8 9 
后序遍历： 1 4 3 9 8 6 
最小节点：1 
最大节点：9

이 기사가 JavaScript 프로그래밍에 종사하는 모든 사람에게 도움이 되기를 바랍니다.