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

    2016-04-03 14:45:14
    二叉树搜索的目的是: 在某个数组中快速搜索某个元素; 要求数组已经进行了排序(本例中是升序); 最简单的方法是顺序搜索:即从第一个位置开始,依次向后检查,知道找到所需元素为止。顺序搜索平均时间是n/2; ...

    二叉树搜索的目的是:

    在某个数组中快速搜索某个元素;

    要求数组已经进行了排序(本例中是升序);

    最简单的方法是顺序搜索:即从第一个位置开始,依次向后检查,知道找到所需元素为止。顺序搜索平均时间是n/2;

    如果采用二叉树搜索,则搜索时间为logn;


    核心思想是:

    将中间元素和搜索值进行比较,如果中间值小于搜索值,则递归调用二叉搜索算法,搜索mid+1到last的区间;如果大于搜索值,则递归搜索first到mid-1区间。

    中间用到了Comparable接口:x.comparaTo(y)

    如果x引用小于y的引用,则返回小于0的整数;

    如果x引用大于y的引用,则返回大于0的整数;

    如果x和y相等,则返回0;


    代码:

    public class binarySearch {
    	public static int binarySearch(Object[] a,int first,int last,Object key){
    		if(first <= last){
    			int mid = (last + first) >> 1;
    			Object midVal = a[mid];
    			int comp = ((Comparable)midVal).compareTo(key);
    			if(comp < 0)
    				return binarySearch(a,mid+1,last,key);
    			if(comp > 0)
    				return binarySearch(a,first,mid-1,key);
    			return mid;
    		}
    			return -1;
    	}
    	
    	public static void main(String[] args) {
    		Object[] a = {1,2,3,4,5,6,7,8};
    		int first = 0;
    		int last = a.length - 1;
    		int key = 2;
    		int position = binarySearch.binarySearch(a,first,last,key);
    		if(position != -1)
    			System.out.println("a["+ position +"] = " + key);
    		else
    			System.out.println("Not Found");
    	}
    
    }
    


    返回结果:

    a[1] = 2


    展开全文
  • 二叉树搜索算法

    2013-12-27 00:07:13
    关于二叉树搜索的算法,是全英文,基础不好的别进,这是我想刷积分的
  • 山东大学数据结构课设二叉树搜索
  • 使用labview完成简单的二叉树搜索和顺序搜索
  • 1.平衡二叉树:每个树的左树的高度与右树高度绝对小于等于1....2.搜索二叉树:每个树的左树的最大值小于节点值,右树的最小值大于节点值。图例 左树的最大3值小于节点6,右树的最小值为7,搜索二叉树。 ...

    1.平衡二叉树:每个树的左树的高度与右树高度绝对小于等于1.图例

    左边的高度为3,右树为2 绝对值小于等于1,为平衡树

    2.搜索二叉树:每个树的左树的最大值小于节点值,右树的最小值大于节点值。图例

    左树的最大3值小于节点6,右树的最小值为7,搜索二叉树。

    展开全文
  • C 语言二叉树 搜索 遍历 非递归
  • 利用二叉树实现IP查询,首先将10进制IPV4地址转化为二进制构建二叉树,利用二叉树搜索进行搜索,查询时间复杂度log2n,比传统IP库n的查询速度高出一个量级。 接口 根据IP查询城市或地区的接口是IpHelper类中的...
  • 二叉树的子树: 在二叉树中以任何一个节点为头部的整棵树称作二叉树的子树。注意是整棵树!!!! 平衡二叉树(AVL树): 1. 空树是平衡二叉树。 2. 如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子...

    二叉树的子树:

    在二叉树中以任何一个节点为头部的整棵树称作二叉树的子树。注意是整棵树!!!!

    平衡二叉树(AVL树):

    1. 空树是平衡二叉树。

    2. 如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过1.


    案例一:给定一棵二叉树的头节点head,判断一棵树是否是平衡二叉树。

    解法的整体过程为:二叉树的后序遍历。

    对于节点head来说,先遍历head的左子树,遍历的时候需要搜集两个信息:

    1. 左子树是否为平衡二叉树(true or false):如果左子树为false,不是平衡二叉树,则无需进行任何的后续过程,因为整棵树已经不是平衡二叉树了,直接返回false

    2. 左子树最深可以到达哪一层,LH

    如果head的左子树是平衡二叉树,再去遍历head的右子树,遍历过程中依然要搜集两个信息:

    1. head右子树是否为平衡二叉树:如果为false,直接返回false。

    2. 右子树最深到达哪一层。RH

    如果左子树和右子树都是平衡二叉树,则比较LH和RH。如果差值大于1,则返回false,整棵树不是平衡二叉树。

    如果差值小于1,则返回LH和RH中较大的一个作为以当前head为头的树的深度。

    注意:!!!二叉树中很多面试题都是对二叉树遍历的代码进行了改写!!!

    /*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/


    class CheckBalance {
    public:
        bool check(TreeNode* root) {
            // write code here
            //也就是将求高度和求左右子树是否平衡合并到一起了
            if(root==NULL)
                return true;
            int height=0;
            return  checkbalancedtree(root,height);
            
        }
        bool checkbalancedtree(TreeNode* root, int& height){
            if(root==NULL){
                height=0;
                return true;
            }
            //大致思路就是先判断左右子树是不是平衡树,如果不是的话就直接返回false;如果是的话,根据算出来的左右子树的高度来判断当前root为根的树是不是平衡树,如果
            //不是的话,直接返回false;如果是的话,才计算当前root为跟的树的高度同时返回true;
            int leftheight,rightheight;
            bool left=checkbalancedtree(root->left,leftheight);
            bool right=checkbalancedtree(root->right,rightheight);
            
            if(left&&right)//当左右子树都是平衡二叉树时
            {
                if(leftheight-rightheight>1||leftheight-rightheight<-1)//以root为根的树不是平衡二叉树
                    return false;
                else{
                 height=leftheight>rightheight?(leftheight+1):(rightheight+1);
                 return true;
                }
                
            }else{
                return false;
            }


       }
    };

    具体的代码实现如上所示,利用递归进行,这里需要注意的是上面的实现方式是一边计算子树的高度,同时判断子树是不是平衡二叉树;当然也可以将这两个分开进行,也就是将树的高度的计算单独拿出来,虽然也是递归,但是这样的缺点就是可能会重复的遍历树,因为先是计算子树的高度的时候会遍历一遍,然后判断子树是不是平衡二叉树的时候又会遍历一遍,造成额外的时间复杂度!!具体实现可以参考http://www.cnblogs.com/ranjiewen/p/5507621.html;而上面的实现方式的主要思想就是先判断左右子树是不是平衡树,如果不是的话就直接返回false;如果是的话,根据算出来的左右子树的高度来判断当前root为根的树是不是平衡树,如果不是的话,直接返回false;如果是的话,才计算当前root为根的树的高度同时返回true!




    搜索二叉树:二叉查找树 或者 二叉排序树

    整棵二叉树并且二叉树的所有子树都具有如下的特征:

    每棵子树的头节点的值都比各自左子树上的所有节点值要大,也都比各组右子树上的所有节点值要小。

    搜索二叉树的性质:搜索二叉树按照中序遍历得到的序列,一定是从小到大排列的。反之,一棵树中序遍历得到的序列是从小到大排列的,说明这棵树一定是搜索二叉树。

    红黑树、平衡搜索二叉树(AVL)等,其实都是搜搜二叉树的不同实现。这些实现,都力争做到让搜索二叉树的搜索效率提高并且调整代价尽量小。


    案例二:给定一棵二叉树的头节点head,请判断这棵树是否是搜索二叉树。

    思路为:

    1.改写二叉树的中序遍历

    2. 遍历到每个节点的值时,如果一直比上一个遍历的节点值要大,则是搜索二叉树,否则,不是搜索二叉树。

    3. 为了方便同时得到当前节点,和上一个遍历的节点,二叉树中序遍历非递归的实现比较合适!!



    满二叉树和完全二叉树:

    满二叉树:除了最后一层的节点无任何子节点外,剩下每一层上的节点都有两个子节点。

    满二叉树的层数记为L,节点数记为N,则N=POW(2,L)-1.  L=log2(N+1).


    完全二叉树:完全二叉树是指除了最后一层之外,其他每一层的节点数都是满的,最后一层如果也满了,是一棵满二叉树。也是完全二叉树。最后一层如果不满,缺少的节点也全部的集中在右边,那也是一棵完全二叉树。


    案例三:给定一棵二叉树的头节点head,判断一棵树是否是完全二叉树。

    按照下面的规则来判断会变得比较简单:

    1. 采用按层遍历二叉树的方式,从每层的左边向右边依次遍历所有的节点。

    2. 如果当前节点有右孩子,但没有左孩子,直接返回false。

    3. 如果当前节点并不是左右孩子全有,那之后的节点都必须为叶节点,否则返回false。

    4.遍历过程中如果不返回false,遍历结束后返回true即可。

    /*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/


    class CheckCompletion {
    public:
        bool chk(TreeNode* root) {
            // write code here
            TreeNode* current;
            queue<TreeNode*> q;
            q.push(root);
            bool flag=false;//正常的按层遍历的话只要借助于队列就可以了,不用考虑什么last或者nlast,因为这两个只有需要换行等操作的时候才需要。
            while(!q.empty()){
                current=q.front();
                q.pop();
                if(flag==true&&(current->left!=NULL||current->right!=NULL))//说明前面已经有节点它的右孩子为空了,因此这个节点之后的节点的左右孩子都应该为空
                    return false;
                else if(flag==false&&current->left==NULL&&current->right!=NULL)
                    return false;
                else if(flag==false&&current->right==NULL)//说明后面遍历的节点的左右孩子都应该为空
                    flag=true;
                if(current->left!=NULL){
                    q.push(current->left);
                }
                if(current->right!=NULL){
                    q.push(current->right);
                }
            }
            return true;
        }
    };

    具体的实现如上面所示,需要注意的是在按层遍历一棵树的时候,是不需要记last或者nlast的,只要队列就可以了!!!

    需要注意的是!!面试中的二叉树节点类型并没有指向父节点的指针,除非特别说明!但是工程上的二叉树节点类型往往多一条指向父节点的指针。


    后继节点和前驱节点:

    后继节点:一个节点的后继节点是指,这个节点在中序遍历序列中的下一个节点。

    比如:中序遍历的序列为:DBEAFCG.

    G的后继为空!

    如果是一个搜索二叉树,那么中序遍历的序列就是升序序列。

    前驱节点:

    这个节点在中序遍历中的上一个节点。


    案例四:

    假如二叉树的节点类型中多了一个指向父节点的指针:parent。假设有一棵这种类型的节点组成的二叉树,

    树中每个节点的parent指针都正确指向自己的父节点,头节点的parent指向空。只给定在二叉树中的某节点

    node,该节点并一定是头节点,可能是树中任何一个节点,请实现返回node的后继节点的函数。

    普通方法:

    1. 通过node节点的parent指针不断向上找到头节点。

    2. 通过找到的头节点,做整棵树的中序遍历,生成中序遍历序列。

    3. 在中序遍历序列中,node节点的下一个节点就是其后续节点。

    上面这种方式要遍历所有节点,时间复杂度为O(N),额外空间复杂度为O(N)。


    最优解法:

    如果node节点和node后继节点之间的实际距离为L,最优解法只用走过L个节点,时间复杂度为O(L),额外空间复杂度为O(1).

    1. 如果node有右子树,那么后继节点就是右子树上最左边的节点。

    2. 如果node没有右子树,那么先看node是不是node父节点的左孩子,如果是左孩子,那么此时node的父节点就是node的后继节点。如果是右孩子,就向上,寻找node的后继

    节点。假设向上移动到的节点记为s,s的父节点记为p,如果发现s是p的做孩子,那么节点p就是node节点的后继节点,否则就一直向上移动。

    3. 如果一直向上寻找,都移动到空节点了还是没有发现node的后继节点,说明node根本不存在后继节点,返回空即可。

    展开全文
  • C++实现二叉树搜索

    2018-12-18 19:21:40
    功能:插入、查找、删除、清除整个树、返回最大值、返回最小值、前序遍历、中序遍历、后序遍历。 注:此二叉树允许插入相同的值
  • 图解二叉树搜索算法

    万次阅读 2016-09-09 16:30:05
    二叉查找树(Binary Search Tree),也称二叉搜索树,是指一棵空树或者具有下列性质的二叉树: 任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 任意节点的右子树不空,则右子树上所有...

    二叉查找树(Binary Search Tree),也称二叉搜索树,是指一棵空树或者具有下列性质的二叉树:

    1. 任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    1. 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    2. 任意节点的左、右子树也分别为二叉查找树;
    3. 没有键值相等的节点。
    4. 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、multiset、关联数组等。(摘自维基百科)

    下面 4 张 GIF 动图,是 penjee 官博制作分享。,分享给大家。
    ###图1:查找 BST 中的某个元素

    在二叉搜索树b中查找x的过程为:

    1. 若b是空树,则搜索失败,否则:
    1. 若x等于b的根节点的数据域之值,则查找成功;否则:
    2. 若x小于b的根节点的数据域之值,则搜索左子树;否则:
      查找右子树。
      这里写图片描述

    ###图2 ↓ :从有序数组构造一个二叉查找树

    这里写图片描述

    ###图3 ↓:往 BST 中插入元素

    向一个二叉搜索树b中插入一个节点s的算法,过程为:

    1. 若b是空树,则将s所指结点作为根节点插入,否则:
    1. 若s->data等于b的根节点的数据域之值,则返回,否则:
    2. 若s->data小于b的根节点的数据域之值,则把s所指节点插入到左子树中,否则:
      把s所指节点插入到右子树中。(新插入节点总是叶子节点)
      这里写图片描述

    ###图4 ↓:BST 转成有序数组
    这里写图片描述

    展开全文
  • 173. 二叉搜索树迭代器 这个题目就是的一个中序遍历的 再加上了一个的队列的先进先出的问题 package 计算机程序算法分类.二叉树问题; import java.util.LinkedList; import java.util.Queue; import java.util....
  • 二叉树搜索算法集合

    2019-01-30 17:26:35
    该篇总结关于二叉树前序遍历,中序遍历,后序遍历的各种实用算法(包括递归和遍历)。 先序遍历 先序遍历又称前序遍历,先序遍历(DLR),是二叉树遍历的一种,也叫做前序周游,可记做根左右。先序遍历首先访问根...
  • 二叉树搜索第k个节点

    2020-06-28 08:52:29
    利用二叉搜索树的性质,如果二叉树的中序遍历的节点是依次升序的,那么就是搜索二叉树。 所以我们可以通过中序遍历这颗二叉搜索树,得到的结果是依次升序的。 把得到的结果放入一个集合中,来得到第k个最小节点。 ...
  • 本文用来保存二叉搜索树的查找,插入,删除以及二叉树搜索树的建立等基本操作实现的完整代码: # 直接上代码!详细算法介绍请参考此文: [二叉搜索树的查找/插入/删除以及二叉树搜索树的建立等基本操作的详细介绍]...
  • 动态算法之最优二叉搜索树## 标题 最优二叉搜索树的解题核心是动态规划算法,每一个左子树右子树都是原树的一个简化,他们都遵循中跟遍历的节点值由低到高,正好具备最优子结构。 将节点从小到大排序:p1,p2,p3,p4,...
  • 非递归 C语言 二叉树算法 参考 遍历
  • 牛客网链接:二叉搜索树与双向链表 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。...转换成有序双向链表就要对搜索二叉树进行中序遍历 双向链表结点的prev可以理解成二叉树的left,next理...
  • 包含 Lec3和Lec4两个PDF文档.Lec3简单介绍了二叉树的相关操作,Lec4介绍了平衡二叉树,AVL树等的相关知识。文章不算长,但希望有用
  • 使用二叉树搜索(DFS、BFS和隐式搜索)求解背包问题 # -*- coding: utf-8 -*- # general binary-tree class BinaryTree : def __init__ (self, value) : self._value = value self._parent_node ...
  • 二叉搜索树是一种特殊的二叉树,为了加快搜索 有点类似二分查找的方法,左子树的值小于根节点的值,根节点的值小于右子树的值 二叉树的中序遍历结果是有序的。 用left表示prev,right表示next /** public class ...
  • 【ICPC-462】二叉树+二叉树搜索树+堆

    千次阅读 2013-01-15 21:16:09
    二叉树 二叉树的几个性质 1在二叉树的第i层最多有2^(i-1)个节点 2深度为k的二叉树最少有k个节点,最多2^k-1个节点 3对于任何一颗非空二叉树,如果其叶子节点数为n0,度为2的非叶子节点个数为n2= n0-1 4具有n...
  • 对于给定一个要插入的节点,需要修改二叉树的结构,首先是要定位到要插入的位置,代码如下:void InsertNode(BiTree &T,char value) { BiNode *node=new BiNode(); node->data=value; node->left=NULL; node->...
  • 问题描述: 给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种? 题号:96 示例: 输入: 3 输出: 5 ...其实和二叉树也没有什么关系,二叉树只是一个载体。 知识:左儿子节点比父节点小,
  • 解题思路:二叉树的中序遍历,左、根、右;因为二叉搜索树的中序遍历就是递增排列的,所以只要在中序遍历时将每个结点放入vector中,再分别为每个结点的左右指针赋值即可。 采用中序遍历: 修改中序遍历,在其中...
  • 题目:输入一个整数数组,判断数组是不是某二叉树的后序遍历的结果, 如果是返回true,否则返回false 。假设输入的数组的任意两个数字互不相同。 思路: 对于二叉搜索树而言,在后序遍历中得到的序列,最后一个...
  • 二叉搜索树:一棵二叉树,可以为空;如果不为空,满足以下性质: 非空左子树的所有结点的值小于其根结点的值。 非空右子树的所有结点的值大于其根结点的值。 左、右子树都是二叉搜索树。 ...
  • ``` #include #include using namespace std;...void search(string name2, string ...可以通过编译,输入完后,程序没有反应,我是在做一个二叉树的实验,所以把问题精简成这样来测试, 我百思不得其解啊
  • 虽然标题为“搜索树”,但是我还是习惯叫“查找树”,以下也将沿袭着一传统学习『查找树』心里面始终要有一个意识:对于查找树而言『平衡』很重要普通查找树(BST)查找树的初始化(返回根结点)查找树的查找(线性...
  • 二叉排序树或者是一颗空树,或者是具有下列性质的二叉树: (1)若它的左子树不空,则左子树上的所有结点的值均小于它的根结点的值。 (2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。 (3...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,939
精华内容 7,975
关键字:

二叉树搜索