欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

算法(2)——二叉树

程序员文章站 2022-03-22 15:36:35
二叉树二叉数的性质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+.......

 二叉树

算法(2)——二叉树

二叉树 二叉链表存储

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

算法(2)——二叉树

算法(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,前序遍历

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

算法(2)——二叉树

       A    (B)     (C)

                B (D)     C (E) F

                  D G H     E I

           A B D G H C E I

2,中序遍历

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

    GH B A E I C F

算法(2)——二叉树

3,后序遍历

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

 G H D B I E F C A

算法(2)——二叉树

4、层序遍历

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

算法(2)——二叉树

//如果一个结点是空的话,那么这个结点所在的数组位置,设置为-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();
        }
    }

二叉排序树

算法(2)——二叉树

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

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

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

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

1,排序方便

2,方便查找

3,方便插入和删除

二叉排序树 删除操作

二叉排序树删除

1,叶子结点

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

3,左右子树都有

算法(2)——二叉树算法(2)——二叉树算法(2)——二叉树

二叉排序树的存储

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

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

二叉排序树的代码实现

一个是树类的定义 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);
        }
    }

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

算法(2)——二叉树

堆排序

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

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

算法(2)——二叉树算法(2)——二叉树

 

 

 

 

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

相关标签: 算法