动力节点旗下在线教育品牌  |  咨询热线:400-8080-105 学Java全栈,上蛙课网
首页 > 文章

java二叉查找树面试题(附答案)

08-19 17:08 238浏览
举报 T字号
  • 大字
  • 中字
  • 小字

树的形状大家都知道,是向上一节一节开树杈的,作为数据结构的树也是类似的,只不过我们通常将它倒着画。树的应用也相当广泛,例如在文件系统,数据库索引中的应用等。下面整理了java二叉查找树面试题,在学习java查找树的朋友们向下看看吧。

1、java二叉查找树是什么?

答:二叉查找树就是左结点小于根节点,右结点大于根节点的一种排序树,也叫二叉搜索树。也叫BST,英文Binary Sort Tree。二叉查找树比普通树查找更快,查找、插入、删除的时间复杂度为O(logN)。

2、二叉查找树操作有什么?

答:二叉查找树常见操作有插入,查找,删除以及遍历。而实际上二叉查找树既可以使用数组来实现,也可以使用链表,本文采用链表来实现。另外本文也排除了两个节点存在相同值的情况。

3、介绍树的基本名词有哪些?

答:(1根节点:root节点没有父节点,我们把它称为根节点;(2父节点:如b节点的父节点为root节点;(3子节点:在图中,root有三个孩子,分别是b,c,d,它们都是root的子节点;(4兄弟节点:b有两个兄弟节点,c,d,因为它们有相同的父节点root;(5叶子节点:e f等节点,它们没有子节点,因此是叶子节点。

4、二叉树的最主要特点是什么?

答:(1)每个结点的度都大于2;(2)每个结点的孩子结点次序不能任意颠倒,即有左右孩子之分。

5、二叉树的性质有什么?

答:(1)若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有 2^(i-1)个结点;(2)若规定只有根节点的二叉树的深度为1,则深度为K的二叉树的最大结点数是 (2^k)-1;(3)对任意一棵二叉树T,若终端节点数为n0,而其度数为2的节点树为n2,则n0 = n2+1;(4)具有n个结点的完全二叉树的深度为lgN+1。

6、创建一个二叉树

答:思路是已前序遍历的特点来创建二叉树,如果没有左右孩子就用"#"来表示。注意:递归调用时_CreatBinaryTree()的参数pRoot 和index数组下标为引用。

BinaryTree(const T array[], size_t size)
		:_pRoot(NULL)
	{
		size_t index = 0;
		_CreatBinaryTree(_pRoot, array, size, index);
	}
	void _CreatBinaryTree(BinaryTreeNode*& pRoot,const T array[], size_t size, size_t& index) 
	{ 
		if (index < size && '#' != array[index])
		{
			pRoot = new BinaryTreeNode(array[index]);
			_CreatBinaryTree(pRoot->_pLeftChild,array,size,++index);
		_CreatBinaryTree(pRoot->_pRightChild,array,size,++index);
		}
}

7、在二叉搜索树中查找一个结点

答:思路根据二叉搜索树根节点大于左子树结点,但是小于右子树结点的特点,和给定值比较,如果根结点的值小于给定值,必然在右子树,然后在在右子树里继续比较查找;如果根结点的值大于给定值,必然在左子树中,然后在左子树里继续比较查找。

代码如下:

//查找一个结点
//根据二叉搜索树的特点,左树都小于根节点,右树都大于根节点的特点和已知值相比遍历二叉搜索树来查找
//这里直接给一级指针也可以,为了和上边操作统一才弄得二级指针
BSTreeNode* BSTreeFind(BSTreeNode** root, BSTDataType x)
{
    assert(root);
    BSTreeNode* cur = *root;
    while (cur)
    {
        //x大于当前结点,必然在右树
        if (cur->_data < x)
        {
            cur = cur->_right;
        }
        //x小于当前结点,必然在左树
        else if (cur->_data>x)
        {
            cur = cur->_left;
        }
        else
        {
            //相等则返回它的指针
            return cur;
        }
    }
    //遍历结束则没有找到,返回NULL
    return NULL;
}

8、中序遍历二叉搜索树

答:思路是递归遍历,先递归遍历左子树,在访问根结点,最后递归遍历右子树。

代码如下:

中序遍历二叉搜索树(递归)
void BSTreeInOrder(BSTreeNode** root)
{
    assert(root);
    //根为空,直接返回
    if ((*root) == NULL)
    {
        return;
    }
    //递归遍历左子树
    BSTreeInOrder(&(*root)->_left);
    //访问根结点
    printf("%d ", (*root)->_data);
    //递归遍历右子树
    BSTreeInOrder(&(*root)->_right);
}

以上8道题目就是java二叉查找树面试题,在java面试中对于二叉查找树知识的考察是很基础的,更深入的内容只会在实际操作中体现出来,所以希望大家平时在学习完java培训课程后要多加练习,尤其java零基础的朋友们一定不能眼高手低的学习java,学习java二叉查找树。希望这篇java二叉查找树面试题可以帮助大家顺利通过面试。

0人推荐
共同学习,写下你的评论
0条评论
谨慎的老王
程序员谨慎的老王

6篇文章贡献19329字

作者相关文章更多>

推荐相关文章更多>

Java数据结构

HelloWorld10-31 08:24

浅谈MySQL中SQL优化的常用方法

军哥08-12 23:29

五分钟读懂UML类图

江湖人称小李白12-10 10:41

MyBatis开发框架的四大核心

IT逐梦者08-17 21:43

一次搞定continue,break和return

HelloWorld11-06 11:19

发评论

举报

0/150

取消