java数据结构之二叉树及对应的遍历

绝地灬酷狼 2022-04-03 07:16 66阅读 0赞

java代码如下：

package 数据结构;
    
    public class Tree {
         NodeTree root;//根节点
        public void insert(long value,String name){//向树中插入元素
        	NodeTree current=root;//给根节点取个别名
        	NodeTree newnode=new NodeTree(value,name);//初始化要插入的结点
        	while(true){//死循环，不断往下查找，直到找到合适的位置
        		NodeTree parent;
        		if(root==null){//当根节点为空，则插入的结点即为空
        			root=newnode;
        			return;//结束循环
        		}
        		else{
        			parent=current;//因为当前结点已经有元素了，则需要往其左子树或右子树进行插入，则该结点为它们的父子树
        			if(current.data>value){
        				current=current.LeftChild;//插入的数据比当前结点的小，往左边移，此结点的左儿子为新的父亲
        				if(current==null){//当前结点的左儿子为空，则此时插入的为左儿子
        					parent.LeftChild=newnode;
        					return;
        				}
        			}
        			else{
        				current=current.RightChild;//插入的数据比当前结点的大，往右边移，此结点的右儿子为新的父亲
        				if(current==null){//当前结点的右儿子为空，则此时插入的为右儿子
        					parent.RightChild=newnode;
        					return;
        				}
        			}
        		}
        	}
        }
        public NodeTree getprocess(NodeTree node){//得到代替要删除结点的结点，与下面对应
        	NodeTree process=node;
        	NodeTree parentprocess=node;
        	NodeTree current=node.RightChild;//开始从该结点的右儿子开始，找它额左儿子
        	while(current!=null){//因为要到位空才能结束循环，所以要定义两个结点，一个用来保存找到的结点，即process，另一个用来保存它的父亲，即parentprocess
        		parentprocess=process;//找到结点的爸爸
        		process=current;//要找的结点
        		current=current.LeftChild;//查找出左儿子为空的结点
        	}
        	if(process!=node.RightChild){//如果代替的结点不刚好是其右结点的话，则需要重新布置一下删除结点右边子树的关系，首先把代替结点删除，然后再把它移动到要删除结点的位置
        		parentprocess.LeftChild=process.RightChild;//把代替的结点删除，因为它左儿子已经为空，则只看右儿子即可
        		process.RightChild=node.RightChild;//把代替结点与之前结点的子树构造关系
        	}
        	return process;
        }
        public NodeTree find(long value){//查找结点
        	NodeTree current=root;//从根节点开始
        	while(current.data!=value){//当前结点的值不符合
        		if(current.data>value){//小于该节点的值往左儿子找
        			current=current.LeftChild;
        		}
        		else{
        			current=current.RightChild;//大于该节点的值往右儿子找
        		}
        		if(current==null){//等于null即没找到，
        			return null;//返回null
        		}
        
        	}
        	return current;//找到了结束循环，返回该结点
        }
        public void FrontOrder(NodeTree node){//先序遍历，递归，中左右
        	if(node!=null){
        		System.out.println(node.data+","+node.name);
        	
        	FrontOrder(node.LeftChild);//先序遍历左子树
        	FrontOrder(node.RightChild);//先序遍历右子树
        }}
        public void InOrder(NodeTree node){//中序遍历，递归，左中右
        	if(node!=null){
        		InOrder(node.LeftChild);//先中序遍历左子树
        		System.out.println(node.data+","+node.name);//遍历跟结点
        		InOrder(node.RightChild);//中序遍历右子树
        	}
        }
       public void LastOrder(NodeTree node){//后序遍历，左右中，递归
    	   if(node!=null){
    		   LastOrder(node.LeftChild);
    		   LastOrder(node.RightChild);
    		   System.out.println(node.data+","+node.name);
    	   }
       }
       public boolean delete(long value){//删除结点，有几种不同的情况
    	   NodeTree current=root;
    	   NodeTree parent=root;
    	   boolean isleft=true;
    	   while(current.data!=value){//先找到该节点的位置
    		   parent=current;//留下父节点，让删除更方便
    		   if(current.data>value){
    			   current=current.LeftChild;
    			   isleft=true;//该结点是左儿子
    		   }
    		   else{
    			   current=current.RightChild;
    			   isleft=false;//该结点是右儿子
    		   }
    		   if(current==null){
    			   return false;
    		   }
    	   }
    	   if(current.LeftChild==null&&current.RightChild==null){//删除叶子结点，没有儿子的那种
    		   if(current==root){//如果是根节点，则它只有一个结点，把它为null即删除
    			   root=null;
    		   }
    		   else if(isleft){//如果它是左儿子，它又没有儿子，则把它父亲的左儿子置为空即可删除
    			   parent.LeftChild=null;
    		   }
    		   else{
    			   parent.RightChild=null;//如果它是右儿子，它又没有儿子，则把它父亲的右儿子置为空即可删除
    		   }
    	   }
    	   //删除只有一个儿子的父节点，首先判断父节点拥有的是左儿子还是右儿子，再根据前面的判断父节点是他爸爸的哪个儿子，把他的儿子赋给他爸爸
    	   else if(current.LeftChild==null){//该结点有一个右儿子
    		   if(current==root){//如果该结点是根节点，它还有一个儿子，则把它的儿子变为根节点即可删除它啦
    			   root=current.RightChild;
    		   }
    		   else if(isleft){//如果该结点是它父亲的左儿子，则将它的右儿子变为它父亲的左儿子即可删除它
    			   parent.LeftChild=current.RightChild;
    		   }
    		   else{//如果该结点是它父亲的右儿子，则将它的右儿子变为它父亲的右儿子即可删除它
    			   parent.RightChild=current.RightChild;
    		   }
    	   }
    	   else if(current.RightChild==null){//该结点有一个左儿子
    		   if(current==root){//如果该结点是根节点，它还有一个儿子，则把它的儿子变为根节点即可删除它啦
    			   root=current.LeftChild;
    		   }
    		   else if(isleft){//如果该结点是它父亲的左儿子，则将它的左儿子变为它父亲的左儿子即可删除它
    			   parent.LeftChild=current.LeftChild;
    		   }
    		   else{//如果该结点是它父亲的右儿子，则将它的左儿子变为它父亲的右儿子即可删除它
    			   parent.RightChild=current.LeftChild;
    		   }
    	   }
    	   //删除有两个儿子的父节点，首先得到代替它的一个节点，一般是要删除的结点的右儿子的左儿子的左儿子。。。。直到左儿子为空
    	   else{
    		   NodeTree t=getprocess(current);//首先利用这个函数找到代替它的结点
    		   if(root==current){//如果为根节点,则让代替的结点代替根节点即可
    			   root=t;
    			   
    		   }
    		   else if(isleft){//如果是一个左儿子，则让代替的结点代替它父亲的左儿子即可
    			   parent.LeftChild=t;
    			  
    		   }
    		   else{
    			   parent.RightChild=t;
    			   
    		   }
    		   t.LeftChild=current.LeftChild;//因为函数已经构造了代替结点和原结点的右儿子关系，所以最后只需要更新一下左儿子与代替结点的关系就可以啦
    	   }
    	   return true;
       }
    }

