二叉树-数据结构

作者：AllinToyou | 2024-04-20 00:42:40

踩

二叉树-数据结构

二叉树是属性结构的一个重要类型。
如下图二叉树形状
在这里插入图片描述

二叉树特征如下：
1.二叉树由 n(n >= 0) 个节点组成
2.如果 n 为 0，则为空树
3.如果 n = 1，则只有一个节点称为根节点(root)
4.每个节点最多有两个节点，节点分为左子树和右子树
5.所有左子树和右子树自身也必须是二叉树

如上图
节点6 是跟节点 root
节点6 的左子树和右子树分别是节点4 和节点8

名词概念：
节点：包含一个数据元素及指向若干个子树信息
节点的度：一个节点拥有子树的数量称为节点的度
叶子节点：也称为终端节点，没有子树的节点或者度为零的节点
分支节点：也成非终端节点，有子树的节点或者度不为零的节点
树的度：树中所有节点的度的最大值
树的层次：从根节点开始，假设根节点是第一层，根节点的子节点为第二层，一次类推，如果某一个节点位于第L层，则其子节点位于第 L+1层
树的深度：也成树的高度，树中所有节点的层次最大值称为树的深度
节点的深度：从根节点到节点的路径长度
节点的高度：从节点到其子树叶子节点最长的路径

二叉树的第 i 层上，最多有 2^(i - 1) 个节点，(i >= 1)
高度为 k 的二叉树，最多有 2^k - 1 个节点，(k >= 0)

完全二叉树
1.完全二叉树除了最低一层外，其他层都完全填充，最低层可能有空缺
2.最低一层的节点从左到右填充，空缺的节点只能在右边
3.对任一节点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。即度为1的点只有1个或0个
下图是一个完全二叉树
在这里插入图片描述

满二叉树
1.满二叉树每个非叶子结点都有两个子结点
2.叶子结点都位于树的最低层
3.满二叉树的每一层都完全填充，没有任何空缺
4.一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树是满二叉树

如果一个满二叉树的层数为 k，则节点个数一定是 (2^k) - 1 个
下图是一个满二叉树
在这里插入图片描述
二叉树有下面几种遍历方式
先序遍历：遍历顺序为根节点-> 左子树->右子树
中序遍历：遍历顺序为左子树->根节点-> 右子树
后序遍历：遍历顺序为左子树->右子树->根节点
层序遍历：按照层遍历，将一层所有的数据从左到右获取到，然后获取下一层

下面是C# 实现的二叉树，包含了上面几种遍历实现，这几种遍历的具体讲解看后续篇章

using System;

namespace DataStruct.BinTree
{
    /// <summary>
    /// 红黑树节点颜色枚举
    /// </summary>
    public enum Color
    {
        Red, 
        Black,
    }

    /// <summary>
    /// 二叉树节点定义
    /// </summary>
    /// <typeparam name="T">节点存储数据的类型</typeparam>
    public class BinNode<T> where T : IComparable<T>
    {
        // 节点值
        private T _element;
        // 父节点
        private BinNode<T> _parentNode;
        // 左子树
        private BinNode<T> _leftChild;
        // 右子树
        private BinNode<T> _rightChild;
        // 树高度
        private int _height;
        // 红黑树节点颜色
        private Color _color;

        public BinNode(T value)
        {
            _element = value;
        }

        public BinNode(T value, BinNode<T> parent)
        {
            _element = value;
            ParentNode = parent;
        }

        public BinNode<T> ParentNode
        {
            get { return _parentNode; }
            set { _parentNode = value; }
        }

        /// <summary>
        /// 获取左子树
        /// </summary>
        public BinNode<T> LeftChild
        {
            get { return _leftChild; }
            set { _leftChild = value; }
        }

        /// <summary>
        /// 获取右子树
        /// </summary>
        public BinNode<T> RightChild
        {
            get { return _rightChild; }
            set { _rightChild = value; }
        }

