下载安卓APP箭头
箭头给我发消息

客服QQ:3315713922

Web前端:树---二叉搜索树的第K个节点

作者:mle123     来源: 博客园点击数:1091发布时间: 2020-05-09 12:56:49

标签: 数据结构Web前端Web开发

Web开发

  树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示。

  树在计算机领域中也得到广泛应用,如在编译源程序如下时,可用树表示源源程序如下的语法结构。又如在数据库系统中,树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树,完全二叉树,排序二叉树。

  二叉查找树(BinarySearchTree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

  给定一棵二叉搜索树,请找出其中的第k小的结点。例如,(5,3,7,2,4,6,8)中,按结点数值大小顺序第三小结点的值为4。

  分析:二叉搜索树就是每个节点X,大于其左子树的值,小于其右子树的值,其中序排序是递增的。使用中序遍历,每遍历一个节点,k-1,直到k减到1,即为第K小的节点

  /*functionTreeNode(x){

  this.val=x;

  this.left=null;

  this.right=null;

  }*/

  functionKthNode(pRoot,k){

  if(pRoot===null||k===0){

  returnnull;

  }

  //为了能追踪k,应该把KthNodeCore函数定义在这里面,k应该在KthNodeCore函数外面

  functionKthNodeCore(pRoot){

  lettarget=null;

  if(pRoot.left!==null){

  target=KthNodeCore(pRoot.left,k);

  }

  if(target===null){

  if(k===1){

  target=pRoot;

  }

  k--;

  }

  if(target===null&&pRoot.right!==null){

  target=KthNodeCore(pRoot.right,k);

  }

  returntarget;

  }

  returnKthNodeCore(pRoot);

  }

  二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。

  每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索,插入,删除的复杂度等于树高,O(log(n)).

赞(0)
踩(0)
分享到:
华为认证网络工程师 HCIE直播课视频教程