精华内容
下载资源
问答
  • 2020-01-14 14:20:22

    中序遍历解决二叉搜索树问题

    Python3

    深度优先搜索

    通过中序遍历二叉搜索树得到的关键码序列是一个递增序列。
    这是二叉搜索树的一个重要性质,巧妙利用这一性质可以解决一系列二叉搜索树问题。
    本系列以以下非递归中序遍历代码为核心,解决一系列相关问题。

    p = root
    st = []  # 用列表模拟实现栈的功能
    while p is not None or st:
        while p is not None:
            st.append(p)
            p = p.left
        p = st.pop()
        proc(p.val)
        p = p.right
    

    一 二叉搜索树迭代器
    (一)算法思路
    中序遍历二叉树
    (二)算法实现

    class BSTIterator:
    
        def __init__(self, root: TreeNode):
            self.root = root
            self.st = []
            self.current = self.root
            
    
        def next(self) -> int:
            """
            @return the next smallest number
            """
            while self.current is not None or self.st:
                while self.current is not None:
                    self.st.append(self.current)
                    self.current = self.current.left
                self.current = self.st.pop()
                node = self.current
                self.current = self.current.right
                return node.val
                
                
    
        def hasNext(self) -> bool:
            """
            @return whether we have a next smallest number
            """
            return self.current or self.st
    

    二 二叉搜索树的最小绝对差
    (一)算法思路
    中序遍历二叉搜索树,第一个结点外的每个节点与其前一节点的差值,如果该值小于最小绝对差,就用它更新最小绝对差(初始可设为无穷)。
    (二)算法实现

    class Solution:
        def getMinimumDifference(self, root: TreeNode) -> int:
            st = []
            p = root
            pre = -float('inf')
            min_val = float('inf')
            while p is not None or st:
                while p is not None:
                    st.append(p)
                    p = p.left
                p = st.pop()
                cur = p.val
                if cur - pre < min_val:
                    min_val = cur - pre
                pre = cur
                p = p.right
            return min_val
    

    (三)复杂度分析
    时间复杂度:O(N),N为树中节点个数。
    空间复杂度:O(log(N))。

    三 二叉搜索树中第k小的元素
    (一)算法思路
    二叉搜索树的中序遍历序列为递增序列,因此可中序遍历二叉搜索树,返回第K个元素。
    (二)算法实现

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def kthSmallest(self, root: TreeNode, k: int) -> int:
            st = []
            p = root
            s = 0
            while p is not None or st:
                while p is not None:
                    st.append(p)
                    p = p.left
                p = st.pop()
                s += 1
                if s == k:
                    return p.val
                p = p.right
    

    (三) 复杂度分析
    时间复杂度:O(N),N为树中节点个数。
    空间复杂度:O(log(N))。

    四 二叉搜索树中的众数
    (一) 算法思想
    二叉搜索树的中序遍历序列单调不减(或曰非严格单调递增),因此可考虑中序遍历二叉搜索树。
    用max_times记录已访问节点的最大重复元素个数,time表示当前访问节点的元素值的出现次数,用res=[]记录结果。
    若time == max_times,则将当前节点值添加到结果集。
    若time > max_times,则以当前节点值构造新的列表作为结果,并用time更新max_times。
    中序遍历结束后,返回结果res。
    (二) 算法实现

    class Solution:
        def findMode(self, root: TreeNode) -> List[int]:
            if root is None:
                return []
            p = root
            st = []
            res = []
            max_times = 1
            time = 1
            pre = float("inf")
            while p is not None or st:
                while p is not None:
                    st.append(p)
                    p = p.left
                p = st.pop()
                
                cur = p.val
                if cur == pre:
                    time += 1
                else:
                    time = 1
                    pre = cur
                if time == max_times:
                    res.append(cur)
                if time > max_times:
                    res = [cur]
                    max_times = time
        
                p = p.right
                    
            return res
    

    (三) 复杂度分析
    时间复杂度:O(N),N为树中节点个数。
    空间复杂度:最坏情况下为O(N), 例如树畸形(树的高度为线性)或每个元素出现一次的情形。

    五 二叉搜索树的范围和
    (一)算法思路
    中序遍历二叉搜索树
    当节点的值等于L时开始累加,当节点的值等于R时停止累加并返回累加的结果。
    (二)算法实现

    class Solution:
        def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
            st = []
            p = root
            s = 0
            while p is not None or st:
                while p is not None:
                    st.append(p)
                    p = p.left
                p = st.pop()
                if p.val == L:
                    s = L
                    p = p.right
                    break
                p = p.right
            
            while p is not None or st:
                while p is not None:
                    st.append(p)
                    p = p.left
                p = st.pop()
                s += p.val
                if p.val == R:
                    return s
                p = p.right
    

    (三)复杂度分析
    时间复杂度:O(N), N为树中节点数。
    空间复杂度:O(log(N))。

    六 两数之和IV-输入BST
    (一)算法思路
    中序遍历+双指针
    (二)算法实现

    class Solution(object):
        def findTarget(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: bool
            """
            nums = []
            st = []
            p = root
            while p is not None or st:
                while p is not None:
                    st.append(p)
                    p = p.left
                p = st.pop()
                nums.append(p.val)
                p = p.right
            
            n = len(nums)
            i, j = 0, n-1
            while i < j:
                if nums[i] + nums[j] == k:
                    return True
                elif nums[i] + nums[j] > k:
                    j -= 1
                else:
                    i += 1
            return False
    

    (三)复杂度分析
    时间复杂度:O(N)
    空间复杂度:O(N)

    七 验证二叉搜索树
    (一)算法思路
    一棵二叉树是二叉搜索树的充要条件是它的中序遍历序列单调递增,因此可以通过判断一个树的中序遍历序列是否单调递增来验证该树是否为二叉搜索树。
    (二)算法实现

    # 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 isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            pre = -float('inf')
            p = root
            st = []
            while p is not None or st:
                while p is not None:
                    st.append(p)
                    p = p.left
                p = st.pop()
                if p.val > pre:
                    pre = p.val
                else:
                    return False
                p = p.right
            return True
    更多相关内容
  • 本文链接:https://blog.csdn.net/m0_37609579/article/details/99687256 一、计算机科学中的树 二、二叉树的定义 一棵树,它的每节点最多只能有两个子节点,此时就叫二叉树。(我们一般在书中试题中见到的树是...

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/m0_37609579/article/details/99687256

    一、计算机科学中的树

    96fa72fbd21ee2663ae0f388e9baa037.png


    二、二叉树的定义
    一棵树,它的每个节点最多只能有两个子节点,此时就叫二叉树。(我们一般在书中试题中见到的树是二叉树,但并不意味着所有的树都是二叉树。如果节点多于两个,我们也称之为多路树)

    411a77aa2f0a5e092a4b2cedad3415e8.png

    1532f0a2a8ccfa9376dfb5033bdbac57.png

    c657c427733b911bcd9bba3e9ff98a55.png

    可以看出: 满二叉树一定是完全二叉树;完全二叉树不一定是满二叉树。
    如果我们给二叉树加一个额外的条件,就可以得到一种被称作二叉查找树(binary search tree)的特殊二叉树。
    二叉查找树要求:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。【左边下边小,右边上边大

    941c8c622703742c665e2572e559724b.png


    三、二叉查找树的日常操作
    PS:二叉树很多,但对我们来说,在实际的应用中,二叉排序树的应用比较多。1.插入新节点
    假设我们要为数组 a[] = {10 , 5 , 15 , 6 , 4 , 16 }构建一个二叉排序树,我们按顺序逐个插入元素。

    76491bece59dd8de38b0ba537a1de338.png


    插入过程是这样的:
    如果是空树,则创建一个新节点,新节点作为根,因此以元素10构建的节点为该二叉查找树的根。

    • 插入5,5比10小,与10的左孩子节点进行比较,10的左孩子节点为空,进行插入。
    • 插入15,15比10大,与10的右孩子节点进行比较,10的右孩子节点为空,进行插入。
    • 插入6,6比10小,与10的左孩子节点5比较;6比5大,与5的右孩子节点进行比较,5的右孩子为空,进行插入。
    • 插入4,4比10小,与10的左孩子节点5比较;4比5小,与5的左孩子节点进行比较,5的左孩子为空,进行插入。
    • 插入16,16比10大,与10的右孩子节点15比较;16比15大,与15的右孩子节点进行比较,15的右孩子为空,进行插入。

    从这个过程我们可以总结出插入新元素的步骤:

    • 寻找元素合适的插入位置:新元素与当前结点进行比较,若值大于当前结点,则从右子树进行寻找;否则从左子树进行寻找.
    • 找到插入位置之后,以元素的值构建新节点,插入二叉排序树中。

    2.遍历平衡二叉树
    【百度百科】平衡二叉搜索树,又被称为AVL树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    620ffd80c79390cb0e16280713fac6dd.png


    遍历平衡二叉树,就是以某种方式逐个“访问”二叉树的每一个节点。举例说明:

    e9c6c56eb5507e206be95c03b00032c9.png


    前序遍历

    • 访问根结点中的数据
    • 前序遍历左子树
    • 前序遍历右子树
      前序遍历结果:
      1, 2, 4, 8, 9, 5, 10, 3, 6, 7

    中序遍历

    • 中序遍历左子树
    • 访问根结点中的数据
    • 中序遍历右子树
      中序遍历结果:
      8, 4, 9, 2, 10, 5, 1, 6, 3, 7

    后序遍历

    • 后序遍历左子树
    • 后序遍历右子树
    • 访问根结点中的数据
      后序遍历结果:
      8, 9, 4, 10, 5, 2, 6, 7, 3, 1

    层次遍历

    • 访问根结点中的数据
    • 访问第二层所有结点的数据
    • 访问第三层所有结点的数据
    • ……
      层次遍历结果:
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10

    3.删除节点
    删除二叉排序树的某个节点有三种情况:

    • 被删除节点同时有左子树与右子树。将前驱节点的值保存在当前结点,继而删除前驱节点。
    • 被删除节点只有左子树或只有右子树。直接用子树替换被删节点。
    • 被删除节点没有子树。可以直接删除节点。

    2fa740c8ea6185dd94d41970938a090d.png

    4.查找最值元素
    二叉排序树的最小值位于其最左节点上;最大值位于其最右节点上

    ea46bde75941c88375854569a37bebb8.png


    我的微信公众号:架构真经(id:gentoo666),分享Java干货,高并发编程,热门技术教程,微服务及分布式技术,架构设计,区块链技术,人工智能,大数据,Java面试题,以及前沿热门资讯等。每日更新哦!

    886de73118a3e72a9ba4e5b40a10d245.png


    四、参考资料https://blog.csdn.net/wannuoge4766/article/details/83998377https://www.cnblogs.com/shixiangwan/p/7530015.htmlhttps://www.cnblogs.com/ysocean/p/8032642.htmlhttps://blog.csdn.net/u014634338/article/details/42465089http://www.it610.com/article/3607922.htm

    展开全文
  • 这是三个节点的二叉树的类型 类型 先序遍历 中序遍历 ...仔细观察,还缺少了一个项 ...所以,这个结论应该是先序/后序遍历+中序遍历能确定一个二叉树,一个二叉树确定遍历,但是这和这遍历没有一一对应的关系。

    这是三个节点的二叉树的类型
    在这里插入图片描述

    树类型先序遍历中序遍历
    (1)ABCCBA
    (2)ABCBCA
    (3)ABCBAC
    (4)ABCACB
    (5)ABCABC

    仔细观察,还缺少了一个项
    先序ABC,中序CAB
    此时树是这样子的
    在这里插入图片描述
    但是等等,这个树的先序可是ACB啊
    也就是说先序ABC,中序CAB与先序ACB,中序CAB确定了同一棵树
    所以,这个结论应该是先序/后序遍历+中序遍历能确定一个二叉树,一个二叉树确定遍历,但是这树和这遍历没有一一对应的关系。

    展开全文
  • 二叉树是种非常重要的数据结构,它同时具有数组和链表各自的特点:它可以像数组一样快速查找,也可以像...对于排序二叉树,若按中序遍历就可以得到由小到大的有序序列。 我们先介绍一些关于二叉树的概念名词。 ...

    二叉树是一种非常重要的数据结构,它同时具有数组和链表各自的特点:它可以像数组一样快速查找,也可以像链表一样快速添加。但是他也有自己的缺点:删除操作复杂。

    虽然二叉排序树的最坏效率是O(n),但它支持动态查找,且有很多改进版的二叉排序树可以使树高为O(logn),如AVL、红黑树等。

    对于排序二叉树,若按中序遍历就可以得到由小到大的有序序列。

    我们先介绍一些关于二叉树的概念名词。

    二叉树:是每个结点最多有两个子树的有序树,在使用二叉树的时候,数据并不是随便插入到节点中的,一个节点的左子节点的关键值必须小于此节点,右子节点的关键值必须大于或者是等于此节点,所以又称二叉查找树、二叉排序树、二叉搜索树。

    完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。

    满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

    深度——二叉树的层数,就是深度。

    二叉树的特点总结:

    (1)树执行查找、删除、插入的时间复杂度都是O(logN)

    (2)遍历二叉树的方法包括前序、中序、后序

    (3)非平衡树指的是根的左右两边的子节点的数量不一致

    (4) 在非空二叉树中,第i层的结点总数不超过 , i>=1;

    (5)深度为h的二叉树最多有个结点(h>=1),最少有h个结点;

    (6)对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

     

    排序二叉树 定义

    二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树:

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

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

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

     

    二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树可得到一个依据关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即是对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。

    搜索、插入、删除的时间复杂度等于树高,期望O(logn),最坏O(n)(数列有序,树退化成线性表,如右斜树)。

    /* 二叉树的二叉链表结点结构定义 */
    typedef  struct BiTNode    /* 结点结构 */
    {
        int data;    /* 结点数据 */
        struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
    } BiTNode, *BiTree;

     

    虽然二叉排序树的最坏效率是O(n),但它支持动态查找,且有很多改进版的二叉排序树可以使树高为O(logn),如AVL、红黑树等。

    对于排序二叉树,若按中序遍历就可以得到由小到大的有序序列。

    插入创建算法

    创建排序二叉树的步骤就是不断像排序二叉树中添加新节点(p)的过程:

    (1)以根节点(root)为当前节点(current)开始搜索;

    (2)用新节点p的值和current的值进行比较;

    (3)如果p.data>current.data,则current=current.right;若p.data<current.data,则current=current.left;

    (4)重复(2)(3),直到找到合适的叶子节点位置;

    (5)将p添加到上面找到的合适位置,若新节点更大,则添加为右子节点;否则,加为左子节点

    查找算法

    在二元排序树b中查找x的过程为:

     1.若b是空树,则搜索失败,否则:

     2.若x等于b的根节点的数据域之值,则查找成功;否则:

     3.若x小于b的根节点的数据域之值,则搜索左子树;否则:

     4.查找右子树。 

    删除算法:

    在二叉排序树中删去一个结点,分三种情况讨论:

     1.若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。

     2.若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树(当*p是左子树)或右子树(当*p是右子树)即可,作此修改也不破坏二叉排序树的特性。

     3.若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整。比较好的做法是,找到*p的直接前驱(或直接后继)*s,用*s来替换结点*p,然后再删除结点*s。

     

    代码:

    /* 若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点, */
    /* 并返回TRUE;否则返回FALSE。 */
    Status DeleteBST(BiTree *T,int key)
    { 
        if(!*T) /* 不存在关键字等于key的数据元素 */ 
            return FALSE;
        else
        {
            if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ 
                return Delete(T);
            else if (key<(*T)->data)
                return DeleteBST(&(*T)->lchild,key);
            else
                return DeleteBST(&(*T)->rchild,key);
             
        }
    }
    
    /* 从二叉排序树中删除结点p,并重接它的左或右子树。 */
    Status Delete(BiTree *p)
    {
        BiTree q,s;
        if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) */
        {
            q=*p; *p=(*p)->lchild; free(q);
        }
        else if((*p)->lchild==NULL) /* 只需重接它的右子树 */
        {
            q=*p; *p=(*p)->rchild; free(q);
        }
        else /* 左右子树均不空 */
        {
            q=*p; s=(*p)->lchild;
            while(s->rchild) /* 转左,然后向右到尽头(找待删结点的前驱) */
            {
                q=s;
                s=s->rchild;
            }
            (*p)->data=s->data; /*  s指向被删结点的直接前驱(将被删结点前驱的值取代被删结点的值) */
            if(q!=*p)
                q->rchild=s->lchild; /*  重接q的右子树 */ 
            else
                q->lchild=s->lchild; /*  重接q的左子树 */
            free(s);
        }
        return TRUE;
    }

    二叉排序树性能分析

    每个结点的Ci为该结点的层次数。最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和logn成正比(O(log2(n)))。最坏情况下,当先后插入的关键字有序时,构成的二叉排序树为一棵斜树,树的深度为n,其平均查找长度为(n + 1) / 2。也就是时间复杂度为O(n),等同于顺序查找。因此,如果希望对一个集合按二叉排序树查找,最好是把它构建成一棵平衡的二叉排序树(平衡二叉树)。

    参考:二叉排序树

    package com.liuhao.DataStructures;  
      
    import java.util.ArrayDeque;  
    import java.util.ArrayList;  
    import java.util.List;  
    import java.util.Queue;  
      
      
    public class SortedBinTree <T extends Comparable>{  
      
        static class Node{  
            Object data;  
            Node parent;  
            Node left;  
            Node right;  
              
            public Node(Object data, Node parent, Node left, Node right) {  
                this.data = data;  
                this.parent = parent;  
                this.left = left;  
                this.right = right;  
            }  
              
            public String toString(){  
                return "[data=" + data + "]";  
            }  
              
            public boolean equals(Object obj){  
                if(this == obj){  
                    return true;  
                }  
                  
                if(obj.getClass() == Node.class){  
                    Node target = (Node) obj;  
                    return data.equals(target.data) && left == target.left   
                            && right == target.right && parent == target.parent;  
                }  
                  
                return false;  
            }  
              
        }  
          
        private Node root;  
          
        public SortedBinTree(){  
            root = null;  
        }     
          
        public SortedBinTree(T o){  
            root = new Node(o, null, null, null);  
        }  
          
        /** 
         * 添加节点 
         * @param ele 新节点的元素 
         */  
        public void add(T ele){  
            if(root == null){  
                root = new Node(ele, null, null, null);  
            }  
            else{  
                Node current = root;  
                Node parent = null;  
                int cmp;  
                  
                //搜索合适的叶子节点,以该叶子节点为父节点添加新节点  
                do{  
                    parent = current;  
                    cmp = ele.compareTo(current.data);  
                      
                    //如果新节点的值大于当前节点的值  
                    if(cmp > 0){  
                        //以当前节点的右子节点作为当前节点  
                        current = current.right;  
                    }else{  
                        current = current.left;  
                    }  
                }while(current != null);  
                  
                //创建新节点  
                Node newNode = new Node(ele, parent, null, null);  
                  
                //如果新节点的值大于父节点的值  
                if(cmp > 0){  
                    parent.right = newNode;  
                }else{  
                    parent.left = newNode;  
                }  
            }  
        }  
          
        /** 
         * 删除节点 
         * @param ele 
         */  
        public void remove(T ele){  
            Node target = getNode(ele);  
              
            if(target == null){  
                return;  
            }  
              
            //左右子树都为空  
            if(target.left == null && target.right == null){  
                if(target == root){  
                    root = null;  
                }  
                else{  
                    //被删除节点是父节点的左子节点  
                    if(target == target.parent.left){  
                        //将target的父节点的left设为null  
                        target.parent.left = null;  
                    }else{  
                        target.parent.right = null;  
                    }  
                      
                    target.parent = null;  
                }  
            }  
              
            //左空右不空  
            else if(target.left == null && target.right != null){  
                if(target == root){  
                    root = target.right;  
                }  
                else{  
                    //被删除节点是父节点的左子节点  
                    if(target == target.parent.left){  
                        target.parent.left = target.right;  
                    }  
                    else{  
                        target.parent.right = target.right;  
                    }  
                      
                    //让target的右子树的parent指向target的parent  
                    target.right.parent = target.parent;  
                }  
            }  
              
            else if(target.left != null && target.right == null){  
                if(target == root){  
                    root = target.left;  
                }  
                else{  
                    //被删除节点是父节点的左子节点  
                    if(target == target.parent.left){  
                        target.parent.left = target.left;  
                    }  
                    else{  
                        target.parent.right = target.left;  
                    }  
                      
                    //让target的右子树的parent指向target的parent  
                    target.left.parent = target.parent;  
                }  
            }  
              
            //左右都不为空  
            else{  
                //leftMaxNode:target的左子树中值最大的节点  
                Node leftMaxNode = target.left;  
                  
                //搜索target的左子树中值最大的节点  
                while(leftMaxNode.right != null){  
                    leftMaxNode = leftMaxNode.right;  
                }  
                  
                //从原来的子树中删除leftMaxNode节点  
                leftMaxNode.parent.right = null;  
                  
                leftMaxNode.parent = target.parent;  
                  
                if(target == target.parent.left){  
                    target.parent.left = leftMaxNode;  
                }  
                else{  
                    target.parent.right = leftMaxNode;  
                }  
                  
                leftMaxNode.left = target.left;  
                leftMaxNode.right = target.right;  
                target.parent = target.left = target.right = null;  
            }  
        }  
          
        /** 
         * 根据指定值搜索节点 
         * @param ele 指定值 
         * @return 节点 
         */  
        public Node getNode(T ele){  
            //从根节点开始搜索  
            Node p = root;  
            while(p != null){  
                int cmp = ele.compareTo(p.data);  
                  
                if(cmp < 0){  
                    p = p.left;  
                }  
                else if(cmp > 0){  
                    p = p.right;  
                }  
                else{  
                    return p;  
                }  
            }  
              
            return null;  
        }  
          
        /** 
         * 广度优先遍历 
         * @return 
         */  
        public List<Node> breadthFirst(){  
            Queue<Node> queue = new ArrayDeque<Node>();  
            List<Node> list = new ArrayList<Node>();  
              
            if(root != null){  
                queue.offer(root);  
            }  
              
            while(!queue.isEmpty()){  
                //将该队列的“队尾”元素添加到List中  
                list.add(queue.peek());  
                //弹出队尾节点  
                Node p = queue.poll();  
                  
                //如果左子节点不为null,将它加入“队列”  
                if(p.left != null){  
                    queue.offer(p.left);  
                }  
                  
                if(p.right != null){  
                    queue.offer(p.right);  
                }  
            }  
              
            return list;  
        }  
          
        /** 
         * 中序遍历 
         * @return 
         */  
        public List<Node> inIterator(){  
            return inIterator(root);  
        }  
          
        private List<Node> inIterator(Node node){  
            List<Node> list = new ArrayList<Node>();  
              
            //递归处理左子树  
            if(node.left != null){  
                list.addAll(inIterator(node.left));  
            }  
              
            //处理根节点  
            list.add(node);  
              
            //递归处理右子树  
            if(node.right != null){  
                list.addAll(inIterator(node.right));  
            }  
              
            return list;  
        }  
    }  

     

     

    自己写的排序二叉树的创建和排序

    package com.binary_tree;
    
    public class SortBinTree {
    
        SortBinTree left;
        SortBinTree right;
        int value;
    
        SortBinTree(int value) {
            left = null;
            right = null;
            this.value = value;
    
        }
    
        static SortBinTree insert(SortBinTree node, int value) {
    
            if (node == null) {
                node = new SortBinTree(value);
            } else {
    
                if (node.value > value) {
                    node.left = insert(node.left, value);
                } else {
                    node.right = insert(node.right, value);
                }
            }
            return node;
        }
    
        static SortBinTree find(SortBinTree root, int key) {
    
            if (root == null)
                return null;
    
            if (root.value == key) {
                return root;
            } else {
                if (root.value > key) {
                    return find(root.left, key);
                } else {
                    return find(root.right, key);
                }
            }
    
        }
    
        static void printMiddleOrder(SortBinTree root) {
            if (root == null)
                return;
    
            printMiddleOrder(root.left);
            System.out.println(root.value);
            printMiddleOrder(root.right);
    
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
    
            SortBinTree root = null;
            int value[] = { 11, 12, 7, 4, 3, 2, 6, 15, 8, 9 };
            for (int i = 0; i < value.length; i++) {
                root = insert(root, value[i]);
            }
    
            printMiddleOrder(root);
    
            SortBinTree findTree = find(root, 3);
            System.out.println("ss");
    
            printMiddleOrder(findTree);
        }
    
    }

     

     

     参考:二叉排序树

    参考:二叉树的Java实现及特点总结

    参考:排序二叉树及其Java实现

    参考:一步一图一代码之排序二叉树

     

     

    转载于:https://www.cnblogs.com/aspirant/p/3557241.html

    展开全文
  • =0)的二叉树,给出中序遍历序列,并判断是否为二叉搜索。 题目保证二叉树不超过200个节点,节点数值在整型int范围内且各不相同。 输入格式: 第一行是一个非负整数N,表示有N个节点 第二行是一个整数k,是树根的...
  • 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。...算法:树中序遍历的顺序为左根右,根据二叉树搜索树的性质,如果一棵树
  • 二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作...
  • 二叉排序,对二叉排序进行中序遍历,可以得到一个递增的有序序列 */ template<class T> class BinNode { public: T key; BinNode* lchild, * rchild; }; template<class T> clas.
  • 经过学习一段时间的数据结构,总结...树的度:一棵树中最大的节点 叶子节点或终端节点:度为0的节点 双亲节点或父节点:若一个含有子节点,则这个节点称为子节点的父节点 二叉树 一颗二叉树是结点的一个有限集合,该集
  • 创建二叉树并中序遍历

    千次阅读 2020-10-22 23:16:12
    题目描述 编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树...输出将输入字符串建立二叉树后中序遍历序列,每个字符后面都有一个空格。 每个输出结果占一行。 样例输入 Copy a#b#cdef##
  • 根据前序遍历和中序遍历求后序遍历

    千次阅读 多人点赞 2019-07-19 21:29:59
    已知一棵二叉树的先序遍历序列中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列。 分析:先序遍历序列的第一个字符为根结点。对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树...
  • 无论是这三种遍历中的哪种,左子树一定先于右子遍历,且所谓的“先中后”都是指根结点root在遍历中的位置,因此先序遍历的访问顺序是根结点→左子树→右子中序遍历的访问顺序是左子树→根结点→右子,后序...
  • 二叉排序的定义 二叉排序,也称二叉查找。二叉排序或者是一棵,或者是一颗具有以下特性的非空二叉树: ...右子结点值,对二叉树中序遍历可得到一个递增的有序序列。 二叉排序的创建...
  • 中序遍历所看到的第一个节点 D是第一个节点,没有左儿子,可能有右儿子,先遍历D的右儿子,没有右儿子,回到D的父亲B。 遍历B的右子E级所在的,从E一直往左走 G的下一个结点是E(E的左子树已经访问完毕了)。...
  • 树的定义 树状图是一种数据结构,它是由n(n>=0)个有限结点组成一个具有层次...有若干个互不相交的子树,这些子树本身也是一棵树 2.通俗的定义 树是由结点和边组成 每个结点只有一个父结点,但可以有多个子结点
  • 建树的时候,有时候没有必要大费周章地去通过...由于二叉树中序遍历的结果是一串有序序列,那么我们可以通过中序来得到一棵二叉树 void leveltra(int root) { //从根节点开始遍历 if (root &gt; n) { return...
  • 验证:中序遍历看是否有序即可 python代码 class TreeNode: def __init__(self,x): self.val = x self.left, self.right = None, None def createBST(nums): root = None for num in nums
  • 在计算机科学中,二叉树是数据结构,其中每节点最多有两子节点,称为左子节点和右子节点。使用集合理论概念的递归定义是(非空)二叉树是元组(L, S, R),其中L和R是二叉树或空集,而S是包含根的单例集。一些...
  • 一棵树,你可以把其中任意一个节点作为根节点。每个节点都有一个小写字母,中序遍历得到一个字符串,求所有能得到的字符串的字典序最小串。因为这棵树不一定是二叉树,所以中序遍历时,先中序遍历以节点序号最小...
  • 一、二叉树的遍历概念 ... 根据前序遍历的结果可知第一个访问的必定是root结点。 (2). 中序遍历 中序遍历:若二叉树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然
  • 恢复二叉搜索树 二叉搜索树中的两节点被错误地交换。...请在不改变其结构的情况下,恢复这棵树。 示例1: 输入: [1,3,null,null,2] 1 / 3 \ 2 输出: [3,1,null,null,2] 3 / ...
  • 现给定一组数据,请你对这组数据按给定顺序建立一棵排序二叉树,并输出其中序遍历的结果。 Input 输入包含多组数据,每组数据格式如下。 第一行包含一个整数n,为关键值的个数,关键值用整数表示。(n<=1000)...
  • 的后续遍历就是二叉树的中序遍历。 1、转换为二叉树 由于二叉树是有序的,为了避免混淆,对于无序,我们约定中的每结点的孩子结点按从左到右的顺序进行编号。 将转换成二叉树的步骤是: (1)加线。...
  • 二叉树中序遍历的非递归算法

    千次阅读 2019-02-07 10:40:49
    其中中序遍历对于一棵二叉搜索来说得到序列一个上升的序列,因为是递归定义的,所以我们在对进行遍历的时候往往是采用递归的方式来进行处理的,而且使用递归的方式往往处理起来相对简洁一些但是有的情况下...
  • 前序/中序/后序遍历/哈夫曼

    千次阅读 2020-09-18 22:00:14
    中序遍历首先遍历左子树,然后访问根结点,最后遍历右子。若二叉树为空则结束返回 后序遍历首先遍历左子树,然后遍历右子,最后访问根结点,在遍历左、右子时,仍然先遍历左子树,然后遍历右子,最后遍历根...
  • 力扣108....将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索。 本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数组...
  • 这种方法以深度 depth 优先为策略,从根节点开始一直遍历到某个叶子节点,然后回到根节点,在遍历另外一个分支。 根据根节点,左孩子节点和右孩子节点的访问顺序又可以将 DFS 细分为先序遍历 preorder,中序遍历 in...
  • 在计算机科学中,二叉树是每结点最多有两子树的结构 demo: 1、创建节点类:Node public class Node { private Node left; // 左子节点 private Node right; // 右子节点 private int data; // 节点的...
  • 给定的升序数组,其实就是BST的中序遍历数组,只是给定一棵二叉树的中序遍历数组,并不能确定一棵二叉树,但是题目要求是严格平衡的二叉搜索,所以可以选择升序序列的中间元素作为当前的根结点元素。 三、代码 /**...
  • 假设能构成颗二叉搜索树,那么这棵树中序遍历必定为有序序列 此时已知前(后)序遍历和中序遍历 根据二叉树的性质,已知前(后)序遍历和中序遍历可以唯一的确定颗二叉树 思路 递归思想,首先找到前序遍历中...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,217
精华内容 4,086
关键字:

中序遍历一棵树可得到一个有序序列