二叉搜索树 客官°小女子只卖身不卖艺 2022-05-31 00:50 243阅读 0赞 二叉搜索树的特征定义就是:一个节点的左子节点的关键字值小于这个节点,右子节点的关键字大于或等于这个父节点 package Trees; import java.util.Scanner; import java.util.Stack; /\*\* \* 二叉搜索树 \* @author 灰太狼 \* \*/ class Node\{ public int iData; public double dData; public Node leftChild;//左节点 public Node rightChild;//右节点 public void displayNode() \{ System.out.println("\{"+iData+","+dData+"\}"); \} \} class Tree\{ private Node root; public Tree()\{ root=null; \} //根据关键字查找节点 public Node find(int key) \{ Node current=root;//从根节点开始往下查找 while(current.iData!=key) \{ if(key<current.iData) \{ current=current.leftChild;//往左节点找 \}else \{ current=current.rightChild;//往右节点找 \} if(current==null) \{//如果没有子节点,找不到,返回null return null; \} \} return current;//找到,返回该节点 \} //插入新节点 public void insert(int id,double dd) \{ Node newNode=new Node(); newNode.iData=id; newNode.dData=dd; if(root==null) \{ root=newNode; \}else \{ Node current=root; Node parent; while(true) \{ parent=current; if(id<current.iData) \{//进入左节点 current=current.leftChild; if(current==null) \{//没有左节点,新节点插入左节点 parent.leftChild=newNode; return; \} \}else \{//进入右节点 current=current.rightChild; if(current==null) \{//没有右节点,新节点插入右节点处 parent.rightChild=newNode; return; \} \} \} \} \} //根据关键字删除节点 public boolean delete(int key) \{ Node current=root; Node parent=root; boolean isLeftChild=true; while(current.iData!=key) \{ parent=current; if(key<current.iData) \{//进入左节点 isLeftChild=true; current=current.leftChild;//往左节点下 \}else \{ isLeftChild=false; current=current.rightChild;//进入右节点 \} if(current==null) \{//没有找到,返回null return false; \} \}//end while //如果没有子节点,直接删除 if(current.leftChild==null&¤t.rightChild==null) \{ if(current==root) \{ root=null;//如果是根节点,树为空 \}else if(isLeftChild) \{ parent.leftChild=null; \}else \{ parent.rightChild=null; \} \}//if end //如果没有右节点,左子树代替 else if(current.rightChild==null) \{ if(current==root) \{ root=current.leftChild; \}else if(isLeftChild) \{ parent.leftChild=current.leftChild; \}else \{ parent.rightChild=current.leftChild; \} \}//else end //如果没有左节点,右子树代替 else if(current.leftChild==null) \{ if(current==root) \{ root=current.rightChild; \}else if(isLeftChild)\{ parent.leftChild=current.rightChild; \}else \{ parent.rightChild=current.rightChild; \} \}//else end //2个子树,后继节点替代 else \{ Node successor=getSuccessor(current); if(current==root) \{ root=successor; \}else if(isLeftChild) \{ parent.leftChild=successor; \}else \{ parent.rightChild=successor; \} successor.leftChild=current.leftChild; \}//else end return true; \} private Node getSuccessor(Node delNode) \{ // TODO Auto-generated method stub Node successorParent=delNode; Node successor=delNode; Node current=delNode.rightChild; while(current!=null) \{ successorParent=successor; successor=current; current=current.leftChild; \} if(successor!=delNode.rightChild) \{ successorParent.leftChild=successor.rightChild; successor.rightChild=delNode.rightChild; \} return successor; \} public void traverse(int traverseType) \{ switch(traverseType) \{ case 1: System.out.println("preorder traversal:"); preOrder(root); break; case 2: System.out.println("inorder traversal:"); inOrder(root); break; case 3: System.out.println("postorder traversal"); postOrder(root); break; \} System.out.println(); \} private void preOrder(Node localRoot) \{ if(localRoot!=null) \{ System.out.println(localRoot.iData+" "); preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); \} \} private void inOrder(Node localRoot) \{ if(localRoot!=null) \{ inOrder(localRoot.leftChild); System.out.println(localRoot.iData+" "); inOrder(localRoot.rightChild); \} \} private void postOrder(Node localRoot) \{ if(localRoot!=null) \{ postOrder(localRoot.leftChild); postOrder(localRoot.rightChild); System.out.println(localRoot.iData+" "); \} \} public void displayTree() \{ Stack globalStack=new Stack(); globalStack.push(root); int nBlanks=32; boolean isRowEmpty=false; System.out.println("--------"); while(isRowEmpty==false) \{ Stack localStack=new Stack(); isRowEmpty=true; for(int j=0;j<nBlanks;j++) \{ System.out.print(' '); \} while(globalStack.isEmpty()==false) \{ Node temp=(Node)globalStack.pop(); if(temp!=null) \{ System.out.print(temp.dData); localStack.push(temp.leftChild); localStack.push(temp.rightChild); \} if(temp.leftChild!=null||temp.rightChild!=null) \{ isRowEmpty=false; \}else \{ System.out.println("--"); localStack.push(null); localStack.push(null); \} for(int j=0;j<nBlanks\*2+2;j++) \{ System.out.print(' '); \} \}//end while System.out.println(); nBlanks/=2; while(localStack.isEmpty()==false) \{ globalStack.push(localStack.pop()); \} System.out.println("-----------"); \} \}//end \}//end class public class TreeApp \{ public static void main(String \[\]args) \{ Scanner s=new Scanner(System.in); int value; Tree theTree=new Tree(); theTree.insert(50, 1.5); theTree.insert(25, 1.2); theTree.insert(75, 1.7); theTree.insert(12, 1.5); theTree.insert(37, 1.2); theTree.insert(43, 1.7); theTree.insert(30, 1.5); theTree.insert(30, 1.2); theTree.insert(87, 1.7); theTree.insert(93, 1.5); theTree.insert(97, 1.5); while(true) \{ System.out.println("enter first"); System.out.println("1显示tree ,2insert ,3find ,4delete, or 5traverse"); int choice=s.nextInt(); switch(choice) \{ case 1: theTree.displayTree(); break; case 2: System.out.println("enter value to insert"); value=s.nextInt(); theTree.insert(value, value+0.9); break; case 3: System.out.println("enter value to find:"); value=s.nextInt(); Node found=theTree.find(value); if(found!=null) \{ System.out.println("found:"); found.displayNode(); System.out.println(); \}else \{ System.out.println("don't find it"+value); \} break; case 4: System.out.println("enter value to delete"); value=s.nextInt(); boolean didDelete=theTree.delete(value); if(didDelete)\{ System.out.println("deleted:"+value); \}else \{ System.out.println("can't delete:"+value); \} break; case 5: System.out.println("enter type 1,2,3"); value=s.nextInt(); theTree.traverse(value); break; default: System.out.println("invalid entry"); \} \} \} \}//end class
相关 二叉搜索树 1 二叉搜索树 二叉搜索树是指一棵树的左子树上所有的节点都小于它的根节点;右子树上所有的节点都大于它的根节点。且对于它的所有子树都是如此。基于这个性质,当我们对二叉搜索树 心已赠人/ 2023年09月28日 09:18/ 0 赞/ 73 阅读
相关 二叉搜索树 在计算机术语中,二叉搜索树又叫二叉查找树、二叉排序树。 二叉搜索树(Binary Search Tree)的定义: 它或者是一棵空树,或者是具有下列性质的二叉树: 若它的 Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 157 阅读
相关 二叉搜索树 搜索树数据结构支持许多动态集合操作,包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此,我们使用一 ╰+哭是因爲堅強的太久メ/ 2022年08月14日 01:50/ 0 赞/ 156 阅读
相关 二叉搜索树 二叉搜索树的特征定义就是:一个节点的左子节点的关键字值小于这个节点,右子节点的关键字大于或等于这个父节点 package Trees; import java.ut 客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 244 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于 ゝ一世哀愁。/ 2022年04月24日 11:20/ 0 赞/ 202 阅读
相关 二叉搜索树 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy た 入场券/ 2022年03月17日 02:18/ 0 赞/ 241 阅读
相关 二叉搜索树 思路 二叉排序树,二叉搜索树好像都行,原理应该都懂,比较基础,但要写出来还是有相当大的难度的。 查找 查找比较简单,基本都是一个while就解决。但查前驱与后继较 短命女/ 2021年12月21日 09:15/ 0 赞/ 230 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不 小咪咪/ 2021年12月20日 02:53/ 0 赞/ 254 阅读
相关 二叉搜索树 二叉搜索树 C++实现![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9 今天药忘吃喽~/ 2021年12月14日 08:47/ 0 赞/ 233 阅读
相关 二叉搜索树 二叉搜索树 基本概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 300 阅读
还没有评论,来说两句吧...