算法（C#版）树

女爷i 2022-02-26 14:56 169阅读 0赞

**树（数据结构的一种 ）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70][]

**树**

什么是树的层次？

最大层是树的深度

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 1][]

什么是有序树和无序树？

**树的错误案例**

1，树只有一个根节点

2，子树之间是不相交的

3，一个结点不能有两个父结点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 2][]

**树的存储结构**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 3][]

我们使用链式存储来表示树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 6][]

**二叉树性质**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 7][]

**二叉树存储结构**

一般的树来说是一对多的关系，使用顺序结构存储起来比较困难，但是二叉树是一种特殊的树，每个结点最多有两个子节点，并且子节点有左右之分，并且兄弟，父亲，孩子可以很方便的通过编号得到，所以我们**使用顺序存储结构使用二叉树的存储。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 9][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 10][]

**二叉树** **- ** **二叉链表存储**

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 11][]

**二叉树的遍历**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 12][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 13][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 14][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 15][]

![20190330141053873.png][]

代码实现

建立一个二叉树类

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 二叉树_顺序结构存储
    {
        //如果一个结点是空的话，那么这个结点所在的数组位置，设置为-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);
            }
            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);
            }
            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);
            }
            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();
            }
        }
    }

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 二叉树_顺序结构存储
    {
        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();
            }
        }
    }

![20190330151008945.png][]

**二叉排序树**

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

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

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

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

1，排序方便

2，方便查找

3，方便插入和删除

4，通过中序遍历就能进行排序

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 16][]

**二叉排序树 删除操作**

![20190330151118209.png][]

![2019033015112889.png][]

![20190330151133114.png][]这种情况是添加左子树最大的结点或者右子树最小的结点到47

**二叉排序树的代码实现**

一个是结点类的定义BSNode

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 二叉排序树_链式存储
    {
        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;
            }
        }
    }

一个是树类的定义 BSTree

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 二叉排序树_链式存储
    {
        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;
                            }
                        }
                    }
                }
            }
    
            //排序，其实就是中序遍历
            public void MiddleTraversal()
            {
                MiddleTraversal(root);
            }
    
            private void MiddleTraversal(BSNode node)
            {
                if (node == null) return;
                MiddleTraversal(node.LeftChild);
                Console.Write(node.Data + " ");
                MiddleTraversal(node.RightChild);
            }
    
            //查找
            public bool Find(int item)
            {
                //return Find(item, root);
                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 (Find(item, node.LeftChild))
                    //    return true;
                    //if (Find(item, node.RightChild))
                    //    return true;
                    if (item > node.Data)
                        return Find(item, node.RightChild);
                    else
                        return Find(item, node.LeftChild);
                }
            }
    
            public bool Delete(int item)
            {
                BSNode temp = root;
                while (true)
                {
                    if (temp == null) return false;
                    if (temp.Data == item) Delete(temp);
                    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;
                    }
                    if(node.Parent.LeftChild == node)
                        node.Parent.LeftChild = null;
                    else if (node.Parent.RightChild == node)
                        node.Parent.RightChild = null;
                }
    
                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;
                }
    
                if (node.LeftChild != null && node.RightChild != null)
                {
                    //找右子树中值最小的结点
                    BSNode temp = node.RightChild;
                    while(true)
                    {
                        if(temp.LeftChild != null)
                        {
                            temp = temp.LeftChild;
                        }
                        else
                        {
                            break;
                        }
                    }
                    node.Data = temp.Data;
                    Delete(temp);
                }
            }
        }
    }

代码验证

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 二叉排序树_链式存储
    {
        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(91));
                Console.WriteLine(tree.Find(99));
                tree.Delete(51);
                tree.MiddleTraversal();
                Console.ReadKey();
            }
        }
    }

![20190330181750314.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70]: /images/20220226/69a8bead464b466795240e28212fd3e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 1]: /images/20220226/08a5c600d9a6448d90bef28bed8a0cb3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 2]: /images/20220226/a598346765e848bd8c387b3fa8ba7c54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 3]: /images/20220226/101e087a02ae4ef19efd6544da5e358c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 4]: /images/20220226/343a66adc82f49059dabd21a201ea6e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 5]: /images/20220226/ac18297b3fcd45d38accd623bc332585.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 6]: /images/20220226/3af9953f8f474ec4ad7b9a78c120b271.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 7]: /images/20220226/8bc149e0b36e44adb65a738f4f5b2b61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 8]: /images/20220226/ff3f3a5d2ed74d5ab681cf0f793635f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 9]: /images/20220226/b4afde0420cf48c09c975e72802e0731.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 10]: /images/20220226/f386edc8c369402aad2f1f576f14f81a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 11]: /images/20220226/355cd57a78334793aca660b9ef9e77fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 12]: /images/20220226/60f666945cd049e68bfe8e530dc85192.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 13]: /images/20220226/3eb8c6d67157413ab819088e5cdf5604.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 14]: /images/20220226/d485e4d82f8f471eb7e81dcd8dc52569.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 15]: /images/20220226/22dcf7258629454791544224a0c43cd2.png
[20190330141053873.png]: /images/20220226/99bb1f2fa99d4ca9891d537420c88f56.png
[20190330151008945.png]: /images/20220226/b6e0464aa78d4d25aefc92ff1d5b6547.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 16]: /images/20220226/a7f9a6af23574af58403bf04b6a5532c.png
[20190330151118209.png]: /images/20220226/284095ead7ab482fb1c1c119ce6dc87c.png
[2019033015112889.png]: /images/20220226/cb81b63c04714c4e8805476e4bf9b2fc.png
[20190330151133114.png]: /images/20220226/322449cfd7ac4315884443a085658b62.png
[20190330181750314.png]: /images/20220226/c9a28065daa048018366c5b903b9ff8d.png