数据结构--树(Java版)

绝地灬酷狼 2022-05-26 12:25 180阅读 0赞

### 一、树节点的表示 ###

/** * 树的节点 * @author hoaven * */
    public class TreeNode<T> { 
        T data;
        TreeNode<T> left;
        TreeNode<T> right;
    
        public TreeNode(T data){
            this.data = data;
        }
    
    }

### 二、树的前中后序遍历 ###

#### 1、实现 ####

/** * 实现树的前序,中序,后续遍历搜索 * * @author hoaven * @see TreeNode */
    public class TreeSearch<T> { 
        StringBuffer searchPath = new StringBuffer();
        private boolean isSearched = false;
    
        /** * 前序遍历root查询item * * @return */
        public void preorderTraversal(TreeNode<T> root, T data) {
            if (root == null) {
                return;
            }
    
            if (!isSearched) {
                //记录遍历路径
                if (!searchPath.toString().equals("")) {
                    searchPath.append("->");
                }
                searchPath.append(root.data);
    
                //先判断根
                if (root.data.equals(data))
                    isSearched = true;
            }
    
            if (!isSearched)
                preorderTraversal(root.left, data);
            if (!isSearched)
                preorderTraversal(root.right, data);
        }
    
        /** * 中序遍历root查询item * * @param root * @return */
        public void inorderTraversal(TreeNode<T> root, T data) {
            if (root == null) {
                return;
            }
    
            if (!isSearched)
                inorderTraversal(root.left, data);
    
            if (!isSearched) {
                if (!searchPath.toString().equals("")) {
                    searchPath.append("->");
                }
                searchPath.append(root.data);
    
                if (root.data.equals(data))
                    isSearched = true;
            }
    
            if (!isSearched)
                inorderTraversal(root.right, data);
        }
    
        /** * 后续遍历root查询item * * @return */
        public void postorderTraversal(TreeNode<T> root, T data) {
            if (root == null) {
                return;
            }
    
            if (!isSearched)
                postorderTraversal(root.left, data);
    
            if (!isSearched)
                postorderTraversal(root.right, data);
    
            if (!isSearched) {
                if (!searchPath.toString().equals("")) {
                    searchPath.append("->");
                }
                searchPath.append(root.data);
                if (root.data.equals(data))
                    isSearched = true;
            }
        }
    }

#### 2、测试 ####

/** * TreeSearch测试类 * @author hoaven * @see TreeSearch * @see TreeNode */
    public class TreeSearchTest { 
    
        private static TreeNode<Integer> root;
    
        @BeforeClass
        public static void beforeClass(){
            TreeNode<Integer> node1 = new TreeNode<Integer>(1);
            TreeNode<Integer> node2 = new TreeNode<Integer>(2);
            TreeNode<Integer> node3 = new TreeNode<Integer>(3);
            TreeNode<Integer> node4 = new TreeNode<Integer>(4);
            TreeNode<Integer> node5 = new TreeNode<Integer>(5);
            TreeNode<Integer> node6 = new TreeNode<Integer>(6);
            TreeNode<Integer> node7 = new TreeNode<Integer>(7);
            TreeNode<Integer> node8 = new TreeNode<Integer>(8);
            TreeNode<Integer> node9 = new TreeNode<Integer>(9);
            TreeNode<Integer> node10 = new TreeNode<Integer>(10);
    
            node1.left = node2;
            node1.right = node3;
    
            node2.left = node4;
            node2.right = node5;
    
            node3.left = node6;
            node3.right = node7;
    
            node4.left = node8;
    
            node7.right = node9;
    
            node9.left = node10;
    
            root = node1;
        }
    
        /** * 前序遍历测试 */
        @Test
        public void preorderTraversalTest(){
            TreeSearch<Integer> treeSearch = new TreeSearch<Integer>();
    
            Integer value = 5;
            String expectedSearchPath = "1->2->4->8->5";
            treeSearch.preorderTraversal(root, value);
            Assert.assertTrue(expectedSearchPath.equals(treeSearch.searchPath.toString()));
    
            treeSearch = new TreeSearch<Integer>();
    
            value = 6;
            expectedSearchPath = "1->2->4->8->5->3->6";
            treeSearch.preorderTraversal(root, value);
            Assert.assertTrue(expectedSearchPath.equals(treeSearch.searchPath.toString()));
        }
    
        /** * 中序遍历测试 */
        @Test
        public void inorderTraversalTest(){
            TreeSearch<Integer> treeSearch = new TreeSearch<Integer>();
    
            Integer value = 5;
            String expectedSearchPath = "8->4->2->5";
            treeSearch.inorderTraversal(root, value);
            Assert.assertTrue(expectedSearchPath.equals(treeSearch.searchPath.toString()));
    
            treeSearch = new TreeSearch<Integer>();
    
            value = 6;
            expectedSearchPath = "8->4->2->5->1->6";
            treeSearch.inorderTraversal(root, value);
            Assert.assertTrue(expectedSearchPath.equals(treeSearch.searchPath.toString()));
        }
    
        /** * 后序遍历测试 */
        @Test
        public void postorderTraversalTest(){
            TreeSearch<Integer> treeSearch = new TreeSearch<Integer>();
    
            Integer value = 5;
            String expectedSearchPath = "8->4->5";
            treeSearch.postorderTraversal(root, value);
            Assert.assertTrue(expectedSearchPath.equals(treeSearch.searchPath.toString()));
    
            treeSearch = new TreeSearch<Integer>();
    
            value = 6;
            expectedSearchPath = "8->4->5->2->6";
            treeSearch.postorderTraversal(root, value);
            Assert.assertTrue(expectedSearchPath.equals(treeSearch.searchPath.toString()));
        }
    }

### 2、二叉查找树判断 ###

>  *  二叉树：每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。
>  *  二叉查找树：对所有节点来说，所有左子树节点都小于等于其根节点；所有右子树节点都大于其根节点。

/** * 二叉查找树的判断<br> * @author hoaven * @see TreeNode */
    public class BinarySearchTree { 
    
        /** * Check root左子树所有节点小于等于max,root右子树所有节点大于min * * @param root * @param min * @param max * @return */
        private static boolean checkBSTMinMax(TreeNode<Integer> root, Integer min, Integer max){
            if(root  == null){
                return true;
            }
    
            if(root.data > max || root.data <= min){
                return false;
            }
    
            if(!checkBSTMinMax(root.left, min, root.data) || !checkBSTMinMax(root.right, root.data, max)){
                return false;
            }
    
            return true;
        }
    
        /** * Check root是否二叉查找树 * @param root * @return */
        public static boolean checkBST(TreeNode<Integer> root){
            return checkBSTMinMax(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
    }