【数据结构与算法】六、手动实现树结构代码示例

男娘i 2023-10-09 14:31 92阅读 0赞

上一篇[【数据结构与算法】五、树结构-从二叉树到B+Tree][-_B_Tree]

#### 文章目录 ####

*  1、二叉树：
 *  2、跳表结构的实现
 *  3、中序遍历递归写法
 *  4、中序遍历递归写法
 *  5、树的各种遍历方式：

## 1、二叉树： ##

/**
     * 二叉树：
     *      就是单向链表中的节点中持有两个
     *      指向下一个引用的变量，且下一个
     *      引用不能去指向原有树中出现过的
     *      元素。
     *      二叉树的每个节点最多只能有两个子节点。
     *      如果有往回指向的子节点引用那么在查询时就会往回检索，
     *      那么这个数据结构就是图。
     *      增加、删除、修改的时间复杂度均为O(1)，
     *      查询的时间复杂度为O(n)，完全和链表一样
     * 
     * 二叉搜索树：
     *      在二叉树定义的基础上，附加一条对所有节点其
     *      左子树所有的节点必须小于根节点，右子树
     *      所有的节点必须大于根节点。
     *      
     *      因为其在增加删除、修改的时候都需要先查询一次应该存放的位置，
     *      所以其增加、删除、修改和查询的时间复杂度均为O(log(n))
     */
    public class BinarySearchTree {
        
        
        /*
         * 二叉树搜索树的根节点
         */
        private BinarySearchTreeNode<Integer> root;
        
        
        
        /**
         * 递归添加节点方法
         * @param root   根节点
         * @param item      值
         * @return  添加后的根节点
         */
        private BinarySearchTreeNode<Integer> addRecursive(BinarySearchTreeNode<Integer> root, int item) {
        
            //如果根节点为空，创建一个节点返回
            if (root == null) {
        
                return new BinarySearchTreeNode<Integer>(item);
            }
            //如果要添加的节点小于根节点则放到左子树中
            if (item < root.item) {
        
                root.left = addRecursive(root.left, item);
            } else if (item > root.item) {
        //如果要添加的节点大于根节点则放到右子树中
                root.right = addRecursive(root.right, item);
            } else {
        
                //如果要添加的节点等于根节点则返回根节点
                return root;
            }
         
            return root;
        }
        
        /**
         * 递归查询是否包含方法
         * @param root      根节点
         * @param item  需要查询的值
         * @return      是否包含
         */
        private boolean containsNodeRecursive(BinarySearchTreeNode<Integer> root, int item) {
        
            //如果根节点为空直接返回false
            if (root == null) {
        
                return false;
            } 
            //如果要查询的值就是根节点那么直接返回true
            if (item == root.item) {
        
                return true;
            } 
            //递归寻找：如果当前值小于等于根则递归左边，否则递归右边
            return item <= root.item
              ? containsNodeRecursive(root.left, item)
              : containsNodeRecursive(root.right, item);
        }
        
        
        
        /**
         * 对外暴露添加节点的方法
         * @param item  需要添加的元素
         */
        public void add(int item){
        
            this.root = addRecursive(root, item);
        }
        
        /**
         * 对外暴露是否包含节点的方法
         * @param item
         * @return
         */
        public boolean contains(int item){
        
            return containsNodeRecursive(root, item);
        }
        
        /**
         * 对外提供一个删除的方法
        * @param item		要删除的元素
        * @return		返回删除是否成功
         */
        public boolean remove(int item){
        
        	//将根节点设置为删除后的返回值
        	root = removeRecursive(root, item);
        	return true;
        }
        
        
        /**
         * 递归删除节点方法
        * @param current		需要删除的节点
        * @param item 	要删除的元素
        * @return		被删除的节点
         */
        private BinarySearchTreeNode<Integer> removeRecursive(
        				BinarySearchTreeNode<Integer> current,int item){
        
        	
        	//校验入参
        	if(current == null){
        
        		return null;
        	}
        	
        	//如果当前节点是要删除的节点就执行删除
        	if(current.item == item){
        
        		/*
            	 * 那么删除节点就需要分为三种情况：
            	 * 1、要删除的节点是叶子节点（无子节点的节点）
            	 * 2、有一个子节点的非叶子节点
            	 * 3、有两个子节点的非叶子节点
            	 */
            	//如果是叶子节点那么只需将父节点的引用断掉即可
            	if(current.left == null && current.right == null){
        
            		//这里在上层是将父节点赋值为返回值所以直接返回null
            		return null;
            	}
            	
            	//如果左边节点为空表示子节点是右边节点，就返回右节点
            	if(current.left == null){
        
            		return current.right;
            	}
            	//如果右边节点为空表示子节点是左边节点，就返回左节点
            	if(current.right == null){
        
            		return current.left;
            	}
            	
            	/*
            	 * 如果有两个节点，那么必须先找到删除后代替
            	 * 被删除节点位置的节点然后再执行删除，
            	 * 这里我是取右子树中大于被删除节点的最小的节点
            	 */
            	Integer smallestItem = findSmallestItem(current.right);
            	//用其右子树中大于被删除节点的最小节点代替
            	current.item = smallestItem;
            	//递归删除掉右子树
            	current.right = removeRecursive(current.right, smallestItem);
            	//然后返回当前节点
            	return current;
        	}
        	//如果需要删除的值小于当前节点的值那么就递归左边
        	if(item < current.item){
        
        		current.left = removeRecursive(current.left, item);
        		//然后返回当前节点即返回已经被删除节点的父节点
        		return current;
        	}
        	//如果果需要删除的值大于当前节点的值那么就递归右边
        	current.right = removeRecursive(current.right, item);
        	//然后返回当前节点即返回已经被删除节点的父节点
        	return current;
        }
        
        /**
         * 找到右子树中最小的大于根节点的节点
        * @param root	根节点
        * @return	找到的结果
         */
        private <E> E  findSmallestItem(BinarySearchTreeNode<E> root){
        
        	/*
        	 * 这里又需要递归，如果root.left == null说明找到了
        	 * 否则就继续递归寻找左子树知道找到为止
        	 */
        	return	root.left == null ? root.item : findSmallestItem(root.left);
        }
        
        
        
        
        /**
         * 一个私有的静态内部类作为二叉树的元素
         * 这里由于后面的算法题中需要使用到这个
         * 静态内部类，所以把其写成public的，并
         * 把其成员变量也写成public的
         * @author Peter
         */
        public static class BinarySearchTreeNode<E>{
        
            
            /*
             * 左边的子节点
             */
            public BinarySearchTreeNode<E>  left;
            
            /*
             * 右边的子节点
             */
            public BinarySearchTreeNode<E>  right;
            
            
            public  E item;
            
            public BinarySearchTreeNode(){
        
                
            }
            
            public BinarySearchTreeNode(E e){
        
                this.item=e;
            }
            
             @Override
             public String toString() {
        
                 if (item == null) {
        
                     return "null";
                 }
                 return item.toString();
             }
        }
    
    	public static void main(String[] args) {
        
    		
    	    
    	    
    
    	}
    	
    	
    
        public BinarySearchTreeNode<Integer> getRoot() {
        
            return root;
        }
    
    
    }