        /// <summary>
        /// 获取节点值
        /// </summary>
        public T Element
        {
            get { return _element; }
            set { _element = value; }
        }

        /// <summary>
        /// 获取树高度
        /// </summary>
        public int Height
        {
            get { return _height; }
            set { _height = value; }
        }

        /// <summary>
        /// 获取红黑树节点颜色
        /// </summary>
        public Color Color
        {
            get { return _color; }
            set { _color = value; }
        }

        /// <summary>
        /// 作为当前节点的左孩子插入新节点
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        public BinNode<T> InsertAsLc(T t)
        {
            BinNode<T> leftChild = new BinNode<T>(t);
            return InsertAsLc(leftChild);
        }

        /// <summary>
        /// 作为当前节点的左孩子插入新节点
        /// </summary>
        /// <param name="leftChild"></param>
        /// <returns></returns>
        public BinNode<T> InsertAsLc(BinNode<T> leftChild)
        {
            _leftChild = leftChild;
            if (null != leftChild)
            {
                leftChild.ParentNode = this;
            }
            return _leftChild;
        }

        /// <summary>
        /// 作为当前节点的右孩子插入新节点
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        public BinNode<T> InsertAsRc(T t)
        {
            BinNode<T> rightChild = new BinNode<T>(t);
            return InsertAsRc(rightChild);
        }

        /// <summary>
        /// 作为当前节点的右孩子插入新节点
        /// </summary>
        /// <param name="rightChild"></param>
        /// <returns></returns>
        public BinNode<T> InsertAsRc(BinNode<T> rightChild)
        {
            _rightChild = rightChild;
            if(null != rightChild)
            {
                rightChild.ParentNode = this;
            }
            return _rightChild;
        }

        /// <summary>
        /// 是否根节点
        /// </summary>
        /// <returns></returns>
        public bool IsRoot()
        {
            return null == ParentNode;
        }

        public bool HasParent()
        {
            return !IsRoot();
        }

        public bool HasLChild()
        {
            return null != LeftChild;
        }

        public bool HasRChild()
        {
            return null != RightChild;
        }

        /// <summary>
        /// 是父节点的左孩子
        /// </summary>
        /// <returns></returns>
        public bool IsLChild()
        {
            return !IsRoot() && this == ParentNode.LeftChild;
        }

        /// <summary>
        /// 是父节点的右孩子
        /// </summary>
        /// <returns></returns>
        public bool IsRChild()
        {
            return !IsRoot() && this == ParentNode.RightChild;
        }

        /// <summary>
        /// 有左子树或者右子树
        /// </summary>
        /// <returns></returns>
        public bool HasChild()
        {
            return HasLChild() || HasRChild();
        }

        /// <summary>
        /// 有左子树并且有右子树
        /// </summary>
        /// <returns></returns>
        public bool HasBoothChild()
        {
            return HasLChild() && HasRChild();
        }

        /// <summary>
        /// 是否叶子节点
        /// </summary>
        /// <returns></returns>
        public bool IsLeaf()
        {
            return !HasChild();
        }

        /// <summary>
        /// 是红黑树黑节点
        /// </summary>
        /// <returns></returns>
        public bool IsBlack()
        {
            return Color == Color.Black;
        }

        /// <summary>
        /// 是红黑树红节点
        /// </summary>
        /// <returns></returns>
        public bool IsRed()
        {
            return Color == Color.Red;
        }

        /// <summary>
        /// 重写 == 方法
        /// </summary>
        /// <param name="node1"></param>
        /// <param name="node2"></param>
        /// <returns></returns>
        public static bool operator == (BinNode<T> node1, BinNode<T> node2)
        {
            if (object.Equals(node1, null) || object.Equals(node2, null))
            {
                return object.Equals(node1, node2);
            }
            return node1.Element.CompareTo(node2.Element) == 0;
        }

