javascript数据结构之二叉搜索树实现方法

本文实例讲述了javascript二叉搜索树实现方法。分享给大家供大家参考,具体如下:

二叉搜索树:顾名思义,树上每个节点最多只有二根分叉;而且左分叉节点的值 < 右分叉节点的值 。

特点:插入节点、找最大/最小节点、节点值排序 非常方便

二叉搜索树-javascript实现

<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 ? "不存在" : minNode.data));
 println("<br/>");
 var maxNode = bTree.max();
 println("最大节点:" + (maxNode == null ? "不存在" : 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程序设计有所帮助。

时间: 2015-11-22

Javascript实现从小到大的数组转换成二叉搜索树

废话不多说了,直接给大家贴代码了,具体代码如下所示: var Array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; var Tree = createTree(Array); console.log(Tree); // 构造一个节点 function Node(nodeData, leftData, rightData) { this.nodeData = nodeData; this.leftData = leftData; this.rightData = rig

javascript算法之二叉搜索树的示例代码

什么是二叉树 二叉树就是树的每个节点最多只能有两个子节点 什么是二叉搜索树 二叉搜索树在二叉树的基础上,多了一个条件,就是二叉树在插入值时,若插入值比当前节点小,就插入到左节点,否则插入到右节点:若插入过程中,左节点或右节点已经存在,那么继续按如上规则比较,直到遇到一个新的节点. 二叉搜索树的特性 二叉搜索树由于其独特的数据结构,使得其无论在增删,还是查找,时间复杂度都是O(h),h为二叉树的高度.因此二叉树应该尽量的矮,即左右节点尽量平衡. 二叉搜索树的构造 要构造二叉搜索树,首先要构造二叉树

C语言判定一棵二叉树是否为二叉搜索树的方法分析

本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法.分享给大家供大家参考,具体如下: 问题 给定一棵二叉树,判定该二叉树是否是二叉搜索树(Binary Search Tree)? 解法1:暴力搜索 首先说明一下二叉树和二叉搜索树的区别.二叉树指这样的树结构,它的每个结点的孩子数目最多为2个:二叉搜索树是一种二叉树,但是它有附加的一些约束条件,这些约束条件必须对每个结点都成立: 结点node的左子树所有结点的值都小于node的值. 结点node的右子树所有结点的值都大于node的值. 结点n

Python二叉搜索树与双向链表转换算法示例

本文实例讲述了Python二叉搜索树与双向链表转换算法.分享给大家供大家参考,具体如下: 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 普通的二叉树也可以转换成双向链表,只不过不是排序的 思路: 1. 与中序遍历相同 2. 采用递归,先链接左指针,再链接右指针 代码1,更改doubleLinkedList,最后返回list的第一个元素: class TreeNode: def __init__(self, x): s

C#二叉搜索树插入算法实例分析

本文实例讲述了C#二叉搜索树插入算法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data; } } public void

Python实现查找二叉搜索树第k大的节点功能示例

本文实例讲述了Python实现查找二叉搜索树第k大的节点功能.分享给大家供大家参考,具体如下: 题目描述 给定一个二叉搜索树,找出其中第k大的节点 就是一个中序遍历的过程,不需要额外的数组,便利到节点之后,k减一就行. 代码1 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def __init__(self): self.k = 0 de

Python实现二叉搜索树BST的方法示例

二叉排序树(BST)又称二叉查找树.二叉搜索树 二叉排序树(Binary Sort Tree)又称二叉查找树.它或者是一棵空树:或者是具有下列性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于根结点的值: 2.若右子树不空,则右子树上所有结点的值均大于根节点的值: 3.左.右子树也分别为二叉排序树. 求树深度 按序输出节点值(使用中序遍历) 查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置.时间复杂度是O(h),h是树的高度. 递归/迭代求最大关键字元素 递归/迭代求最小关

Python二叉搜索树与双向链表转换实现方法

本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

Python实现二叉搜索树

二叉搜索树 我们已经知道了在一个集合中获取键值对的两种不同的方法.回忆一下这些集合是如何实现ADT(抽象数据类型)MAP的.我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈希表.在这一节中,我们将要学习二叉搜索树,这是另一种键指向值的Map集合,在这种情况下我们不用考虑元素在树中的实际位置,但要知道使用二叉树来搜索更有效率. 搜索树操作 在我们研究这种实现方式之前,让我们回顾一下ADT MAP提供的接口.我们会注意到,这种接口和Python的字典非常相似. Map() 创建了一个新的