精华内容
下载资源
问答
  • 二叉搜索树建立

    2021-03-09 14:51:26
    // BinaryTree2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include #include using namespace std; struct BinaryNode { int val;... 验证方法:二叉搜索树的中序遍历是有序的
    // BinaryTree2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include <iostream>
    #include<vector>
    using namespace std;
    
    struct BinaryNode {
    	int val;
    	BinaryNode* left;
    	BinaryNode* right;
    	
    	BinaryNode(int x) :val(x), left(NULL), right(NULL) {}
    };
    BinaryNode* insert(BinaryNode* &t, int data)
    {
    	if (t == NULL)
    	{
    		t = new BinaryNode(data);
    		
    	}
    	else if (data < t->val)
    	{
    		t->left = insert(t->left, data);
    	}
    	else if (data > t->val)
    	{
    		t->right = insert(t->right, data);
    	}
    	else
    	{
    		cout << "重复不操作" << endl;
    	}
    	return t;
    }
    void recursion(BinaryNode* root)
    {
    	if (root == NULL) return;
    	else
    	{
    		cout << root->val << ",";
    		recursion(root->left);
    		recursion(root->right);
    	}
    }
    int main()
    {
    	vector<int>v = { 2,8,7,1,4,3 };
    	BinaryNode* root = new BinaryNode(2);
    	//直接给根节点赋值,后续就只需要从1位置开始插入
    	for (int i = 1;i<v.size();i++)
    	{
    		cout << v[i] << ' ';
    		insert(root, v[i]);
    	}
    	recursion(root);
    
    	system("pause");
    	return 0;
    }
    
    
    

    缺点:
    序列的第一个元素是根节点(例:8),如果后续元素都比根节点小(6,5,4,3)就会形成只有左子树的二叉树,且深度一直增加。
    验证方法:二叉搜索树的中序遍历是有序的

    展开全文
  • 二叉排序树(BST)又称二叉查找树、二叉搜索树二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树;或者是具有下列性质的二叉树:1.若左子树不空,则左子树上所有结点的值均小于根结点的值;2.若右子树不...

    二叉排序树(BST)又称二叉查找树、二叉搜索树

    二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树;或者是具有下列性质的二叉树:

    1.若左子树不空,则左子树上所有结点的值均小于根结点的值;

    2.若右子树不空,则右子树上所有结点的值均大于根节点的值;

    3.左、右子树也分别为二叉排序树。

    求树深度

    按序输出节点值(使用中序遍历)

    查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置。时间复杂度是O(h),h是树的高度。

    递归/迭代求最大关键字元素

    递归/迭代求最小关键字元素

    # -*- coding:utf-8 -*-

    '''

    用Python实现二叉搜索树。

    '''

    class Node():

    def __init__(self, x):

    self.val = x

    self.left = None

    self.right = None

    #求树的深度

    def depth(root):

    if root is None:

    return 0

    else:

    return 1 + max(depth(root.left), depth(root.right))

    #按序输出结点值(中序遍历)

    def input_in_order(root):

    if root is None:

    return

    input_in_order(root.left)

    print(root.val)

    input_in_order(root.right)

    #(递归实现 、迭代实现)查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置。时间复杂度是O(h),h是树的高度。

    #递归实现

    def search1(root, value):

    if root is None or root.val == value:

    return root

    if root.val > value:

    return search1(root.left, value)

    if root.val < value:

    return search1(root.right, value)

    #迭代实现

    def search2(root, value):

    while root != None and root.val != value:

    if root.val > value:

    root = root.left

    elif root.val < value:

    root = root.right

    return root

    #求最大关键字元素

    #迭代实现

    def max_value1(root):

    while root != None and root.left != None:

    root = root.right

    if root is None:

    return root

    else:

    return root.val

    #递归实现

    def max_value2(root):

    if root == None:

    return root

    elif root.right == None:

    return root.val

    else:

    return max_value2(root.right)

    #求最小关键字元素

    #递归实现

    def min_value1(root):

    if root is None:

    return root

    elif root.left is None:

    return root.val

    else:

    return min_value1(root.left)

    #迭代实现

    def min_value2(root):

    if root is None:

    return root

    while root.left !=None:

    root = root.left

    return root.val

    if __name__ == '__main__':

    a = Node(15)

    b = Node(6)

    c = Node(18)

    d = Node(4)

    e = Node(8)

    f = Node(17)

    g = Node(20)

    h = Node(13)

    i = Node(9)

    a.left = b

    a.right = c

    b.left = d

    b.right = e

    c.left = f

    c.right = g

    e.right = h

    h.left = i

    print(search1(a, 13))

    print(search2(a,13))

    print(max_value1(a))

    print(max_value2(a))

    print(min_value1(a))

    print(min_value2(a))

    ps:从二叉查找树BST中查找元素X,返回其所在结点的地址,查找的次数取决于树的高度。

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

    本文标题: Python实现二叉搜索树BST的方法示例

    本文地址: http://www.cppcns.com/jiaoben/python/267098.html

    展开全文
  • 二叉查找树或者是一棵空树,或者是具有下列性质的二叉树:...二叉搜索树不一定是完全二叉树,因此不能像堆一样可以数组表示。定义一个TNode类来实例化节点,有key,value,l_child,r_child属性。其中key,value通过构造...

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

    二叉搜索树不一定是完全二叉树,因此不能像堆一样可以数组表示。

    定义一个TNode类来实例化节点,有key,value,l_child,r_child属性。其中key,value通过构造函数传入,l_child,r_child初始化为None。

    再定义一个BSTree类,根节点初始化为None。

    然后给BSTree添加以下方法:

    insert(key,value) 插入一个节点

    update(key,value) 更新节点的值

    search(key) 通过key来找相应节点的value

    remove(key) 通过key来删除树中相应节点

    以及深度优先和广度优先的遍历方法。

    insert:

    传入参数key,value,插入一个新的节点。但是如果树中已经存在key为key的节点,就将插入操作转变为更新操作。

    def __insert(self, key, value, curr_node):

    if curr_node is None:

    return TNode(key, value)

    if key < curr_node.key:

    curr_node.l_child = self.__insert(key, value, curr_node.l_child)

    elif key > curr_node.key:

    curr_node.r_child = self.__insert(key, value, curr_node.r_child)

    else:

    curr_node.value = value

    return curr_node

    当当前的节点为None时,根据参数中的key和value建立新的节点,并返回这个节点。当key值小于当前节点的key时,将新节点插入到当前节点的左子树的相应位置,然后返回当前节点。同理key值大于当前节点的key时,将新节点插入到当前节点的右子树的相应位置,返回当前节点。如果key等于当前节点key,将插入操作改变为更新操作。

    search:

    def __search(self, node, key):

    if node:

    if node.key == key:

    return node

    elif node.key > key:

    return self.__search(node.l_child, key)

    else:

    return self.__search(node.r_child, key)

    return False

    在当前node为根节点的子树中,查找key为key的子节点,如果当前node的key值与参数相同,返回当前节点。否则递归地到左右子树中找key为key的节点,如果没有找到,最终返回False。

    update:

    def __update(self, key, value, node):

    if node:

    if node.key == key:

    node.value = value

    elif node.key > key:

    self.__update(key, value, node.l_child)

    else:

    self.__update(key, value, node.r_child)

    在当前node为根节点的子树中,查找key为key的节点。如果当前node的key值与参数相同,更新当前节点的value。否则递归地到左右子树中找到key为key的节点,并更新value。

    remove:

    执行remove操作时,分为两种情况。

    1.当前要删除的节点没有右子节点,此时将左子节点作为当前节点,返回。

    2.当前要删除的节点(node_to_delete)有右子节点(r_child),找到右子节点下,最小的节点(r_child_smallest_child),将该节点与要删除的节点换位置。具体操作为:先拿到r_child_smallest_child,再将该节点从以r_child为根的子树中删除。再将node_to_delete的左孩子作为r_child_smallest_child的左孩子,node_to_delete的右孩子作为r_child_smallest_child的右孩子。最终将r_child_smallest_child赋给node_to_delete,并返回。

    代码如下:

    def __remove(self, node, key):

    if node:

    if node.key < key:

    node.r_child = self.__remove(node.r_child, key)

    elif node.key > key:

    node.l_child = self.__remove(node.l_child, key)

    else:

    if node.r_child is None:

    node = node.l_child

    else:

    node_r_child_smallest_child = self.__get_smallest_child(node.r_child)

    self.__remove_smallest(node.r_child)

    node_r_child_smallest_child.r_child = node.r_child

    node_r_child_smallest_child.l_child = node.l_child

    node = node_r_child_smallest_child

    return node

    return False

    其中__remove_smallest和__get_smallest_child含义分别是:删除当前节点下,最小的节点,以及获得当前节点下最小的节点。

    代码如下:

    def __remove_smallest(self, node):

    if node.l_child:

    node.l_child = self.__remove_smallest(node.l_child)

    return node

    return node.r_child

    当当前节点有左孩子时,删除左子树中最小的节点,并且返回当前节点。没有左孩子时,返回右孩子。

    def __get_smallest_child(self, node):

    if node.l_child:

    return self.__get_smallest_child(node.l_child)

    return node

    当当前节点有左孩子时,获得左子树中最小的节点。没有左孩子时,返回当前节点。

    深度优先遍历,可以选择先序遍历,中序遍历,后续遍历,以其中之一为例:

    def __l_m_r(self, node):

    if node:

    self.__l_m_r(node.l_child)

    print(node)

    self.__l_m_r(node.r_child)

    当进行广度优先遍历时,需要用到队列。

    def bfs(self):

    queue = deque()

    queue.append(self.root)

    while queue:

    node = queue.popleft()

    if node:

    l_child = node.l_child

    r_child = node.r_child

    print(node.value)

    queue.append(l_child)

    queue.append(r_child)

    以上是我所了解的二叉搜索树的基本功能

    展开全文
  • 几种遍历方式:验证二叉搜索树给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子...

    几种遍历方式:

    验证二叉搜索树

    给定一个二叉树,判断其是否是一个有效的二叉搜索树。

    假设一个二叉搜索树具有如下特征:

    节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

    示例 1:

    输入:

    2

    / \

    1   3

    输出: true

    示例 2:

    输入:

    5

    / \

    1   4

    / \

    3   6

    输出: false

    解释: 输入为: [5,1,4,null,null,3,6]。

    根节点的值为 5 ,但是其右子节点值为 4 。

    解法

    一开始想的是直接和左右值比较,但是忽略了隔层之间可能存在不符合规定的可能性,代码是错的。最后参考了别人的代码,发现别人是从上往下比较的,将每个节点往左就是最大,往右就是最小值,太机智了。还有就是在传输过程中原函数不能够传递最大最小值,又重新定义了一个函数调用遍历方法:使用中序遍历,基本上所有二叉搜索树的操作都可以这样做

    解法一:

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def validBST(self,root,small,large):

    if root==None:

    return True

    if small>=root.val or large<=root.val:

    return False

    return self.validBST(root.left,small,root.val) and self.validBST(root.right,root.val,large)

    def isValidBST(self, root):

    """

    :type root: TreeNode

    :rtype: bool

    """

    return self.validBST(root,-2**32,2**32-1)

    解法二:

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    pre=None

    def isValidBST(self, root):

    """

    :type root: TreeNode

    :rtype: bool

    """

    if root is None:

    return True

    Bool= self.isValidBST(root.left)

    if self.pre!=None:

    Bool=Bool and (self.pre.val

    self.pre=root

    Bool=Bool and self.isValidBST(root.right)

    return Bool

    二叉搜索树迭代器

    实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。

    示例:

    BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator.next(); // 返回 9 iterator.hasNext(); // 返回 true iterator.next(); // 返回 15 iterator.hasNext(); // 返回 true iterator.next(); // 返回 20 iterator.hasNext(); // 返回 false

    提示: next() 和 hasNext() 操作的时间复杂度是 O(1),并使用 O(h) 内存,其中 h 是树的高度。 你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 中至少存在一个下一个最小的数。

    解法 开始一直没想出来,一直想怎么找到输出节点后删除节点。其实可以用数组存储的。参考:https://blog.csdn.net/qq_17550379/article/details/86082379 有三种方法:

    通过遍历(中序)将二叉树的数据存放到数组中,然后每次next操作时取出最小值即可。用heapq实现最小堆将左边不断压栈,那么栈中存放的就是从大到小的值。调用next的时候,我们只需要弹出栈顶元素即可,同时我们需要将right加入栈中(非递归先序遍历二叉树的思路)

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class BSTIterator(object):

    def __init__(self, root):

    """

    :type root: TreeNode

    """

    self.root = root

    self.stack = []

    self.pushleft(self.root)

    def pushleft(self, cur):

    while cur:

    self.stack.append(cur)

    cur = cur.left

    def next(self):

    """

    @return the next smallest number

    :rtype: int

    """

    tmp = self.stack.pop()

    self.pushleft(tmp.right)

    return tmp.val

    def hasNext(self):

    """

    @return whether we have a next smallest number

    :rtype: bool

    """

    return True if self.stack else False

    # Your BSTIterator object will be instantiated and called as such:

    # obj = BSTIterator(root)

    # param_1 = obj.next()

    # param_2 = obj.hasNext()

    Search in a Binary Search Tree

    给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

    例如,

    给定二叉搜索树:

    4

    / \

    2   7

    / \

    1   3

    和值: 2 你应该返回如下子树:

    2

    / \

    1   3

    在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。

    解法 比较简单

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def searchBST(self, root, val):

    """

    :type root: TreeNode

    :type val: int

    :rtype: TreeNode

    """

    if not root:

    return None

    cur = root

    while cur:

    if val == cur.val:

    return cur

    elif val < cur.val:

    cur = cur.left

    else:

    cur = cur.right

    return None

    Insert into a Binary Search Tree

    给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

    注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

    例如,

    给定二叉搜索树:

    4

    / \

    2   7

    / \

    1   3

    和 插入的值: 5

    你可以返回这个二叉搜索树:

    4

    /   \

    2     7

    / \   /

    1   3 5

    或者这个树也是有效的:

    5

    /   \

    2     7

    / \

    1   3

    \

    4

    解法 正常的搜索,就按照叶子节点的方法插入

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def insertIntoBST(self, root, val):

    """

    :type root: TreeNode

    :type val: int

    :rtype: TreeNode

    """

    if not root:

    return TreeNode(val)

    cur = root

    while cur:

    if val < cur.val:

    if not cur.left:

    cur.left = TreeNode(val)

    return root

    else:

    cur = cur.left

    else:

    if not cur.right:

    cur.right = TreeNode(val)

    return root

    else:

    cur = cur.right

    return root

    Delete Node in a BST

    给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

    一般来说,删除节点可分为两个步骤:

    首先找到需要删除的节点; 如果找到了,删除它。 说明: 要求算法时间复杂度为 O(h),h 为树的高度。

    示例:

    root = [5,3,6,2,4,null,7]

    key = 3

    5

    / \

    3   6

    / \   \

    2   4   7

    给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。

    一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5

    / \

    4   6

    /     \

    2       7

    另一个正确答案是 [5,2,6,null,4,null,7]。

    5

    / \

    2   6

    \   \

    4   7

    解法 参考:https://blog.csdn.net/qq_39315740/article/details/89034263 删除节点主要有三种情况:

    节点只存在左子树,那么我们直接用左子树代替根节点即可;节点只存在右子树,同样地,我们直接用右子树代替根节点;同时存在左右子树是比较复杂的情况,这是我们重点关注的情况。

    这里我们优先采用右子树替换根节点的原则(当然左子树也可以)。 当我们找到需要删除的节点后,必须以右子树的最小节点(也就是右子树最左的节点)来代替被删除的节点

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def deleteNode(self, root, key):

    """

    :type root: TreeNode

    :type key: int

    :rtype: TreeNode

    """

    if not root:

    return None

    if root.val < key:

    root.right = self.deleteNode(root.right, key)

    elif root.val > key:

    root.left = self.deleteNode(root.left, key)

    else:

    if not root.left or not root.right:

    root = root.left if root.left else root.right

    else:

    cur = root.right

    while cur.left:

    cur = cur.left

    root.val = cur.val

    root.right = self.deleteNode(root.right, cur.val)

    return root

    Recover Binary Search Tree

    Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

    Example 1:

    Input: [1,3,null,null,2]

    1

    /

    3

    \

    2

    Output: [3,1,null,null,2]

    3

    /

    1

    \

    2

    Example 2:

    Input: [3,1,4,null,null,2]

    3

    / \

    1   4

    /

    2

    Output: [2,1,4,null,null,3]

    2

    / \

    1   4

    /

    3

    Follow up:

    A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

    同样使用中序遍历即可,所以还是需要定义pre节点表示前驱节点。 有两个节点颠倒了,只需要找到两个节点的位置。用n1存储第一个错位的元素,n2存储第二个,然后交换就可以了。

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def recoverTree(self, root):

    """

    :type root: TreeNode

    :rtype: None Do not return anything, modify root in-place instead.

    """

    self.n1, self.n2, self.pre = None, None, None

    self.inorder(root)

    self.n1.val, self.n2.val = self.n2.val, self.n1.val

    def inorder(self, root):

    if root ==None:

    return

    self.inorder(root.left)

    if self.pre!=None and self.pre.val > root.val:

    if self.n1 == None:

    self.n1=self.pre

    self.n2=root

    self.pre=root

    self.inorder(root.right)

    二叉搜索树中第K小的元素

    给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

    说明: 你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。

    示例 1:

    输入: root = [3,1,4,null,2], k = 1

    3

    / \

    1   4

    \

    2

    输出: 1 示例 2:

    输入: root = [5,3,6,2,4,null,null,1], k = 3

    5

    / \

    3   6

    / \

    2   4

    /

    1

    输出: 3 进阶: 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?

    解法 二叉搜索树BST,左子树不大于父节点,右子树不小于父节点,要找到第k小的数字,也就是把树整理成从小到大的顺序,也就是中序遍历。

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def kthSmallest(self, root, k):

    """

    :type root: TreeNode

    :type k: int

    :rtype: int

    """

    res = []

    self.inorder(root, res, k)

    return res[k-1]

    def inorder(self, root, res, k):

    if root:

    self.inorder(root.left, res, k)

    if len(res) >= k:

    return res

    res.append(root.val)

    self.inorder(root.right, res, k)

    Kth Largest Element in a Stream

    设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

    你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。

    示例:

    int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8 说明: 你可以假设 nums 的长度≥ k-1 且k ≥ 1。

    解法 两种解法:

    最小堆:比较简单,维护一个size为K的小顶堆,则堆顶元素即为第K大的元素。BST:给每个Node维护一个cnt,表示以它为根的树共多少节点。那么每个节点的所有右子树如果有m个节点,则该节点就是第m+1大的数。

    最小堆:

    from heapq import *

    class KthLargest(object):

    def __init__(self, k, nums):

    """

    :type k: int

    :type nums: List[int]

    """

    self.heap = nums

    self.k = k

    heapify(self.heap)

    while len(self.heap) > k:

    heappop(self.heap)

    def add(self, val):

    """

    :type val: int

    :rtype: int

    """

    if len(self.heap) < self.k:

    heappush(self.heap, val)

    elif val > self.heap[0]:

    heapreplace(self.heap, val)

    return self.heap[0]

    BST:

    class Node(object):

    def __init__(self, val):

    self.val = val

    self.cnt = 1

    self.left = None

    self.right = None

    class KthLargest(object):

    def __init__(self, k, nums):

    """

    :type k: int

    :type nums: List[int]

    """

    self.root = None

    self.k = k

    for x in nums:

    self.insert(x)

    def add(self, val):

    """

    :type val: int

    :rtype: int

    """

    self.insert(val)

    return self.get_k(self.root, self.k)

    def insert(self, x):

    if not self.root:

    self.root = Node(x)

    return

    cur = self.root

    while cur:

    cur.cnt += 1

    if x < cur.val:

    if not cur.left:

    cur.left = Node(x)

    return

    else:

    cur = cur.left

    else:

    if not cur.right:

    cur.right = Node(x)

    return

    else:

    cur = cur.right

    def get_k(self, cur, k):

    if not cur.right and k == 1:

    return cur.val

    if not cur.right:

    return self.get_k(cur.left, k - 1)

    if cur.right.cnt == k - 1:

    return cur.val

    if cur.right.cnt >= k:

    return self.get_k(cur.right, k)

    else:

    return self.get_k(cur.left, k - cur.right.cnt - 1)

    # Your KthLargest object will be instantiated and called as such:

    # obj = KthLargest(k, nums)

    # param_1 = obj.add(val)

    二叉搜索树的最近公共祖先

    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

    例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]  示例 1:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

    说明:

    所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def lowestCommonAncestor(self, root, p, q):

    """

    :type root: TreeNode

    :type p: TreeNode

    :type q: TreeNode

    :rtype: TreeNode

    """

    if root.val == p.val or root.val == q.val:

    return root

    if (p.val < root.val and q.val > root.val) or (q.val < root.val and p.val > root.val):

    return root

    if p.val < root.val and q.val < root.val:

    return self.lowestCommonAncestor(root.left, p, q)

    else:

    return self.lowestCommonAncestor(root.right, p, q)

    class Solution(object):

    def lowestCommonAncestor(self, root, p, q):

    """

    :type root: TreeNode

    :type p: TreeNode

    :type q: TreeNode

    :rtype: TreeNode

    """

    pointer = root

    while pointer:

    if q.val < pointer.val and p.val < pointer.val:

    pointer = pointer.left

    elif q.val > pointer.val and p.val > pointer.val:

    pointer = pointer.right

    else:

    return pointer

    将有序数组转换为二叉搜索树

    将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    示例:

    给定有序数组: [-10,-3,0,5,9],

    一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

    0

    / \

    -3   9

    /   /

    -10  5

    解法 数组nums是一个升序数组,所以根节点的位置一定是m = len(nums)//2 nums中索引值小于m的树都位于根节点的左子树上,而另一半位于根节点的右子树上,然后进行递归调用。

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def sortedArrayToBST(self, nums):

    """

    :type nums: List[int]

    :rtype: TreeNode

    """

    if not nums:

    return None

    mid = len(nums) // 2

    root = TreeNode(nums[mid])

    root.left = self.sortedArrayToBST(nums[:mid])

    root.right = self.sortedArrayToBST(nums[mid + 1:])

    return root

    不同的二叉搜索树

    给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

    示例:  解法 动态规划:假设n个节点存在二叉排序树的个数是G(n),因为根节点值不同,形成的二叉搜索树就不同,那么[1:n]范围内的n个数就有n个不同的选择 假设选取i作为根节点值,根据二叉搜索树的规则,[1:i−1]这i-1个数在其左子树上,[i+1:n]这n-i个数在其右子树上;对于左子树,又可以采用上述方法进行分解;对于右子树,同样可以采用上述方法进行分解。 让G(n)表示由连续的n个数形成的二叉搜索树的个数。所以当x为根节点时,其左子树节点个数为x - 1个,右子树节点为n - x,即f(i) = G(x - 1) * G(n - x),需要对G(0)和G(1)特殊处理,令其为1,即G(0)=G(1)=1

    具体做法:让i表示连续i个数,dp[i]表示连续i个数能形成的BST的个数;j表示根节点的位置;最后返回dp[n]即可

    class Solution:

    def numTrees(self, n: 'int') -> 'int':

    '''

    '''

    dp = [0] * (n+1)

    dp[0],dp[1] = 1,1

    #状态转移公式:dp(n) = dp(0)*dp(n-1)+dp(1)*dp(n-2)+...+dp(n-1)*dp(0)

    for i in range(2,n+1):

    for j in range(i):

    dp[i] += dp[j] * dp[i-j-1]

    return dp[n]

    不同的二叉搜索树 II

    给定一个整数 n,生成所有由 1 … n 为节点所组成的二叉搜索树。

    示例:

    输入: 3

    输出:

    [

    [1,null,3,2],

    [3,2,null,1],

    [3,1,null,null,2],

    [2,1,3],

    [1,null,2,null,3]

    ]

    解释:

    以上的输出对应以下 5 种不同结构的二叉搜索树:

    1         3     3      2      1

    \       /     /      / \      \

    3     2     1      1   3      2

    /     /       \                 \

    2     1         2                 3

    解法 类似于上一题,从序列 1 …n 取出数字 i 并以它作为当前树的根节点。 那么就有 i - 1 个元素可以用来构造左子树,而另外的 n - i 个元素可以用于构造右子树。最后我们将会得到 G(i - 1) 棵不同的左子树,以及 G(n - i) 棵不同的右子树。 所以可以使用递归的方法,在序列 1 … i - 1 上重复前面的步骤来构造所有的左子树,之后对序列 i + 1 … n 也这样做以得到所有的右子树。 这么一来,我们就得到了根节点 i 和两个可能的左右子树列表。 最后一步是遍历两个列表,将左右子树和根节点链接起来。

    注意:边界值的处理;属于排列组合的算法

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution:

    def generateTrees(self, n):

    """

    :type n: int

    :rtype: List[TreeNode]

    """

    def generate_trees(start, end):

    if start > end:

    return [None,]

    all_trees = []

    for i in range(start, end + 1):  # pick up a root

    # all possible left subtrees if i is choosen to be a root

    left_trees = generate_trees(start, i - 1)

    # all possible right subtrees if i is choosen to be a root

    right_trees = generate_trees(i + 1, end)

    # connect left and right subtrees to the root i

    for l in left_trees:

    for r in right_trees:

    current_tree = TreeNode(i)

    current_tree.left = l

    current_tree.right = r

    all_trees.append(current_tree)

    return all_trees

    return generate_trees(1, n) if n else []

    二叉搜索树的后序遍历序列

    题目描述:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

    解法 后序遍历中,最后一个数字是根结点的值,数组的前面数字部分可分为两部分,一部分是左子树,一部分是右子树。我们根据二叉搜索树的性质可知,左子树的值要比根节点小,而右子树所有值要比根节点大。以此递归来判断所有子树。

    # -*- coding:utf-8 -*-

    class Solution:

    def VerifySquenceOfBST(self, sequence):

    # write code here

    if not sequence:

    return False

    else:

    return self.verify(sequence)

    def verify(self, sequence):

    if not sequence:

    return True

    # 根节点就是最后一个树,获取一下这个值,然后从数组中弹出去

    root = sequence.pop()

    # 找一下左右子树

    index = self.findIndex(sequence, root)

    # 细分到没有子结点作为终止条件

    if not sequence[index:]:

    return True

    # 如果右边数组最小值都大于root,则说明没有问题。进一步细分

    elif min(sequence[index:]) > root:

    left = sequence[:index]

    right = sequence[index:]

    return self.verify(left) and self.verify(right)

    return False

    # 定义一个函数,来找到左右子树的分界线

    # 左子树的值比根节点小,右子树的值比根节点大,以此为左右子树的界限

    def findIndex(self, sequence, root):

    for i, seq in enumerate(sequence):

    if sequence[i]>root:

    return i

    return len(sequence)

    二叉搜索树与双向链表

    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

    解法 参考:https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5?answerType=1&f=discussion

    辅助数组:最容易想到的,是用一个数组来存储中序遍历的节点,然后再从头到尾,建立节点前后的连接关系。线索化二叉树:因为二叉排序树中序遍历的结果是排好序的,很容易联想到用线索化二叉树的方法去做,用一个全局变量去保存前一个节点,然后再去创建节点之间的关系。只要pre不空,就创建关系,创建后就是链表了。但是要注意,返回的双向链表是降序排列的,那我们有两种解决方法,第一种是再遍历一遍得到的结果,将节点的最后一个结果返回。第二种是设置一个变量来记录。优化:我们受到惯性思维的约束,每次都是想着中序遍历先遍历左子树,再遍历根节点,再遍历右子树。那既然第二种方法得到的二叉树是降序的,那我先遍历右子树,再遍历根节点,再遍历左子树不就可以了么

    方法二:

    class Solution:

    def __init__(self):

    self.pre = None

    self.root = None

    def Convert(self, pRootOfTree):

    # write code here

    if not pRootOfTree:

    return None

    self.Convert(pRootOfTree.left)

    if self.root == None:

    self.root = pRootOfTree

    if self.pre:

    pRootOfTree.left = self.pre

    self.pre.right = pRootOfTree

    self.pre = pRootOfTree

    self.Convert(pRootOfTree.right)

    return self.pre

    方法三:

    # -*- coding:utf-8 -*-

    # class TreeNode:

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution:

    def __init__(self):

    self.pre = None

    def Convert(self, pRootOfTree):

    # write code here

    if pRootOfTree == None:

    return None

    self.Convert(pRootOfTree.right)

    if self.pre != None:

    pRootOfTree.right = self.pre

    self.pre.left = pRootOfTree

    self.pre = pRootOfTree

    self.Convert(pRootOfTree.left)

    return self.pre

    二叉搜索树转换成循环双向链表

    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。  我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

    下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。  特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

    解法 同上,两类方法

    进行中序遍历的时候,将所有 node 存放在一个数组中,依次遍历数组,改造 right 指针指向下一个元素,left 指针指向前一个元素,单独处理首尾的连接为了能够完成双向的指向,我们必须同时有两个 node。让第一个 node 的 right 指向第二个 node,同时让第二个 node 的 left 指向第一个node。第一个 node 使用一个全局遍历 self.pre,第二个 node 使用当前点 root。

    方法一:

    class Solution:

    def __init__(self):

    self.list = []

    def inOrderTraverse(self, root):

    if not root:

    return None

    self.inOrderTraverse(root.left)

    self.list.append(root)

    self.inOrderTraverse(root.right)

    def treeToDoublyList(self, root: 'Node') -> 'Node':

    if not root:

    return None

    self.inOrderTraverse(root)

    l = len(self.list)

    for i in range(l-1):

    self.list[i].right = self.list[i+1]

    self.list[l-1-i].left = self.list[l-2-i]

    self.list[l-1].right = self.list[0]

    self.list[0].left = self.list[l-1]

    return self.list[0]

    方法二:

    class Solution:

    def __init__(self):

    self.pre = None

    self.head = None

    def inOrderTraverse(self, root):

    if not root:

    return None

    # left DFS

    self.inOrderTraverse(root.left)

    if self.pre == None:

    self.pre = root

    self.head = root # This is the left most node -> head

    else:

    self.pre.right = root   # Pre.right -> current node

    root.left = self.pre    # current node.left -> pre

    self.pre = root         # change pre to current node

    # right DFS

    self.inOrderTraverse(root.right)

    def treeToDoublyList(self, root: 'Node') -> 'Node':

    if not root:

    return None

    # Inorder traverse

    self.inOrderTraverse(root)

    # Link head and tail

    self.head.left = self.pre

    self.pre.right = self.head

    return self.head

    二叉搜索树序列

    从左向右遍历一个数组,通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树,输出所有可能生成此树的数组。

    示例: 给定如下二叉树

    2

    / \

    1   3

    返回:

    [ [2,1,3], [2,3,1] ]

    解法  会出现这样的一个结果 [[3,0,1,2,4],[3,0,1,4,2],[3,0,4,1,2],[3,4,0,1,2]] 我们发现其实并不是每个节点的后面都是他的一个子节点,0后面也可能出现4,1后面也可能出现4,…,说明左右节点也可以交替出现!

    具体做法:

    3这个节点的左右节点[0, 4],那么下一个节点就要在[0, 4]中选择如果下个节点是0,其左右节点[1], 那么0后面的节点可能有哪些呢?–> [4]+[1]如果下个节点是4,没有子节点[ ], 那么1后面的节点可能有哪些呢?–> [0]+[]

    所以还是dfs递归全排列的方法:除了res和tmp外,还需要多加一个queue的队列,用来存储左右子节点。

    # Definition for a binary tree node.

    # class TreeNode(object):

    #     def __init__(self, x):

    #         self.val = x

    #         self.left = None

    #         self.right = None

    class Solution(object):

    def BSTSequences(self, root):

    """

    :type root: TreeNode

    :rtype: List[List[int]]

    """

    if not root:

    return [[]]

    res, queue = [], []

    tmp = [root.val]

    self.dfs(root, queue, tmp, res)

    return res

    def dfs(self, root, queue, tmp, res):

    if root.left:

    queue.append(root.left)

    if root.right:

    queue.append(root.right)

    if not queue:

    res.append(tmp)

    return

    for i, node in enumerate(queue):

    self.dfs(node, queue[:i] + queue[i + 1:], tmp + [node.val], res)

    展开全文
  • 题目难度:★☆☆☆☆类型:二叉树给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。例如,给定二叉搜索树:4/ \2 7/ \1 3...
  • 练习 20:二叉搜索树译者:飞龙自豪地采用谷歌翻译在本练习中,我将让你将数据结构的中文描述翻译成工作代码。你已经知道如何使用“大师复制”方法,分析算法或数据结构的代码。你还可以了解如何阅读算法的伪代码...
  • 原标题:二叉查找的增加,删除,遍历 python本文主要使用python实现二叉查找的如下部分:二叉查找构造二叉查找插入二叉查找遍历二叉查找删除二叉查找是一颗二叉树,并且基本数据结构要求满足如下条件...
  • 有关二叉搜索树的概念以及二叉树中常用的一些基本的操作:删除 增加 查找
  • 一、二叉搜索树**二叉搜索树(BST binary searchtree)**是一种比较特殊的二叉树,表现为任意节点的值都比左孩子的值要大,而且小于等于右孩子的值,采用中序遍历BST(BinarySearch Tree)就可以的到排序好的元素集合,...
  • * 功能:二叉搜索树 * author:xjp */ typedef struct _NODE{ int value; struct _NODE *left; struct _NODE *right; }NODE; NODE *insertBST(NODE *BST, int value){ //新建一个节点 NODE *tmp = (NODE *)...
  • }else if (t->ivalue ){ // 如果比当前结点大,则插入右子 t->pright = create_searchtree(t->pright, temp); } return t; } node * creat_bitree(int value[], int len) //非递归方式 { int i, ...
  • #include #include #include #include #include #include #include #include #include #include #include #i
  • 1.二叉搜索树建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)
  • 今天PAT考完试,只做出了3道题,70分。...第四题最惨,1个小时的时间,有半小时在理解题意上,很短的题目,竟然没注意到“搜索树构建”,只看到“前序序列”。。。 还有,最后其实已经写成功了,就
  • 一直以来,都对有关的东西望而却步。以前每次说要看一看,都因为惰性,时间就那么荒废掉了。今天下个决心,决定好好的数据结构中的东西看一下。不知道看这篇文章的你,是不是和我有同样的感受,空有一颗努力的心,...
  • 数据结构二叉排序树建立In everyday life, we need to find things or make decisions, and one way to make that process easier is to cut those choices in half. 在日常生活中,我们需要找到事情或做出决定,而...
  • 二叉搜索树的结构 二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;...
  • 二叉搜索树

    2016-08-10 16:07:35
    二叉搜索树建立,删结点,插入节点,遍历
  • 题目链接:http://ac.jobdu.com/problem.php?pid=1009 详解链接:... 参考代码: // // 1009 二叉搜索树.cpp // Jobdu // // Created by PengFei_Zheng on 09/04/2017. // Copyri...
  • 二叉搜索树建立

    2020-01-16 15:50:21
    二叉搜索树的概念 二叉搜索树又称二叉排序树, 最基本形态就是一颗空树,它具有以下一个性质: · 如果一个节点有左子树, 那么左子树上的节点值都小于该节点 · 如果一个节点有右子树, 那么右子树上的节点值都大于该...
  • 二叉排序树(二叉搜索树)的建立 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {....
  • 二叉搜索树建立 就是它的左子树永远比它的根结点要小,它的右子树永远比它的根节点要大。 树的结构 struct stree{ int data;//数据 struct stree* left;//左子树 struct stree *right;//右子树 }; 我做的...
  • 本周为学校的算法与数据结构实践周,博主接到的题目内容如下: 题B5:搜索树操作程序 开发建立搜索树的程序,在程序中可以进行参数设置、数据...可以对已经生成的二叉搜索树进行插入、删除和搜索操作,程序动态...
  • 二叉搜索树 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 判断两序列是否为同一二叉搜索树序列 Input 开始一个数n,(1<=n<=20) 表示有n...
  • 给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 822
精华内容 328
关键字:

二叉搜索树建立