## 2、跳表结构的实现 ##

/**
     * 跳表结构的实现
     * 为了方便不做泛型了直接用Integer
     * 
     * 跳表结构的特点：
     * 1、有多个层的数据；
     * 2、有多少层是由一个随机算法决定的；
     * 3、最底层包含整个跳表的所有元素；
     * 4、是采用空间换时间的思想实现的。
     * @author Peter
     */
    public class SkipList {
        
        
        private  static final byte HEAD_NODE=(byte)-1;
        
        private  static final byte ELEMENT_NODE=(byte)0;
        
        private  static final byte TAIL_NODE=(byte)1;
        
        
        private Node head;
        
        private Node tail;
        
        private int size;
        
        private int height=1;
        
        private Random random;
        
        public SkipList() {
        
            this.head=new Node(null,HEAD_NODE);
            this.tail=new Node(null,TAIL_NODE);
            head.right=tail;
            tail.left=head;
            this.random=new Random();
        }
        
        
        
        public int size(){
        
            return this.size;
        }
        
        public boolean contains(Integer e){
        
            //首先先寻找
            Node foundNode = this.find(e);
            /*
             * 如果找到的和我们要判断是否存在的
             * 相等，那么说明集合中包含这个元素。
             */
            return foundNode.item.equals(e);
        }
        
        
        public void add(Integer e){
        
            //首先找到应该添加的临近的节点
            Node nearNode = this.find(e);
            //然后创建一个要添加的节点
            Node toAddNode=new Node(e);
            //将要添加的节点的左边设置为原有的附近的节点
            toAddNode.left=nearNode;
            //将要添加的节点的右边设置为原有的附近的节点的右边
            toAddNode.right=nearNode.right;
            //将原有的附近的节点的右边节点的左边设置为要添加的节点
            nearNode.right.left=toAddNode;
            //将原有的附近的节点的右边设置为要添加的节点
            nearNode.right=toAddNode;
            
            //决定该放在哪一层
            int currentLayer=1;
            //用随机数决定是否需要提高层次    1 、2 、3、4
            while(random.nextInt(4)+1>2){
        
                
                //如果超过原有的层高了
                if(currentLayer>=this.height){
        
                    height++;
                    Node dummyHead=new Node(null, HEAD_NODE);
                    Node dummyTail=new Node(null, TAIL_NODE);
                    
                    dummyHead.right=dummyTail;
                    dummyHead.down=head;
                    head.up=dummyHead;
                    
                    dummyTail.left=dummyHead;
                    dummyTail.down=tail;
                    tail.up=dummyTail;
                    
                    head=dummyHead;
                    tail=dummyTail;
                }
                
                //这里说明还需要往左挪位置
                while(nearNode!=null && nearNode.up==null){
        
                    nearNode=nearNode.left;
                }
                nearNode=nearNode.up;
                
                //创建一个要添加节点的上层节点
                Node upToAddNode=new Node(e);
                //设置上层节点的链表关系
                upToAddNode.left=nearNode;
                upToAddNode.right=nearNode.right;
                upToAddNode.down=toAddNode;
                
                //设置临近节点的关系
                nearNode.right.left=upToAddNode;
                nearNode.right=upToAddNode;
                
                //设置要添加节点的关系
                toAddNode.up=upToAddNode;
                //可能循环提高层高所以
                toAddNode=upToAddNode;
                
                currentLayer++;
                
            }
            size++;
            
        }
        
        public void flushSkipList(){
        
            Node tempNode=head;
            //从最高层一层一层往下刷新
            for(int i=height;i>0;i--){
        
                System.out.print("总共："+height+"层，当前层数："+i);
                Node toFlushNode=tempNode.right;
                while(toFlushNode.type==ELEMENT_NODE){
        
                    System.out.print("-->"+toFlushNode.item);
                    toFlushNode=toFlushNode.right;
                }
                //本层打印完就换行
                System.out.println();
                tempNode=tempNode.down;
            }
            System.out.println("--------------------打印完毕-----------------------");
        }
        
        
        private Node find(Integer e){
        
            Node current=head;
            while(true){
        
                /*
                 * 如果当前元素的右边节点不是末尾节点，
                 * 且要添加的元素比当前节点右边的节点大，
                 * 那么就进行交换，将当前节点变为
                 * 当前节点的右边节点
                 * 此过程为一直在同层中往右走寻找大于等于自己的元素，直到找到为止
                 */
                while(current.right.type!=TAIL_NODE  && e>=current.right.item){
        
                    current=current.right;
                }
                
                /*
                 * 如果是在最底层说明不用再找了
                 * 已经找到位置了直接跳出循环
                 */
                if(current.down==null){
        
                    break;
                }
                //如果不是最底层又继续往下层找
                current=current.down;
            }
            /*
             * 如果要寻找的元素存在于本集合中，那么
             * 这里可以确定要寻找的元素>=current
             * 且<=current.right
             */
            return current;
        }
        
        private  static class Node{
        
            
            private Integer item;
            
            private Node up,down,left,right;
            
            private byte type;
            
            public Node(Integer e){
        
                this(e,ELEMENT_NODE);
            }
            
            public Node(Integer e,byte type){
        
                this.item=e;
                this.type=type;
            }
            
        }
        
        
    
    	public static void main(String[] args) {
        
    		
    	    SkipList mySkipList=new SkipList();
            mySkipList.add(10);
            mySkipList.flushSkipList();
    //      mySkipList.add(5);
    //      mySkipList.flushSkipList();
            //添加100个小于1000的随机数
            Random random=new Random();
            for(int i=0;i<100;i++){
        
                mySkipList.add(random.nextInt(1000));
            }
            mySkipList.flushSkipList();
    	}
    }

