锐客网

  1. 首页 > 睿知 > it技术 > >

#yyds干货盘点# 二叉搜索树

IT知识干货二叉搜索树

莫问天涯路几重，轻衫侧帽且从容。这篇文章主要讲述#yyds干货盘点# 二叉搜索树相关的知识，希望能为你提供帮助。
二叉搜索树的特征定义就是：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字大于或等于这个父节点
【#yyds干货盘点# 二叉搜索树】?

import java.util.Scanner;
import java.util.Stack;

/**
* 二叉搜索树
*
*/
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=https://www.songbingjia.com/android/id;
newNode.dData=https://www.songbingjia.com/android/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& & current.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=https://www.songbingjia.com/android/s.nextInt();
theTree.insert(value, value+0.9);
break;
case 3:
System.out.println("enter value to find:");
value=https://www.songbingjia.com/android/s.nextInt();
Node found=theTree.find(value);
if(found!=null)
System.out.println("found:");
found.displayNode();
System.out.println();
else
System.out.println("dont find it"+value);

break;
case 4:
System.out.println("enter value to delete");
value=https://www.songbingjia.com/android/s.nextInt();
boolean didDelete=theTree.delete(value);
if(didDelete)
System.out.println("deleted:"+value);
else
System.out.println("cant delete:"+value);


break;
case 5:
System.out.println("enter type 1,2,3");
value=https://www.songbingjia.com/android/s.nextInt();
theTree.traverse(value);
break;
default:
System.out.println("invalid entry");





//end class


    推荐阅读


    上一篇：#yyds干货盘点#CCNA学习记录8

    下一篇：视频课程上线（域账号到期提前邮件提醒-AD域日常维护实战）