        /// <summary>
        /// 重写 != 方法
        /// </summary>
        /// <param name="node1"></param>
        /// <param name="node2"></param>
        /// <returns></returns>
        public static bool operator != (BinNode<T> node1, BinNode<T> node2)
        {
            if (object.Equals(node1, null) || object.Equals(node2, null))
            {
                return !object.Equals(node1, node2);
            }
            return node1.Element.CompareTo(node2.Element) != 0;
        }

        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274

二叉树实现部分

    /// <summary>
    /// 二叉树
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BinTree<T> where T : IComparable<T>
    {
        private BinNode<T> _root = null;   // 跟节点

        public BinTree()
        {
            _root = null;
        }

        public BinNode<T> Root
        {
            get { return _root; }
            protected set { _root = value; }
        }

        public bool Empty()
        {
            return null == Root;
        }

        /// <summary>
        /// 删除节点
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public virtual bool Remove(BinNode<T> node)
        {
            if (node.IsRoot())
            {
                Root = null;
                return true;
            }
            
            if (node.IsLChild())
            {
                node.ParentNode.LeftChild = null;
            }
            else
            {
                node.ParentNode.RightChild = null;
            }

            UpdateHeightAbove(node.ParentNode);
            return true;
        }

        /// <summary>
        /// 清空树，并创建新的根节点
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        public virtual BinNode<T> InsertAsRoot(T t)
        {
            _root = new BinNode<T>(t);
            UpdateHeightAbove(_root);
            return _root;
        }

        /// <summary>
        /// 作为当前节点的左孩子插入新节点
        /// </summary>
        /// <param name="node"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public virtual BinNode<T> InsertAsLc(BinNode<T> node, T t)
        {
            node.InsertAsLc(t);
            UpdateHeightAbove(node);
            return node.LeftChild;
        }

        /// <summary>
        /// 作为当前节点的右孩子插入新节点
        /// </summary>
        /// <param name="node"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public virtual BinNode<T> InsertAsRc(BinNode<T> node, T t)
        {
            node.InsertAsRc(t);
            UpdateHeightAbove(node);
            return node.RightChild;
        }

        #region Recursion
        /// <summary>
        /// 递归实现 先序遍历：跟节点->左子树->右子树
        /// </summary>
        /// <param name="node"></param>
        public void TraversePreRecursion(BinNode<T> node)
        {
            if (null == node)
            {
                return;
            }

            Console.Write(node.Element.ToString() + "    ");
            TraversePreRecursion(node.LeftChild);
            TraversePreRecursion(node.RightChild);
        }

        /// <summary>
        /// 递归实现 中序遍历：左子树->跟节点->右子树  递归实现
        /// </summary>
        /// <param name="node"></param>
        public void TraverseiInRecursion(BinNode<T> node)
        {
            if (null == node)
            {
                return;
            }

            TraverseiInRecursion(node.LeftChild);
            Console.Write(node.Element.ToString() + "    ");
            TraverseiInRecursion(node.RightChild);
        }

        /// <summary>
        /// 递归实现 后序遍历：左子树->右子树->跟节点
        /// </summary>
        /// <param name="node"></param>
        public void TraverseiPostRecursion(BinNode<T> node)
        {
            if (null == node)
            {
                return;
            }

            TraverseiPostRecursion(node.LeftChild);
            TraverseiPostRecursion(node.RightChild);
            Console.Write(node.Element.ToString() + "    ");
        }
        #endregion

        #region Iteration
        /// <summary>
        /// 迭代实现 先序遍历：跟节点->左子树->右子树
        /// </summary>
        /// <param name="node"></param>
        public void TraversePre(BinNode<T> node)
        {
            if (null == node)
            {
                return;
            }

            Stack<BinNode<T>> stack = new Stack<BinNode<T>>();
            stack.Push(node);
            while (stack.Count > 0)
            {
                node = stack.Pop();
                Console.Write(node.Element.ToString() + "    ");
                if (node.HasRChild())
                {
                    stack.Push(node.RightChild);
                }
                if(node.HasLChild())
                {
                    stack.Push(node.LeftChild);
                }
            }
        }

        /// <summary>
        /// 迭代实现 先序遍历：跟节点->左子树->右子树
        /// </summary>
        /// <param name="node"></param>
        public void TraversePre2(BinNode<T> node)
        {
            if (null == node)
            {
                return;
            }

            Stack<BinNode<T>> stack = new Stack<BinNode<T>>();
            stack.Push(node);
            while (stack.Count > 0)
            {
                while (null != node)
                {
                    Console.Write(node.Element.ToString() + "    ");
                    if ((node = node.LeftChild) != null)
                    {
                        stack.Push(node);
                    }
                }

                node = stack.Pop();
                if (null != node && ((node = node.RightChild) != null))
                {
                    stack.Push(node);
                }
            }
        }

        /// <summary>
        /// 迭代实现 中序遍历：左子树->跟节点->右子树
        /// </summary>
        /// <param name="node"></param>
        public void TraverseIn(BinNode<T> node)
        {
            if (null == node)
            {
                return;
            }

            Stack<BinNode<T>> stack = new Stack<BinNode<T>>();
            stack.Push(node);
            while (stack.Count > 0)
            {
                while (null != node)
                {
                    if ((node = node.LeftChild) != null)
                    {
                        stack.Push(node);
                    }
                }

                node = stack.Pop();
                Console.Write(node.Element.ToString() + "    ");
                if (null != node && ((node = node.RightChild) != null))
                {
                    stack.Push(node);
                }
            }
        }

        /// <summary>
        /// 迭代实现 后序遍历：左子树->右子树->跟节点
        /// </summary>
        /// <param name="node"></param>
        public void TraversePost(BinNode<T> node)
        {
            if (null == node)
            {
                return;
            }

            Stack<BinNode<T>> result = new Stack<BinNode<T>>();
            Stack<BinNode<T>> stack = new Stack<BinNode<T>>();
            stack.Push(node);
            while (stack.Count > 0)
            {
                node = stack.Pop();
                result.Push(node);
                if (node.HasLChild())
                {
                    stack.Push(node.LeftChild);
                }
                if (node.HasRChild())
                {
                    stack.Push(node.RightChild);
                }
            }

            while (result.Count > 0)
            {
                BinNode<T> temp = result.Pop();
                Console.Write(temp.Element.ToString() + "    ");
            }

            Console.WriteLine();
        }

        //、层序遍历：按层从上到下，每层从左到右依次遍历
        public List<BinNode<T>> TraverseLevel(BinNode<T> node)
        {
            List<BinNode<T>> list = new List<BinNode<T>>();
            if (null == node)
            {
                return list;
            }

            Queue<BinNode<T>> queue = new Queue<BinNode<T>>();
            queue.Enqueue(node);
            while (queue.Count > 0)
            {
                node = queue.Dequeue();
                Console.Write(node.Element.ToString() + "   ");
                list.Add(node);
                if (node.HasLChild())
                {
                    queue.Enqueue(node.LeftChild);
                }
                if (node.HasRChild())
                {
                    queue.Enqueue(node.RightChild);
                }
            }
            return list;
        }
        #endregion

        /// <summary>
        /// 更新树高度
        /// </summary>
        /// <param name="node"></param>
        protected void UpdateHeightAbove(BinNode<T> node)
        {
            while (null != node) // 从node出发，覆盖历代祖先
            {
                UpdateHeight(node);
                node = node.ParentNode;
            }
        }

        /// <summary>
        /// 更新树高度
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        protected virtual int UpdateHeight(BinNode<T> node)
        {
            node.Height = 1 + Math.Max(NodeHeight(node.LeftChild), NodeHeight(node.RightChild));
            return node.Height;
        }

        /// <summary>
        /// 后去节点的高度
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        protected int NodeHeight(BinNode<T> node)
        {
            return (null != node) ? node.Height : -1;
        }

        public virtual void Release()
        {
            _root = null;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/454462