## 3、中序遍历递归写法 ##

/**
     * 
     * 
     * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
     * 中序遍历递归写法
     */
    public class LeeCodeTest01 {
        
    	
    	private List<Integer> treeNodeList = new ArrayList<>();
    	
    	/**
    	 * 递归写法
    	 * @param root
    	 * @return
    	 */
        public List<Integer> inorderTraversal1(TreeNode root) {
        
    
            
            if(root == null){
        
                return treeNodeList;
            }
            
            //递归左边
            inorderTraversal1(root.left);
            treeNodeList.add(root.val);
            //递归右边
            inorderTraversal1(root.right);
    
            return treeNodeList;
        }
        
        
        private static class TreeNode{
        
        	
        	private TreeNode left;
        	
        	private TreeNode right;
        	
        	private int val;
        	
        }
    
    	public static void main(String[] args) {
        
    		
    	}
    
    }

## 4、中序遍历递归写法 ##

/**
     * 
     * https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
     * 前序遍历递归写法
     */
    public class LeeCodeTest02 {
        
    	
    	private List<Integer> treeNodeList = new ArrayList<>();
        
    	/**
    	 * 递归的方式
    	 * @param root
    	 * @return
    	 */
        public List<Integer> preorderTraversal1(TreeNode root) {
        
    
            
            if(root == null){
        
                return treeNodeList;
            }
            
            treeNodeList.add(root.val);
            //递归左边
            preorderTraversal1(root.left);
            //递归右边
            preorderTraversal1(root.right);
    
            return treeNodeList;
        }
        
        
        
        private static class TreeNode{
        
        	
        	private TreeNode left;
        	
        	private TreeNode right;
        	
        	private int val;
        	
        }
    
    	public static void main(String[] args) {
        
    
    	}
    
    }

