我勒个去啊。。。刚刚好不容易写了一篇博客,怎么突然就不见了。。只要再写一遍了。。它这个自动保存草稿真是坑爹啊。。受不鸟了。。。
这学期开了数据结构的课,刚刚上完树,正好在蓝杰也学到了树,今天,就实现下二叉搜索树。
所谓二叉搜索树,它的最主要特征就是对于任意一个节点X,它的所有的左子树上存放的关键字一定比X的关键字要小,而右子树上存放的则比X的要大。正是由于这种特性,使得我们在查找的时候特别容易,时间复杂度大概是O(log N)。下图就是一个二叉搜索树。
首先,定义一个节点类。
/* * 定义一个二叉树的节点类 */ public class Node { int data; Node root; Node right_child; Node left_child; Node parent; int position; public Node(int data){ this.data = data; } }
实现的方法如下:
1、MakeEmpty
这个方法用于将树初始化。
/* *将一棵二叉树置为空树的方法 */ public void MakeEmpty(Node root){ if(root != null){ MakeEmpty(root.right_child); MakeEmpty(root.left_child); root = null; } System.out.println("该树为空树!"); }
2、Find
这个方法用来查找某一元素,需要传入你所要查找的元素以及一个树的根节点作为参数。因为二叉搜索树的特点,查找是一件非常容易的事。
/* * 在一棵二叉搜索树中查找某一元素的方法 */ public Node Find(int x, Node root){ if(root == null){ System.out.println("该树为空树!"); return null; } if(x < root.data){ return Find(x, root.left_child); }else if(x > root.data){ return Find(x, root.right_child); } else return root; }
3、FindMin 和 FindMax
分别用于查找最小和最大的元素。需要传入一个树的根节点作为参数。对于FindMin只需要一直查找它的左节点直到为空即可,FindMax则只需要查找右节点。这里运用了递归和非递归两种方法来实现。
/* *在一棵二叉搜索树中查找最小的元素的方法(递归实现) */ public Node FindMin(Node root){ if(root == null){ System.out.println("该树为空树!"); return null; } else if(root.left_child == null){ return root; }else return FindMin(root.left_child); } /* * 在一棵二叉搜索树中查找最大元撒的方法(非递归实现) * 从根节点开始,一直查找它的右子树,直到最后一层 */ public Node FindMax(Node root){ Node node = root; if(root == null){ System.out.println("该树为空!"); return null; } else{ while(node.right_child != null){ node = node.right_child; } return node; } }
4、Insert
插入的方法在概念上简单的,需要传入你所要插入的元素及根节点作为参数。对于要插入的元素,判断它和节点之间的关系,直到找到它的位置。比如对于上图所示的树,我们需要插入一个新的元素“5”,首先判断它和根节点的关系,应该存放在左子树上,再判断它和“2”的关系,应该存放在有子树上,再判断和“4”的关系,应该存放在右子树上,而“4”的右子树为空,于是我们就找到了存放它的位置。
/* * 向一棵二叉搜索树中添加元素的方法 */ public Node Insert(int x, Node root){ Node node = new Node(x); if(root == null){ root = node; return root; }else{ Node current_node = root; Node parent_node; while(true){ parent_node = current_node; if(x < current_node.data){ current_node = current_node.left_child; if(current_node == null){ parent_node.left_child = node; return root; } }else{ current_node = current_node.right_child; if(current_node == null){ parent_node.right_child = node; return root; } } } } }
5、Delete
喜闻乐见的又到了删除的时候,需要传入你所要删除的元素已经树的根节点作为参数。二叉搜索树的删除是比较复杂的。它可能会遇到三种情况,第一种是要删除的节点没有子节点,这无疑是最简单的一种。第二种是它由一个子节点,这种情况也是比较简单的,只需要记下要删除的节点的父节点即可。第三种是要删除的节点有两个子节点,这时候我采取的策略是用要删除的节点的右子树上存放元素最小的节点来代替你所要删除的节点。
/* * 删除二叉搜索树中的一个元素 */ public Node Delete(int x, Node root){ Node node = root; Node node1 = Find(x, root); if(node1 == null){ System.out.println("要删除的元素不存在!"); }else if((node1.right_child != null) && (node1.left_child != null)){ //判断要删除的节点是否有两个子节点 //如果有两个子节点,则该用该节点的右子树的最小元素的子节点来代替该节点 //判断要删除的及节点是它的父节点的左节点还是右节点 if(node1.data < node1.parent.data){//左节点 node1.parent.left_child = FindMin(node1.right_child); FindMin(node1.right_child).parent = node1.parent; }else{ node1.parent.right_child = FindMin(node1.right_child); FindMin(node1.right_child).parent = node1.parent; } FindMin(node1.right_child).left_child = node1.left_child; node1.left_child.parent = FindMin(node1.right_child); }else{ //如果要删除的节点只有一个子节点,则让它的父节点指向它的子节点 if(node1.data < node1.parent.data){//左节点 if(node1.left_child == null){ node1.parent.left_child = node1.right_child; node1.right_child.parent = node1.parent; }else{ node1.parent.left_child = node1.left_child; node1.left_child.parent = node1.parent; } }else{ if(node1.left_child == null){ node1.parent.left_child = node1.right_child; node1.right_child.parent = node1.parent; }else{ node1.parent.left_child = node1.left_child; node1.left_child.parent = node1.parent; } } } return root; }
6、PrintTree
遍历二叉搜索树将其打印。需要传入根节点作为参数。这里用的是中序遍历的方法。
/* * 遍历打印二叉搜索树 */ public void PrintTree(Node root){ Node node = root; if(node.left_child != null){ PrintTree(node.left_child); } System.out.println(node.data); if(node.right_child != null){ PrintTree(node.right_child); } }
相关推荐
函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针; 函数Delete将X从二叉搜索树BST中删除,并返回结果树的根结点指针;如果X不在树中,则打印一行Not Found并返回原树的根结点指针; 函数Find在二叉搜索树...
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的...
一、实验目的 (1)理解动态查找表的动态生成过程; (2)任意给出一组数(不...(1)定义二叉排序树的数据结构; (2)实现二叉排序树的插入算法与查找算法,并建立二叉排序树; (3)进行数据查找和建树过程的比较。
主要介绍了javascript数据结构之二叉搜索树实现方法,较为详细的分析了二叉搜索树的概念、原理与JavaScript实现二叉搜索树的方法,对于学习JavaScript数据结构具有一定参考借鉴价值,需要的朋友可以参考下
基于C语言的数据结构-二叉搜索树bitTree
数据结构 二叉排序树 二叉搜索树 java swing图形界面实现
此程序用C++实现了数据结构中二叉搜索树,希望有所帮助
用二叉链表作存储结构。 要求: (1)以回车(0)为输入结束标志,输入数列L,生成一棵二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果; (3)计算二叉排序树T查找成功的平均查找长度,输出结果; (4)输入元素x,查找...
数据结构二叉树二叉搜索树堆相关C++代码.docx
1.实现二叉搜索树的基本操作 2.包括建立,查找,删除,显示 3.得到最长路径和最短路径,并能分别计算长度
数据结构课程实验C++实现霍夫曼树和二叉搜索树
数据结构经典应用,VC/C++,模板类,顺序查找,二分查找,二叉搜索树
二叉搜索树有关应用,数据结构课程设计 1.用二叉链表作存储结构 (1)以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果; (3)计算二叉排序树T的平均查找长度,输出结果;...
二叉排序树数据结构实验,一个程序实现二叉排序树的基本运算
计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双链表,每个节点包含一些数据,以及两个指向其他节点的指针;它们在这些节点彼此...
二叉搜索树具有一些重要特性,如有序性、唯一性和高度平衡性,这些特性使得它在数据结构中有着广泛的应用。 二叉搜索树的应用 二叉搜索树常用于实现查找表、排序和范围查询等功能,其高效的操作性能使得它在计算机...
是我大二数据结构上机考试要做的题目 分别是 客户消费积分管理系统 校园导航问题 判别否为二叉排序树 源码我也是在csdn找到的 但是他们都有些问题 要么编译有问题 要么不符合报告要求 稍微和报告要求有关 还有就...
python数据结构与算法,二叉搜索树的操作,来源中山大学软件学院考试参考代码