结点Node类：

package 数据结构;
    
    public class NodeTree {//二叉树的结点
        long data;//数据
        String name;
        NodeTree LeftChild;//左儿子
       NodeTree RightChild;//右儿子
       public NodeTree(long data,String name){
    	   this.data=data;
    	   this.name=name;
       }
    }

测试：

package 数据结构;
    
    public class TestTree {
      public static void main(String args[]){
    	  Tree a=new Tree();
    	  a.insert(10,"liyong");
    	  a.insert(3,"liyttt");
    	  a.insert(2, "pp");
    	  a.insert(5,"liyi");
    	  a.insert(6,"liyu");
    	  a.insert(20,"liyo");
    	  a.insert(45,"ty");
    	  //a.find(5);
    	  //System.out.println(a.find(5).data+a.find(5).name);
    	  System.out.println("先序遍历*************");
    	  a.FrontOrder(a.root);
    	  System.out.println("中序遍历**************");
    	  a.InOrder(a.root);
    	  System.out.println("后序遍历************");
    	  a.LastOrder(a.root);
    	  a.delete(3);
    	  System.out.println("删除3结点的先序遍历*************");
    	  a.FrontOrder(a.root);
      }
    }

输出结果如下：

先序遍历\*\*\*\*\*\*\*\*\*\*\*\*\*  
10,liyong  
3,liyttt  
2,pp  
5,liyi  
6,liyu  
20,liyo  
45,ty  
中序遍历\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
2,pp  
3,liyttt  
5,liyi  
6,liyu  
10,liyong  
20,liyo  
45,ty  
后序遍历\*\*\*\*\*\*\*\*\*\*\*\*  
2,pp  
6,liyu  
5,liyi  
3,liyttt  
45,ty  
20,liyo  
10,liyong  
删除3结点的先序遍历\*\*\*\*\*\*\*\*\*\*\*\*\*  
10,liyong  
5,liyi  
2,pp  
6,liyu  
20,liyo  
45,ty

好啦,这次就到这里啦，有问题可以和我留言哦！

邮箱：2321591758@qq.com

其他博客的链接：

[Github个人网站][Github]      [知乎][Link 1]      [简书][Link 2]

欢迎各位访问哦，这次就到这里啦！

[Github]: http://www.imlowliness.club
[Link 1]: https://www.zhihu.com/people/li-yong-ji-suan-ji/activities
[Link 2]: https://www.jianshu.com/u/6c1284ced65e