## 5、树的各种遍历方式： ##

/**
     * 树的各种遍历方式：
     * 前序遍历：根 --> 左子树 --> 右子树
     * 中序遍历：左子树 --> 根 --> 右子树
     * 后序遍历：左子树 --> 右子树 --> 根
     * https://www.cnblogs.com/zhi-leaf/p/10813048.html
     */
    public class TreeErgodicTest {
        
    
    	public static void main(String[] args) {
        
    		//准备数据
    	    BinarySearchTree binarySearchTree = new BinarySearchTree();
            binarySearchTree.add(39);
            binarySearchTree.add(20);
            binarySearchTree.add(69);
            
            binarySearchTree.add(11);
            binarySearchTree.add(27);
            binarySearchTree.add(23);
            
            binarySearchTree.add(50);
            binarySearchTree.add(87);
    //        binarySearchTree.remove(69);
            
            
    //      System.out.println(binarySearchTree.contains(23));
            
            BinarySearchTreeNode<Integer> root = binarySearchTree.getRoot();
            System.out.println("根节点是："+root);
            
    //        prePrint1(root);
    //        prePrint2(root);
            
    //        middlePrint1(root);
    //        middlePrint2(root);
            
            postPrint1(root);
            postPrint2(root);
            
            
            levelPrint(root);
            
    
    	}
    	
    	
    	/**
    	 * O(2^n)
    	 * O(n)
         * 前序遍历打印二叉搜索树（递归的方式）
         * 根 --> 左子树 --> 右子树
         * @param root 二叉树的根节点
         */
        private static <E> void prePrint1(BinarySearchTreeNode<E> root){
        
            
            if(root == null){
        
                return;
            }
            
            System.out.print(root.item+"-->");
            //递归左边
            prePrint1(root.left);
            //递归右边
            prePrint1(root.right);
            
        }
        
        
        /**
         * 非递归的方式（使用栈的方式）
         * 1、弹栈并进行打印
         * 2、如果有右子节点，就将右子节点进行压栈
         * 3、如果有左子节点，就将左子节点进行压栈
         * 即：先根再右再左
         * 压完栈后执行弹栈操作，弹出时就进行打印
         * 然后重复2和3步骤
         * 
         * 时间复杂度为：O(n)
         * 空间复杂度为：O(?)
         * 前序遍历打印二叉搜索树
         * 根 --> 左子树 --> 右子树
         * @param root 二叉树的根节点
         */
        private static <E> void prePrint2(BinarySearchTreeNode<E> root){
        
            
            System.out.println();
            if(root == null){
        
                return;
            }
            //准备一个栈
            Stack<BinarySearchTreeNode<E>> stack = new Stack<>();
            //首先将根节点进行压栈
            stack.push(root);
            //如果栈不为空就一直执行
            while(!stack.isEmpty()){
        
                //进行弹栈，并替换掉根节点的值，弹出时就进行打印
                root = stack.pop();
                System.out.print(root.item+"-->");//invoke method
                //如果有右子节点，就将右子节点进行压栈
                if(root.right != null){
        
                    stack.push(root.right);
                }
                //如果有左子节点，就将左子节点进行压栈
                if(root.left != null){
        
                    stack.push(root.left);
                }
            }
            
        }
        
        
        /**
         * 中序遍历打印二叉搜索树（中序遍历是有序的）
         * 左子树 --> 根 --> 右子树
         * @param root 二叉树的根节点
         */
        private static <E> void middlePrint1(BinarySearchTreeNode<E> root){
        
            
            if(root == null){
        
                return;
            }
            
            //递归左边
            middlePrint1(root.left);
            System.out.print(root.item+"-->");
            //递归右边
            middlePrint1(root.right);
            
        }
        
        
        /**
         * 中序遍历打印二叉搜索树（中序遍历是有序的）
         * 左子树 --> 根 --> 右子树
         * 
         * 1、将树的左边界的元素全部依次压入栈中
         * 2、弹栈并进行打印，然后去弹栈元素的右子树
         * 将其右子树的左边界全部依次压入栈中，重复此过程
         * 时间复杂度：O(n)
         * 空间复杂度：O(n)
         * @param root 二叉树的根节点
         */
        private static <E> void middlePrint2(BinarySearchTreeNode<E> root){
        
            
            System.out.println();
            if(root == null){
        
                return;
            }
            //准备一个栈
            Stack<BinarySearchTreeNode<E>> stack = new Stack<>();
            
            while(!stack.isEmpty() || root != null){
        
                //如果根节点不为空
                if(root != null){
        
                    //将根节点压入栈中
                    stack.push(root);
                    //根节点变为根节点的左子节点
                    root = root.left;
                    continue;
                }
              //如果根节点为空
              //根节点变为弹栈的元素
              root = stack.pop();
              //打印当前根节点
              System.out.print(root.item+"-->");
              //根节点变为根节点的右子节点
              root = root.right;
            }
        }
        
        
        /**
         * 后序遍历打印二叉搜索树
         * 左子树 --> 右子树 --> 根
         * @param root 二叉树的根节点
         */
        private static <E> void postPrint1(BinarySearchTreeNode<E> root){
        
            
            if(root == null){
        
                return;
            }
            
            //递归左边
            postPrint1(root.left);
            //递归右边
            postPrint1(root.right);
            System.out.print(root.item+"-->");
            
        }
        
        
        /**
         * 后序遍历打印二叉搜索树
         * 左子树 --> 右子树 --> 根
         * 
         *  非递归的方式（使用两个栈的方式）
         * 1、弹栈，然后将弹出元素压入另一个栈
         * 2、如果有左子节点，就将左子节点进行压栈
         * 3、如果有右子节点，就将右子节点进行压栈
         * 即：先根再左再右
         * 压完栈后执行弹栈操作，弹出后
         * 将弹出元素压入另一个栈
         * 然后重复2和3步骤
         * @param root 二叉树的根节点
         */
        private static <E> void postPrint2(BinarySearchTreeNode<E> root){
        
            
            System.out.println();
            
            if(root == null){
        
                return;
            }
            //准备两个栈
            Stack<BinarySearchTreeNode<E>> stack1 = new Stack<>();
            Stack<BinarySearchTreeNode<E>> stack2 = new Stack<>();
            //首先将根节点进行压栈
            stack1.push(root);
            //如果栈不为空就一直执行
            while(!stack1.isEmpty()){
        
                //进行弹栈，并替换掉根节点的值，弹出时不打印
                root = stack1.pop();
                //将弹栈的元素压入另一个栈
                stack2.push(root);
                //如果有左子节点，就将左子节点进行压栈
                if(root.left != null){
        
                    stack1.push(root.left);
                }
                //如果有右子节点，就将右子节点进行压栈
                if(root.right != null){
        
                    stack1.push(root.right);
                }
            }
            //等第一个栈的元素都弹栈完了，将第二个栈元素进行弹栈并打印
            while(!stack2.isEmpty()){
        
                System.out.print(stack2.pop().item+"-->");
            }
            
        }
        
        
        /**
         * 层次遍历打印二叉搜索树
         * 根节点那一层为第一层，第二层，第三层
         * 
         *  需要使用队列
         * 1、首先把根节点放入队列
         * 2、获取到队首元素并打印
         * 3、将其左子节点入队，将其右子节点入队
         * 4、重复2和3过程
         * @param root 二叉树的根节点
         */
        private static <E> void levelPrint(BinarySearchTreeNode<E> root){
        
            
            System.out.println();
            
            if(root == null){
        
                return;
            }
            //准备一个队列
            Queue<BinarySearchTreeNode<E>> queue = new LinkedList<>();
            //首先把根节点放入队列
            queue.offer(root);
            //如果队列不为空就一直执行
            while(!queue.isEmpty()){
        
                //获取到队首元素
                BinarySearchTreeNode<E> current = queue.poll();
                //出队后就打印
                System.out.print(current.item+"-->");
                //将其左子节点入队
                if(current.left != null){
        
                    queue.offer(current.left);
                }
                //将其右子节点入队
                if(current.right != null){
        
                    queue.offer(current.right);
                }
                //重复此过程直到没有子节点为止
            }
            
        }
    
    }

[-_B_Tree]: https://blog.csdn.net/weixin_43333483/article/details/125629149?spm=1001.2014.3001.5502