算法(2)——二叉树

 二叉树

二叉树 -  二叉链表存储

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表为二叉链表。

 

二叉数的性质

1，在二叉树的第i层上最多有 2i-1个结点（i>=1）

2，深度为k的二叉树至多有2k-1个结点

  20+21+22+23+24+25+26+27+.....+2k-1+-1

  =1+20+21+22+23+24+25+26+27+.....+2k-1-1

  =21+21+22+23+24+25+26+27+.....+2k-1-1

  =22+22+23+24+25+26+27+.....+2k-1-1

  =23+23+24+25+26+27+.....+2k-1-1

  =2k-1+2k-1-1

  =2k-1

3,对于一个完全二叉树，假设它有n个结点，对结点进行从1开始编号，对任一结点i满足下面

  a，它的双亲是结点 i/2  (除了i=1的情况)

  b，左孩子是 2i  右孩子是 2i+1

  c，如果2i>n 说明无左孩子   2i+1>n 说明无右孩子

    class Program
    {
        static void Main(string[] args)
        {
            char[] data = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };//这个是我们要存储的数据
            BiTree<char> tree = new BiTree<char>(10);
            for (int i = 0; i < data.Length; i++)
            {
                tree.Add(data[i]);
            }
            //前序遍历
            tree.FirstTraversal();
            Console.WriteLine();
            //中序遍历
            tree.MiddleTraversal();
            Console.WriteLine();
            //后序遍历
            tree.LastTraversal();
            Console.WriteLine();
            //层遍历
            tree.LayerTraversal();
            Console.ReadKey();
        }
    }

前序遍历，中序遍历，后序遍历三种遍历方式

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

1，前序遍历

    先输出当前结点的数据，再依次遍历输出左结点和右结点

       A    (B)     (C)

                B (D)     C (E) F

                  D G H     E I

           A B D G H C E I

2，中序遍历

先遍历输出左结点，再输出当前结点的数据，再遍历输出右结点

    GＤH B A E I C F

3，后序遍历

    先遍历输出左结点，再遍历输出右结点，最后输出当前结点的数据

 G H D B I E F C A

4、层序遍历

从树的第一层开始，从上到下逐层遍历，在同一层中，从左到右对结点 逐个访问输出

//如果一个结点是空的话，那么这个结点所在的数组位置，设置为-1，
    class BiTree<T>
    {

        private T[] data;
        private int count = 0;
        public BiTree(int capacity)// 这个参数是当前二叉树的容量，容量就是最多可以存储的数据个数， 数量count代表当前保存了多少个数据
        {
            data = new T[capacity];
        }
        public bool Add(T item)
        {
            if (count >= data.Length)
                return false;
            data[count] = item;
            count++;
            return true;
        }

        public void FirstTraversal()
        {
            FirstTraversal(0);
        }

        //前序遍历
        /// <summary>
        /// 前序遍历：先输出当前结点的数据，再依次遍历输出左结点和右结点
        /// </summary>
        /// <param name="index"></param>
        private void FirstTraversal(int index)
        {
            if (index >= count) return;
            //得到要遍历的这个结点的编号 
            int number = index + 1;
            if (data[index].Equals(-1)) return;
            Console.Write(data[index] + " ");
            //得到左子结点的编号
            int leftNumber = number * 2;
            //右子节点的编号
            int rightNumber = number * 2 + 1;
            //递归
            FirstTraversal(leftNumber - 1);
            FirstTraversal(rightNumber - 1);
        }

        public void MiddleTraversal()
        {
            MiddleTraversal(0);
        }

        /// <summary>
        /// //中序遍历，先遍历输出左结点，再输出当前结点的数据，再遍历输出右结点
        /// </summary>
        /// <param name="index"></param>
        private void MiddleTraversal(int index)
        {
            if (index >= count) return;
            //得到要遍历的这个结点的编号 
            int number = index + 1;
            if (data[index].Equals(-1)) return;
            //得到左子结点的编号
            int leftNumber = number * 2;
            int rightNumber = number * 2 + 1;
            MiddleTraversal(leftNumber - 1);
            Console.Write(data[index] + " ");
            MiddleTraversal(rightNumber - 1);
        }

        public void LastTraversal()
        {
            LastTraversal(0);
        }

        /// <summary>
        /// 后续遍历：先遍历输出左结点，再遍历输出右结点，最后输出当前结点的数据
        /// </summary>
        /// <param name="index"></param>
        private void LastTraversal(int index)
        {
            if (index >= count) return;
            //得到要遍历的这个结点的编号 
            int number = index + 1;
            if (data[index].Equals(-1)) return;
            //得到左子结点的编号
            int leftNumber = number * 2;
            int rightNumber = number * 2 + 1;
            LastTraversal(leftNumber - 1);
            LastTraversal(rightNumber - 1);
            Console.Write(data[index] + " ");
        }

        public void LayerTraversal()
        {
            for (int i = 0; i < count; i++)
            {
                //当前的节点没有数据
                if (data[i].Equals(-1)) continue;
                Console.Write(data[i] + " ");
            }
            Console.WriteLine();
        }
    }

二叉排序树

二叉排序树，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

  若它的左子树不为空，则左子树上所有的结点的值均小于根结构的值；

  若它的右子树不为空，则右字数上所有结点的值均大于它的根结点的值；

  它的左右子树也分别为二叉排序树。

1，排序方便

2，方便查找

