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

    作者:mle123更新于: 2020-05-09 12:56:45

    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)).

课课家教育

未登录