树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示。
树在计算机领域中也得到广泛应用,如在编译源程序如下时,可用树表示源源程序如下的语法结构。又如在数据库系统中,树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树,完全二叉树,排序二叉树。
二叉查找树(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)).
¥99.00
¥39.00
¥59.00