数据结构 - 顺序存储二叉树(前序中序后序遍历)

梦里梦外; 2023-07-03 04:52 45阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70]

# 就是逻辑上是二叉树，物理上是一个数组 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 1]

# 需求 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 2]

package tree;
    
    public class ArrayBinaryTreeDemo { 
        public static void main(String[] args) { 
            int arr [] = { 1, 2, 3, 4, 5, 6, 7};
            ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
            //arrayBinaryTree.preOrder();
            //arrayBinaryTree.infixOrder();
            arrayBinaryTree.postOrder();
        }
    }
    //编写一个ArrayBinaryTree，实现顺序存储二叉树
    class ArrayBinaryTree{ 
        private int [] arr; //存储数据节点的数组
    
        public ArrayBinaryTree(int[] arr) { 
            this.arr = arr;
        }
    
        //重载preOrder()
        public void preOrder(){ 
            this.preOrder(0);
        }
    
        //重载infixOrder()
        public void infixOrder(){ 
            this.infixOrder(0);
        }
    
        //重载postOrder()
        public void postOrder(){ 
            this.postOrder(0);
        }
        //编写一个方法，完成顺序存储二叉树前序遍历
        /** * * @param index 数组下标 */
        public void preOrder(int index){ 
            //如果数组为空，或者arr.length = 0；
            if (arr == null || arr.length == 0){ 
                System.out.println("数组为空，不能遍历");
                return;
            }
            //输出当前元素
            System.out.println(arr[index]);
            //向左递归遍历
            if ( (index * 2 + 1) < arr.length){ 
                preOrder(2 * index + 1);
            }
            if ((index * 2 + 2) < arr.length){ 
                preOrder(index * 2 + 2);
            }
        }
    
        //中序遍历
        public void infixOrder(int index){ 
            if (arr == null || arr.length == 0){ 
                System.out.println("数组为空，不能遍历");
                return;
            }
            if ((index * 2 + 1) < arr.length){ 
                infixOrder(index * 2 + 1);
            }
            System.out.println(arr[index]);
            if ((index * 2 + 2)<arr.length){ 
                infixOrder(index * 2 + 2);
            }
        }
    
        //后序遍历
        public void postOrder(int index){ 
            if (arr == null || arr.length == 0){ 
                System.out.println("数组为空，不能遍历");
                return;
            }
            if ((index * 2 + 1) < arr.length){ 
                infixOrder(index * 2 + 1);
            }
            if ((index * 2 + 2)<arr.length){ 
                infixOrder(index * 2 + 2);
            }
            System.out.println(arr[index]);
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200202153750135.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200202153902847.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200202154231277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70