树（4）

JusterZhu

发布于 2022-12-07 20:18:40

1720

发布于 2022-12-07 20:18:40

文章被收录于专栏：JusterZhuJusterZhu

顺序存储二叉树

从数据存储来看，数组存储发昂是和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。

问题

（1）上图的二叉树的节点，要求以数组的方式来存放。array【1，2，3，4，5，6，7】

（2）在遍历数组array时，仍然可以以前、中、后序遍历方式完成节点的遍历。可称为顺序存储二叉树。

概念

顺序存储二叉树的特点如下：

（1）顺序二叉树通常只考虑完全二叉树

（2）第n个元素的左子节点为2*n+1

（3）第n个元素的右子节点为2*n+2

（4）第n个元素的父节点为（n-1）/2

n表示二叉树中的第几个元素（从0开始编号，如图）

代码

    internal class ArrayBinaryTree
    {
        private int[] array;

        public ArrayBinaryTree(int[] array)
        {
           this.array = array;
        }

        public void PreOrder()
        {
            //如果数组为空，或者array.length = 0
            if (array == null || array.Length == 0)
            {
                Console.WriteLine("数组为空，不能按照二叉树的前序遍历");
            }
            //输出当前这个元素
            Console.WriteLine(array[0]);
            //向左递归遍历
            if (2 * 0 + 1 < array.Length)
            {
                PreOrder(2 * 0 + 1);
            }
            //向右递归遍历
            if (2 * 0 + 2 < array.Length)
            {
                PreOrder(2 * 0 + 2);
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index">数组下标</param>
        public void PreOrder(int index)
        {
            //如果数组为空，或者array.length = 0
            if (array == null || array.Length == 0)
            {
                Console.WriteLine("数组为空，不能按照二叉树的前序遍历");
            }
            //输出当前这个元素
            Console.WriteLine(array[index]);
            //向左递归遍历
            if (2 * index + 1 < array.Length)
            {
                PreOrder(2 * index + 1);
            }
            //向右递归遍历
            if (2 * index + 2 < array.Length)
            {
                PreOrder(2 * index + 2);
            }
        }
    }

调用

        static void Main(string[] args)
        {
            int[] array = { 1, 2, 3, 4, 5, 6, 7 };
            ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
            arrayBinaryTree.PreOrder();
            Console.Read();
        }