1。树结构树是一种非常特殊的数据结构。树的数据结构被称为“树”，因为它看起来像一棵树。但是这棵树画出来的图，看起来就像一棵倒过来的树，树根在上面，树叶在下面。树是一种图形。树和图的区别在于树没有环，而图可以有环。树状图是一种数据结构，它是由n（n>=1）个有限节点组成的一组层次关系。它被称为“树”，因为它看起来像一棵倒置的树，这意味着它的根朝上，叶子朝下。2、为什么会有树状结构2.1树状结构是一种自然的组织结构。比如电脑中的一个文件夹，我们需要找到一个特定的文件，我们需要去某个文件夹中找到这个文件，电脑的文件存储结构来源于生活。另一个例子是图书馆。我们知道图书馆里有历史、数学和计算机课。如果我们要找关于java的书籍，我们需要在Java的计算机类中找到我们需要的书籍，比如公司中的层级结构。:CEO，HRCTO等等，还有我们常见的家谱等等，都是类似树状结构的。数据采用树结构后，效率会更高。3.二叉搜索树3.1特点二叉搜索树是一种动态数据结构二叉搜索树也就是二叉树（也叫多叉树）。二叉搜索树的每个节点的值都大于其左子树中所有节点的值，而每个节点的值都小于其右子树中所有节点的值。存储在值中的元素必须是可比较的。在Java中，二叉搜索树存储的数据类型必须实现Comparable接口，或者使用额外的比较器来实现每个子树也是一棵二叉搜索树。二叉搜索树有一个唯一的根。结点，二叉树的底部是它的叶子结点二叉搜索树有一个只为根的结点，每个结点最多有两个孩子（左孩子称为左孩子，右孩子称为右孩子），并且每个节点至多有一个父二叉搜索树，自然是递归的。每个节点的左子树也是一棵二叉树。每个节点的右子树也是一棵二叉树。二叉树不一定是满的。计算机也是二叉树，空的也是二叉树。4.具体代码实现在进行相关操作之前，先定义一个支持泛型的节点类，用于存储二叉搜索树各个节点的信息。此类用作二叉搜索树的内部类。二叉查找树的类声明和Node节点类声明如下：4.1添加元素二叉查找树添加元素的非递归写法与链表非常相似。由于二叉搜索树本身的递归特性，使用递归向二叉搜索树添加元素是非常方便的。代码实现：//添加到二叉搜索树中向搜索树中添加一个新元素epublicvoidadd(Ee){root=add(root,e);}//将元素E插入到以Node为根的二叉搜索树中，递归算法//插入新节点根后返回二叉查找树privateNodeadd(Nodenode,Ee){if(node==null){size++;returnnewNode(e);}if(e.compareTo(node.e)<0)node.left=add(node.left,e);elseif(e.compareTo(node.e)>0)node.right=add(node.right,e);returnnode;}4.2查找元素由于二叉查找树没有下标，所以我们需要为二叉查找树的查找操作定义一个contains()方法来检查二叉查找树是否包含一个元素，并返回一个布尔变量代码实现：//SeeifthebinarysearchisDoesthesearchtreecontaintheelementpublicbooleancontains(Ee){returncontains(root,e);}//查看以Node为根的二叉搜索树是否包含元素e，递归算法privatebooleancontains(Nodenode,Ee){if(node==null)returnfalse;if(e.compareTo(node.e)==0)returntrue;elseif(e.compareTo(node.e)<0)returncontains(node.left,e);else//e.compareTo(node.e)>0returncontains(node.right,e);}4.3遍历操作1、什么是遍历操作？在遍历左右子节点之前，遍历顺序：当前节点->左子节点->右子节点中序遍历：当前节点的遍历在左右子节点的遍历中间，遍历顺序:leftchild->currentnode->Rightchildpost-ordertraversal：当前节点的遍历在遍历左右子节点之后，遍历顺序：leftchild->rightchild->currentnode2.前序遍历//二叉搜索树前序遍历publicvoidpreOrder(){preOrder(root);}//前序遍历以Node为根的二叉搜索树，递归算法privatevoidpreOrder(Nodenode){if(node==null)return;System.out.println(node.e);preOrder(node.left);preOrder(node.right);}publicvoidpreOrderNR(){Stackstack=newStack<>();stack.push(root);而(!stack.isEmpty()){Nodecur=stack.pop();系统输出文件rintln(cur.e);if(cur.right!=null)stack.push(cur.right);if(cur.left!=null)stack.push(cur.left);}}三.中序遍历//二叉查找树的中序遍历publicvoidinOrder(){inOrder(root);}//以Node为根的二叉查找树的中序遍历，递归算法privatevoidinOrder(Nodenode){if(node==null)return;inOrder(node.left);System.out.println(node.e);inOrder(node.right);}4.后序遍历//二叉搜索树的后序遍历publicvoidpostOrder(){inOrder(root);}publicvoidlevelOrder(){Queueq=newLinkedList();q.add(root);while(!q.isEmpty()){Nodecur=q.remove();System.out.println(cur.e);if(cur.left!=null)q.add(cur.left);if(cur.right!=null)q.add(cur.right);}}//二叉搜索树的后序遍历根植于Node，递归算法privatevoidpostOrder(Nodenode){if(node==null)return;inOrder(node.left);inOrder(node.right);System.out.println(node.e);}五、理解非递归写法前后二叉查找树的前序