3，方便插入和删除

二叉排序树 删除操作

二叉排序树删除

1，叶子结点

2，仅有左子树或者右子数的结点

3，左右子树都有

二叉排序树的存储

因为二叉排序树的存储，跟自身值的大小有关系，并不是想之前学习的完全二叉树使用顺序结构可以存储的，

所以我们使用链式结构存储二叉排序树。

二叉排序树的代码实现

一个是树类的定义 BSTree

一个是结点类的定义BSNode

节点

    class BSNode
    {
        public BSNode LeftChild { get; set; }
        public BSNode RightChild { get; set; }
        public BSNode Parent { get; set; }
        public int Data { get; set; }
        public BSNode()
        {
        }
        public BSNode(int item)
        {
            this.Data = item;
        }
    }

执行程序

    class Program
    {
        static void Main(string[] args)
        {
            BSTree tree = new BSTree();
            int[] data = { 62, 58, 88, 47, 73, 99, 35, 51, 93, 37 };
            foreach (int t in data)
            {
                tree.Add(t);
            }
            tree.MiddleTraversal();
            Console.WriteLine();
            Console.WriteLine(tree.Find(99));
            Console.WriteLine(tree.Find(100));
            tree.Delete(35);
            tree.MiddleTraversal(); Console.WriteLine();
            tree.Delete(62);
            tree.MiddleTraversal(); Console.WriteLine();
            Console.ReadKey();
        }
    }

树

    class BSTree
    {
        BSNode root = null;

        //添加数据
        public void Add(int item)
        {
            BSNode newNode = new BSNode(item);
            if (root == null)
            {
                root = newNode;
            }
            else
            {
                BSNode temp = root;
                while (true)
                {
                    //比根节点大
                    if (item >= temp.Data)//放在temp的右边
                    {
                        if (temp.RightChild == null)
                        {
                            //右节点为空，直接放右边
                            //孩子和父亲互认一下
                            temp.RightChild = newNode;
                            newNode.Parent = temp;
                            break;
                        }
                        else
                        {
                            temp = temp.RightChild;
                        }
                    }
                    else//放在temp的左边
                    {
                        if (temp.LeftChild == null)
                        {
                            //左节点为空，放左节点，父子相认
                            temp.LeftChild = newNode;
                            newNode.Parent = temp;
                            break;
                        }
                        else
                        {
                            temp = temp.LeftChild;
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        public void MiddleTraversal()
        {
            MiddleTraversal(root);
        }
        //中序遍历从哪个节点开始
        private void MiddleTraversal(BSNode node)
        {
            if (node == null) return;

            MiddleTraversal(node.LeftChild);
            Console.Write(node.Data + " ");
            MiddleTraversal(node.RightChild);
        }

        /// <summary>
        /// 查找根节点，外部调用
        /// </summary>
        /// <param name="item"></param>
        /// <returns></returns>
        public bool Find(int item)
        {
            BSNode temp = root;
            while (true)
            {
                if (temp == null) return false;
                if (temp.Data == item) return true;
                if (item > temp.Data)
                    //向右子树查找
                    temp = temp.RightChild;
                else
                    //向左册数查找
                    temp = temp.LeftChild;
            }
        }

        private bool Find(int item, BSNode node)
        {
            if (node == null) return false;
            if (node.Data == item)
            {
                return true;
            }
            else
            {
                if (item > node.Data)
                {
                    return Find(item, node.RightChild);
                }
                else
                {
                    return Find(item, node.LeftChild);
                }
            }
        }

        /// <summary>
        /// //删除节点值
        /// </summary>
        /// <param name="item"></param>
        /// <returns></returns>
        public bool Delete(int item)
        {
            BSNode temp = root;
            while (true)
            {
                if (temp == null) return false;
                if (temp.Data == item)
                {
                    Delete(temp);
                    return true;
                }
                if (item > temp.Data)
                    temp = temp.RightChild;
                else
                    temp = temp.LeftChild;
            }
        }
        public void Delete(BSNode node)
        {
            if (node.LeftChild == null && node.RightChild == null)
            {
                //左右节点都为空
                if (node.Parent == null)
                {
                    root = null;
                }
                else if (node.Parent.LeftChild == node)
                {
                    node.Parent.LeftChild = null;
                }
                else if (node.Parent.RightChild == node)
                {
                    node.Parent.RightChild = null;
                }
                return;
            }
            if (node.LeftChild == null && node.RightChild != null)
            {
                //左节点为空
                node.Data = node.RightChild.Data;
                node.RightChild = null;
                return;
            }
            if (node.LeftChild != null && node.RightChild == null)
            {
                //右节点为空
                node.Data = node.LeftChild.Data;
                node.LeftChild = null;
                return;
            }

            //左右节点都存在，找右节点的最左侧的值
            BSNode temp = node.RightChild;
            while (true)
            {
                if (temp.LeftChild != null)
                {
                    temp = temp.LeftChild;
                }
                else
                {
                    break;
                }
            }
            node.Data = temp.Data;
            Delete(temp);
        }
    }

堆

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆!

堆排序

堆排序算法就是利用堆（小顶堆或者大顶堆）进行排序的方法。

  将待排序的序列构造成一个大顶堆，此时整个序列的最大值就是根节点。将它移走（跟堆的最后一个元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

 

 

 

 

本文地址：https://blog.csdn.net/qq_35647121/article/details/110939205