精华内容
下载资源
问答
  • 在一棵空的二叉排序树
    2021-10-15 21:58:02

    判断一棵树是否为二叉排序树

    思路

    • 二叉排序树的中序遍历是有序的,所以判断一棵排序树可以进行中序遍历并且在遍历过程中判断是否有序。
    • 为此设置一个全局变量记录上一个中序遍历节点的值,遍历过程中与全局变量比大小并更新全局变量的值。

    实现

    #include<stdio.h>
    
    typedef struct node
    {
    	int data;
    	struct node *lchild;
    	struct node *rchild;
    }BTNode;
    
    int num=-32767;	//定义最小的全局变量 
    
    //中序遍历思想,并且更新全局变量的值 
    int Judge(BTNode *&p)
    {
    	int i; 
    	if(p==NULL) return 1;	//空节点则返回
    	
    	i=Judge(p->lchild);		//遍历并判断左子树是否满足二叉排序 
    	if(i==0) return 0;
    	
    	if(p->data>num)		//如果符合二叉排序树,更新全局变量的值 
    		num=p->data;
    	else			 
    		return 0;
    	
    	return  Judge(p->rchild);//最后判断右子树是否满足 
    } 
    
    更多相关内容
  • 二叉排序树又称二叉查找树。本文主要对二叉排序树的实现与基本操作进行详细介绍,以下代码实现了:1、二叉树的构建;2、二叉树的中、前、后、层序遍历;3、二叉树中结点的最大距离。下面就跟着小编一起来看下吧
  • 代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树二叉排序树查找递归算法,二叉排序树查找非递归算法
  • 二叉排序树详解

    千次阅读 2022-04-01 16:49:31
    摘要:本篇笔记专门介绍二叉排序树,重点讲解了二叉排序树的特性,以及二叉排序树各方面的基本实现。

    二叉排序树详解

    摘要:本篇笔记专门介绍二叉排序树,重点讲解了二叉排序树的特性,以及二叉排序树各方面的基本实现

    1.二叉排序树简介

      二叉排序树又称为二叉搜索树,是一种重要的数据结构,需要注意的是,在使用二分搜索中,搜索数组中每一个数字的函数调用栈重叠起来,就是一个平衡的或者说是接近平衡的二叉排序树,也就是说使用有序数组进行二分搜索实际上和在一个二叉排序树搜索一个节点干的事情是一样的。并且,对于一棵二叉排序树的深度优先中序遍历结果,就是一个有序的数组。二叉排序树首先要求该树是一棵二叉树,之后要求在这棵树中,所有子树的根节点的左子树上的节点值或者说是权重要均小于(或大于)根节点,而右子树上的所有节点值或者说是权重均大于(或小于)根节点。如图所示:

    image-20220330160850370

      二者均为二叉排序树,其中的左右的大小关系根据具体情况而定。

    2.二叉排序树的实现

    2.1.二叉排序树的节点实现

      二叉排序树的节点和普通树的节点没有差异,只是整棵树在生成的时候有所限制,因此不再画图介绍,我们在IDE中直接创建TreeNode.java文件,代表树的节点类,如图所示:

    image-20220330163153460

      之后我们开始书写代码,在树的节点类中,我们需要创建的字段分别为leftChildNoderightChildNode以及value,我们将他们声明为私有类型,如图所示:

    image-20220330163541208

      我们为其编写一个构造器,以便于节点对象初始化的时候就将这些数据进行赋值,如图所示:

    image-20220330163817219

      之后我们为其所有字符生成访问器和修改器,方法简单,不再赘述,生成后如图所示:

    image-20220330164434967

      在此附上源码:

    package binarySortTree;
    
    public class TreeNode {
        private TreeNode leftChildNode;
        private TreeNode rightChildNode;
        private Integer value;
    
        public TreeNode(Integer val) {
            this.value = val;
            this.leftChildNode = null;
            this.rightChildNode = null;
        }
    
        public TreeNode getLeftChildNode() {
            return leftChildNode;
        }
    
        public void setLeftChildNode(TreeNode leftChildNode) {
            this.leftChildNode = leftChildNode;
        }
    
        public TreeNode getRightChildNode() {
            return rightChildNode;
        }
    
        public void setRightChildNode(TreeNode rightChildNode) {
            this.rightChildNode = rightChildNode;
        }
    
        public Integer getValue() {
            return value;
        }
    
        public void setValue(Integer value) {
            this.value = value;
        }
        
    
    }
    
    
    2.2.二叉排序树的管理类实现

      二叉排序树的管理类实际上就是二叉排序树类,在这个类中定义了二叉排序树的存储结构,以及对于二叉排序树的各种方法,因此关于二叉排序树的生成,节点添加,节点修改,节点删除,节点搜索等各种方法都会在此定义。为此,我们特意新建一个BinarySortTree.java来存储这个管理类,如图所示:

    image-20220330165753921

    2.2.1.二叉排序树的结构定义

      在管理类中,我们通常会定义一个指针字段,用于指向实体结构的首索引节点,如在链表中我们会定义一个head节点,而在二叉排序树中我们也会定义一个root节点,在之后的各种生成操作中,我们都会以这个节点为首索引节点,在这个节点上进行扩充,简而言之,我们使用这个节点来表示整棵树结构,实际上它并不是一棵树,但是它是我们访问这棵树的入口,因此我们在逻辑上认为它就是这棵树逻辑上的实体,它的定义并不难,一个字段即可,如图所示:

    image-20220330170830776

      然而,真正困难的方法才刚要到来,接下来,我们研究二叉排序树的插入方法。

    2.2.2.二叉排序树的插入方法定义

      首先我们使用画图的方式来描绘一下二叉排序树的插入过程,如图,我们要在一棵空的二叉排序树中插入一个数组6,2,7,4,0,3,1,5,如图所示:

    image-20220330174910436

      首先我们插入第一个元素6,此时二叉排序树中还没有任何一个节点,因此我们应该新建一个节点,并将6存储进去,并将6认定为根节点,如图所示:

    image-20220330185009407

      之后我们插入第二个元素2,此时二叉排序树已经不是一个空树了,因此我们需要首先找到适合它的位置,我们将2和6进行对比,判断谁大谁小,我们发现2更小,因此2应该被插入在6的左子树中,之后我们将2和根节点6的左子树进行对比,发现6的左子树是空的,因此这时我们将2存放在6的左子树根节点位置,如图所示:

    image-20220330185248249

      之后是元素7,7显然大于6,因此我们要将7放在6的右子树中,经过探寻我们发现6的右子树根节点也是空的,因此我们需要将7放在右子树的根节点上,如图所示:

    image-20220330185409930

      之后是元素4,我们首先将4和6对比,发现4是小于6的,因此4应该位于6的左子树上,之后我们将4和6的左子树根节点进行对比,发现4是大于2的,因此4应该被放在2的右子树上,而2的右子树为空,因此4直接被放置在2的右子树根节点上,如图所示:

    image-20220330185550116

      之后是元素0,首先我们将0和元素6进行对比,发现0是小于元素6的,因此应该被放置在6的左子树上,之后我们将0和6的左子树根节点进行对比,发现其小于2,因此0应该被放置在2的左子树上,这时我们发现0是小于2的,因此0应该被放置在2的左子树上,同时我们发现2的左子树为空,因此我们将0放置在2的左子树根节点上,如图所示:

    image-20220330185804440

      之后是元素3,我们发现元素3是小于6的,因此3应该被放置在6的左子树上,而这时我们就开始研究6的左子树,3大于2,因此3应该被放置在2的右子树上,这时我们开始研究2的右子树,而3是小于2的右子树根节点4的,因此3应该放置在4的左子树上,我们发现4的左子树为空,因此我们将3放置在4的左子树根节点上,如图所示:

    image-20220330190756726

      之后是元素1,首先我们将1和6进行对比,发现1是小于6的,因此1应该被放置在6的左子树上,而1又小于2,因此应该被放置在2的左子树上,而1又大于0,因此应该被放置在0的右子树上,0的右子树为空,因此1应该被放置在0的右子树根节点上,如图所示:

    image-20220330191000945

      之后我们研究最后一个元素5,5小于根节点6,因此我们应该将5放置在6的左子树上,而5大于2,因此我们应该将5放置在2的右子树上,5大于4,因此5应该被放置在4的右子树上,4的右子树为空,因此我们将5放置在4的右子树根节点上,如图所示:

    image-20220330191224075

      至此这个二叉排序树宣布构造完毕,经过这个步骤,我们可以分析出二叉排序树的插入规则:新的节点只能被插入在一个叶子节点之下,这个插入过程实际上是新节点在和不同规模的子树的根节点进行比较之后,被放置在了一个最小的或者是次最小的子树之下,并一定会形成一个新的最小规模子树,新的节点一定会作为一个新子树的根节点,而不是顶替一个已有子树的根节点。因此我们总结出来了插入的规律:

    1.检查该二差排序树是否为空,如果为空,则将新节点指定为根节点,否则将新节点与根节点进行比较;
    2.根据比较结果,确定新节点应该插入根节点的左子树还是右子树,之后我们将应该被插入的左右子树作为新的研究对象,重复1过程
    

      现在我们来书写代码,首先我们书写一个普通的实现方式,代码如图所示:

    image-20220330202028559

      我们在TreeNode类中重写一个toString方法,用来测试一下这个插入方法:

    image-20220330202157471

      书写测试代码如下:

    image-20220330202413652

      获取输出结果如下:

    image-20220330202450403

    //整理如下:
    TreeNode{
        leftTreeNode=TreeNode{
            leftTreeNode=TreeNode{
                leftTreeNode=null, 
                rightTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=1
                }, 
                value=0
            }, 
            rightTreeNode=TreeNode{
                leftTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=3
                }, 
                rightTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=5
                }, 
                value=4
            }, 
            value=2
        }, 
        rightTreeNode=TreeNode{
            leftTreeNode=null, 
            rightTreeNode=null, 
            value=7
        }, 
        value=6
    }
    

      经验证发现这个输出结果是正确的,接下来我们分析代码:

    public void insert(Integer value) {
            TreeNode newTreeNode = new TreeNode(value);//首先建立一个新节点,代表即将要插入的节点
            if (root == null) {//检查根结点,如果根结点为null的话,我们直接将新节点赋值给根节点
                root = newTreeNode;
            } else {//否则我们将进行普通的插入操作
                TreeNode currentNode = root;//设置一个心指针指向当前结构的根节点
                TreeNode parentNode;//为了便于插入,我们专门设置一个父节点,让它一直指向当前指针的父节点
                while (true) {//让循环一直进行下去
                    parentNode = currentNode;//父节点保存当前节点值
                    if (newTreeNode.getValue() > currentNode.getValue()) {//如果新节点的值大于当前节点,那么我们进行如下操作
                        currentNode = currentNode.getRightChildNode();//如果新节点的值大于当前节点,那我们首先要让当前指针指更新,指向它的右子树
                        if (currentNode == null) {//如果右子树为空,那么说明此时有供新节点插入的空位,那么我们进行插入
                            parentNode.setRightChildNode(newTreeNode);//因为当前指针已经更新,但是父节点保存了它更新之前的值,此时父节点指向的就是当前指针的上一个节点,因此直接让父节点指针的右子树等于新节点即可
                            return;//插入一个之后立即返回
                        }
                        //如果右子树不为空,则什么也不做,让循环继续推移
                    } else {//如果新节点的值不大于当前节点,我们则进行如下操作
                        currentNode = currentNode.getLeftChildNode();//我们将让当前指针更新为自己的左孩子节点
                        if (currentNode == null) {//同理,此时我们应该进行插入操作
                            parentNode.setLeftChildNode(newTreeNode);//因为父节点已经保存了之前的指向,我们直接让父节点的做孩子节点为新节点
                            return;
                        }
                    }
                }
            }
        }
    

      对于这个方法我又一个小小的优化方案,可以去掉父节点指针的使用:

    image-20220330204611909

      现在让我们修改测试代码如下:

    image-20220331080317127

      我们运行查看输出如下:

    TreeNode{
        leftTreeNode=TreeNode{
            leftTreeNode=TreeNode{
                leftTreeNode=null, 
                rightTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=1
                }, 
                value=0
            }, 
            rightTreeNode=TreeNode{
                leftTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=3
                }, 
                rightTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=5
                }, 
                value=4
            }, 
            value=2
        }, 
        rightTreeNode=TreeNode{
            leftTreeNode=null, 
            rightTreeNode=null, 
            value=7
        }, value=6
    }
    

      我们可以发现其结果是和之前的方法输出一致的。除去普通的插入方法外,我们还可以使用一种递归的方法,首先因为这个插入过程就是一个递归插入的过程,实际上我们做的事情是:拿到新节点之后,先将其放在最大的树中进行比较,我们让它和根节点进行比较,如果其小于根节点,这时我们查看根节点是否拥有左子树,并将新节点放在根节点的左子树上进行比较,此时我们是与左子树的根节点进行了比较,我们将眼界缩小到了一棵子树,然后我们重复这个过程,因此这也是一个递归的过程,我们可以书写这样的递归方法来解决这个问题:

    image-20220331090556063

      验证输出为:

    TreeNode{
        leftTreeNode=TreeNode{
            leftTreeNode=TreeNode{
                leftTreeNode=null, 
                rightTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=1
                }, value=0
            }, rightTreeNode=TreeNode{
                leftTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=3
                }, 
                rightTreeNode=TreeNode{
                    leftTreeNode=null, 
                    rightTreeNode=null, 
                    value=5
                }, 
                value=4
            }, 
            value=2
        }, 
        rightTreeNode=TreeNode{
            leftTreeNode=null, 
            rightTreeNode=null, 
            value=7
        }, 
        value=6
    }
    

      验证正确。

      代码如下:

    public void insertRec(TreeNode currentRoot, Integer val) {
            if (this.root == null) {//如果结构根节点为null,那么先为其赋予一个实体节点
                TreeNode newTreeNode = new TreeNode(val);
                this.root = newTreeNode;
            } else {
                if (currentRoot.getValue() > val) {//如果即将插入的值小于当前根节点
                    if (currentRoot.getLeftChildNode() == null) {//那么这个新节点铁定要往它的左子树上放,我们先看看它的左子树是否为空,是否能直接放
                        TreeNode newTreeNode = new TreeNode(val);//如果为空说明此时我们可以直接放,那么我们就直接生成一个新节点,然后直接往里放
                        currentRoot.setLeftChildNode(newTreeNode);//这里就是放入的过程
                        return;
                    }
                    insertRec(currentRoot.getLeftChildNode(), val);//否则我们继续研究其左子树,将插入范围缩小到当前节点的左子树上,在下一层递归,将以当前根节点的左子树作为研究对象
                } else {
                    if (currentRoot.getRightChildNode() == null) {
                        TreeNode newTreeNode = new TreeNode(val);
                        currentRoot.setRightChildNode(newTreeNode);
                        return;
                    }
                    insertRec(currentRoot.getRightChildNode(), val);
                }
            }
        }
    

    3.二叉排序树的中序遍历

      二叉树的深度优先中序遍历,对于一棵子树的遍历,是先检索左孩子节点,然后在检索根节点,之后再检索右孩子节点的,对于一棵比较大的树,它会递归的检索左子树,左子树检索完毕之后检索根节点,之后再递归的检索右子树,这个检索过程使得二叉排序树的深度优先中序遍历结果,是一个有序的排列,接下来我们写一下二叉排序树的中序遍历:

    image-20220331093743839

      使用递归的方法并不难写,接下来让我们调用看看我们构建的二叉排序树使用中序遍历输出出来是否是一个有序的排列:

    image-20220331093923894

      结果如下图所示,很显然我们输出了一个有序排列:

    image-20220331094015011

    4.二叉排序树的节点查找

      在二叉排序树中进行指定值的节点查找非常简便,这个查找过程实际上就是一个二分搜索的过程,我们首先创建一个遍历指针,让这个指针指向排序树的根节点,如果根节点值等于我们想要查找的值,那么我们就直接进行返回操作即可,如果不等于,那么根节点必定大于或者小于我们要查找的值,此时我们根据具体情况在根节点的左子树或者右子树中继续查询,这里是一个递归过程,算法比较简单,因此不再深入研究,直接附上代码。

    public TreeNode search(TreeNode node, int value){
            if(node == null){
                return null;
            }
            if(node.getValue()>value){
                if(node.getLeftTreeNode() == null)
                    return null;
                return search(node.getLeftTreeNode(),value);
            }else if(node.getValue()<value){
                if(node.getRightTreeNode() == null)
                    return null;
                return search(node.getRightTreeNode(),value);
            }else{
                return node;
            }
        }
    

    5.二叉排序树的节点删除

      关于这个问题,实际上比较复杂,为了避免增大篇幅,我另起一篇笔记来记录这个知识点,点击链接查看。

    展开全文
  • 建立一棵二叉排序树

    千次阅读 多人点赞 2019-06-03 23:53:28
    二叉排序树(也称二叉查找树),或者是一棵空的二叉树,或者是具有下列性质的二叉树: ⑴ 若它的左子树不,则左子树上所有结点的值均小于根结点的值; ⑵ 若它的右子树不,则右子树上所有结点的值均大于根结点的...

    定义

    二叉排序树(也称二叉查找树),或者是一棵空的二叉树,或者是具有下列性质的二叉树:
    ⑴ 若它的左子树不空,则左子树上所有结点的值均小于根结点的值;
    ⑵ 若它的右子树不空,则右子树上所有结点的值均大于根结点的值;
    ⑶ 它的左右子树也都是二叉排序树。
    中序遍历二叉排序树可以得到一个按关键码的有序数列。

    建树

    脱胎于二叉树,区别是每个节点数据要进行比对,再进行插入,小插左,大插右,直接上代码,清楚明白。

    #include<bits/stdc++.h>
    using namespace std;
    #define N 100
    
    typedef  struct BiTNode
    {
        char data;
        struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    BiTree root=NULL;
    int n,k[N];
    
    void inOrder(BiTree T)//中序遍历 
    {
    
    	if(T!=NULL)
    	{
    	  inOrder(T->lchild);//左 
    	  printf("%d ",T->data);// 根 
    	  inOrder(T->rchild);//右 
    	}
    }
    
    void insert(int m)
    {
    	BiTree p1, p2;
    	if(root==NULL)
    	{
    	  	root=new BiTNode;
    	  	root->data=m;
    	  	root->lchild=root->rchild=NULL;
    	}
    	else
    	{
    		p1=root;
    		while(m!=p1->data)
    		{
    		    if((m<p1->data) && (p1->lchild!=NULL))
    		    {
    		    	p1=p1->lchild;
    			}
    		    else if((m>p1->data) && (p1->rchild!=NULL))
    		    {
    		    	p1=p1->rchild;
    			}
    		    else if((m<p1->data) && (p1->lchild==NULL))
    		    {
    		      	p2=new BiTNode;
    		      	p2->data=m;
    		      	p2->lchild=p2->rchild=NULL;
    		      	p1->lchild=p2;
    		      	return;
    		    }
    		    else if((m>p1->data) && (p1->rchild==NULL))
    		    {
    		      	p2=new BiTNode;
    		      	p2->data=m;
    		      	p2->lchild=p2->rchild=NULL;
    		      	p1->rchild=p2;
    		      	return;
    		    }
    		}
    	}
    }
    
    void create()
    {
    	cout<<"输入节点数量:";
    	cin>>n;
    	for(int i=0; i<n; i++)
    	{
    		cin>>k[i];
    	}
    	for(int i=0; i<n; i++)
    	{
    		insert(k[i]);
    	}
    }
    
    int main()
    {
    	create();
    	cout<<"中序遍历输出:"<<endl; 
    	inOrder(root);
    	return 0;
    }
    
    展开全文
  • 1二叉排序树 二叉排序树:BST( Binary Sort( Search)Tree,又称二叉查找树(Binary Search Tree),亦称二叉搜索树。对于二叉排序树的任何个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前...

    1、二叉排序树

    二叉排序树:BST( Binary Sort( Search)Tree,又称二叉查找树(Binary Search Tree),亦称二叉搜索树。对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小右子节点的值比当前节点的值大

    特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点

    比如针对前面的数据(7,3,10,12,5,1,9),对应的二叉排序树为:
    在这里插入图片描述

    2、二叉排序树的创建和遍历

    一个数组创建成对应的二叉排序树,并使用中序遍历二叉排序树,比如:数组为Aray(7,3,10,12,5,1,9),创建成对应的二叉排序树为:
    在这里插入图片描述

    3、二叉排序树的删除

    二叉排序树的删除情况比较复杂,有下面三种情况需要考虑:

    1. 删除叶子节点(比如:2,5,9,12)
    2. 删除只有一个子树的节点(比如:1)
    3. 删除有两个子树的节点(比如:7,3,10)

    操作思路分析
    在这里插入图片描述
    在这里插入图片描述

    4、二叉排序树的删除节点的代码实现

    package binarysorttree;
    
    /**
     * Create with IntelliJ IDAE
     *
     * @Author: JINLEI
     * @Description: 二叉排序树
     * @Date: 2022/3/15
     * @Time: 11:19
     **/
    public class BinarySortTreeDemo {
        public static void main(String[] args) {
            
            int[] arr = {7,3,10,12,5,1,9,2};
            BinarySortTree binarySortTree = new BinarySortTree();
            //循环添加节点到二叉排序树
            for (int i = 0; i < arr.length; i++) {
                binarySortTree.add(new Node(arr[i]));
            }
            //中序遍历二叉排序树
            System.out.println("中序遍历二叉排序树");
            binarySortTree.infixOrder();//1 3 5 7 9 10 12
    
            //测试删除叶子节点
            //binarySortTree.delNode(2);
            //binarySortTree.delNode(5);
            //binarySortTree.delNode(9);
            binarySortTree.delNode(1);
    //        binarySortTree.delNode(7);
            System.out.println("删除节点后");
            binarySortTree.infixOrder();
        }
    }
    
    //创建二叉排序树
    class BinarySortTree{
    
        private Node root;
    
        //查找要删除的节点
        public Node search(int value){
            if (root == null){
                return null;
            }else {
                return root.search(value);
            }
        }
        //查找父节点
        public Node searchParent(int value){
            if (root == null){
                return null;
            }else {
                return root.searchParent(value);
            }
        }
    
        /**
         *编写一个方法
         * 返回以node为根节点的二叉排序树的最小节点的值
         * 删除node为根节点的二叉排序树的最小节点
         * @param node 传入的节点(当做二叉排序树的根节点)
         * @return 返回的以node为根节点的二叉排序树的最小节点的值
         */
        public int delRightTreeMin(Node node){
            Node target = node;
            //循环的查找左节点,就回找到最小值
            while (target.left != null){
                target = target.left;
            }
            //这时target指向了最小节点
            //删除最小节点
            delNode(target.value);
            return target.value;
        }
    
        //删除节点
        public void delNode(int value){
            if (root == null){
                return;
            }else {
                //先去找到要删除的节点
                Node targetNode = search(value);
                //没有找到要删除的节点
                if(targetNode == null){
                    return;
                }
                //如果发现当前的二叉排序树只有一个节点
                if (root.left == null && root.right == null){
                    root = null;
                    return;
                }
    
                //找到targetNode的父节点
                Node parent = searchParent(value);
                //如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
                    //判断targetNode是父节点的左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {//是左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {//是右子节点
                        parent.right = null;
                    }
                }else if(targetNode.left != null && targetNode.right != null){//删除有两个子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                }else {
                    //删除只有一个子树的节点
                    //如果要删除的节点有左子节点
                    if (targetNode.left != null){
                        //如果targetNode是parent的左子节点
                        if (parent.left.value == value){
                            parent.left = targetNode.left;
                        }else {//targetNode是parent的右子节点
                            parent.right = targetNode.left;
                        }
                    }else {//如果要删除的节点有右子节点
                        //如果targetNode是parent的左子节点
                        if (parent.left.value == value){
                            parent.left = targetNode.right;
                        }else {//targetNode是parent的右子节点
                            parent.right = targetNode.right;
                        }
                    }
                }
            }
        }
    
        //添加节点的方法
        public void add(Node node){
            if (root == null){
                root = node;
            }else {
                root.add(node);
            }
        }
        //中序遍历
        public void infixOrder(){
            if (root != null){
                root.infixOrder();
            }else {
                System.out.println("二叉排序树为空,不能遍历");
            }
        }
    }
    
    //创建Node节点
    class Node{
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        /**
         *  查找要删除的节点
         * @param value 希望删除的节点的值
         * @return 如果找到返回该节点,否则返回null
         */
        public Node search(int value){
            if (value == this.value){//找到就是该节点
                return this;
            }else if (value < this.value){//如果要查找的值小于当前节点,向左子树递归查找
                if (this.left == null){
                    return null;
                }
                return this.left.search(value);
            }else{//如果要查找的值大于当前节点,向右子树递归查找
                if (this.right == null){
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 查找要删除的节点的父节点
         * @param value 要找到的节点的值
         * @return 返回的是要删除的节点的父节点,如果没有就返回null
         */
        public Node searchParent(int value){
            //如果当前节点就是要删除的节点的父节点
            if((this.left != null && this.left.value == value) ||
                    (this.right != null && this.right.value == value)){
                return this;
            }else {
                //如果查找的值小于当前节点的值,并且当前的节点的左子节点不为空
                if (value < this.value && this.left != null){
                    return this.left.searchParent(value);//向左子树递归查找
                }else if (value >=this.value && this.right != null){
                    return this.right.searchParent(value);//向右子树递归查找
                }else {
                    return null;//没有找到父节点
                }
            }
        }
    
        //添加节点
        //递归的形式添加,注意要满足二叉排序树的要求
        public void add(Node node){
            if (node == null){
                return;
            }
            //判断传入的节点值,跟当前子树根节点的值的关系
            if (node.value < this.value){
                //如果当前节点的左子树节点为null
                if (this.left == null){
                    this.left = node;
                }else {
                    //递归想左子树添加
                    this.left.add(node);
                }
            }else {//添加的节点值大于当前的节点值
                if (this.right == null){
                    this.right = node;
                }else {
                    //递归向右子树添加
                    this.right.add(node);
                }
            }
        }
        //中序遍历
        public void infixOrder(){
            if (this.left != null){
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null){
                this.right.infixOrder();
            }
        }
    }
    
    
    展开全文
  • 二叉排序树

    千次阅读 2021-08-22 22:25:22
    文章目录 二叉排序树 二叉排序树插入 查询 查找分析 插入 建立 二叉排序树删除    二叉排序树   二叉排序树: 或者是一棵空树;或者是具有下列性质的二叉树:(1)若它的左子树不,则左子树上所有结点的值均小于...
  • 二叉排序树总结

    2022-03-17 19:25:19
    二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: 左子树上所有结点的值均小于根结点的值; 右子树的所有结点的值均大于根结点的值; 他的左右子树也分别都是二叉排序树二叉排序树的查找过程 首先和根...
  • 什么是二叉排序树(BST) 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。一般情况下,查询效率比链表结构要高。 要求:对于二叉树中的任何个非叶子结点,要求左子结点...
  • 树-二叉排序树的构建

    2022-04-01 17:32:36
    二叉排序树介绍 二叉排序树:对于二叉排序树的任何个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。 特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点 、...
  • 二叉排序树,又称二叉查找树(BST(Binary Sort/Search Tree) )或者是一棵空树,或者是具有下列特性的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于根结点的值。 (2)若右子树非空,则右子树删所有...
  • 【数据结构】二叉排序树(C语言版)前言二叉排序树的定义二、二叉排序树的性质三、二叉排序树的操作二叉排序树常用存储结构二叉排序树的查找(递归实现)查找"二叉树T"中键值为 key 的节点(非递归实现)查找"二叉树...
  • C语言实现二叉排序树

    2022-03-02 17:39:50
    C语言实现二叉排序树
  • 它或则是树,或者是带有以下性质的二叉树:构造二叉排序树的目的,并不是为了顺序,而是为了提升查找和插入删除关键字的速度。以下程序DEV C++中安装运行通过。#include#include/*二叉树的二叉链表结点结构...
  • 图解二叉排序树(二叉查找树、二叉搜索树)的插入操作、查找操作、删除操作以及完整的代码实现
  • 。题目 给定个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由...二叉排序树的插入函数 遍历两树,每次判断遍历的相同位置的相同节点的data数据是不是一样。不管用什么前序,中序,
  • 文章收藏的好句子:坚持和放纵是永远对立的矛盾,好习惯的坚持就像春天...目录1、数列的查询和添加问题2、二叉排序树 2、1二叉排序树的介绍 2、2二叉排序树的创建和遍历 2、3二叉排序树的删除1、数列的查询和添加...
  • 二叉排序树(BST)

    2021-06-18 17:00:35
    二叉排序树(也称二叉查找树)。 性质:左子树结点值 < 根结点值 < 右子树结点值 所以对二叉排序树进行中序遍历,可以得到个递增的xu'l
  • 二叉排序树1、定义2、性质3、操作3.1 查找 ...(3)其左右子树本身又各是一棵二叉排序树。 \quad \quad总结起来就是根据结点的值有:左子树<根结点<右子树 \quad \quad如下图就是一棵二叉排序树: \quad
  • 《数据结构》实验报告班级:姓名:学号:E-mail:日期:◎实验题目: 建立二叉排序树...、需求分析1、本程序中,输入组数据,然后建立一棵二叉排序树存储这些元素,再中序遍历输出检验树建立是否正确,中序遍历输出的...
  • 二叉排序树的建立

    千次阅读 2022-05-08 21:30:59
    1) 将第个要创建的元素插入成为根节点。 2) 将元素值与结点值比较,如果元素值大于结点值,将此元素送往结点的右儿子结点,如果右儿子结点不是的,需要重复比较,否则创建结点将元素值插入。 3)如果元素值小于...
  • 插入过程: (1)若二叉排序树T为,则创建个key域为k的节点,将它作为根节点; (2)否则将k和根节点的关键字比较,若两者相等,则说明树中已有此关键字k,无须插入,直接返回0; (3)若kkey,则将k插入根节点...
  • 从键盘读入组数据,建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。 【基本要求】 建立二叉排序树并对其进行查找,包括成功和不成功两种情况,并给出查找长度 【选作内容】 实现二叉排序树的插入、...
  • 二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树: 1) 若左子树非空,则左子树上所有结点关键字均小于根结点的关键字值; 2) 若右子树非空,则右子树上所有结点关键字均大于根结点的关键字值; 3)...
  • 二叉排序树的删除

    2022-04-01 17:34:58
    二叉排序树的删除 二叉排序树的删除情况比较复杂,有以下三种情况需要考虑 1)删除叶子节点 (比如:2,5,9,10) 2) 删除只有个子树的节点(比如:1) 3)删除有两个子树的节点 (比如:7,3,10) 分析情况:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,960
精华内容 18,384
关键字:

在一棵空的二叉排序树