排序二叉树的实现

时间:2022-02-08 15:13:57

实现了如下基本功能:

1。添加节点

2。删除节点

3。查找最小值

4。查找最大值

5。中序遍历 

  1排序二叉树的实现using System;
  2排序二叉树的实现using System.Collections.Generic;
  3排序二叉树的实现using System.Text;
  4排序二叉树的实现
  5排序二叉树的实现namespace BinarySearchTree
  6排序二叉树的实现{
  7排序二叉树的实现    class Program
  8排序二叉树的实现    {
  9排序二叉树的实现        static void Main(string[] args)
 10排序二叉树的实现        {
 11排序二叉树的实现            BinarySearchTree bTree = new BinarySearchTree();
 12排序二叉树的实现            bTree.Insert(5);
 13排序二叉树的实现            bTree.Insert(8);
 14排序二叉树的实现            bTree.Insert(39);
 15排序二叉树的实现            bTree.Insert(23);
 16排序二叉树的实现            bTree.Insert(12);
 17排序二叉树的实现          
 18排序二叉树的实现            bTree.InOrder();
 19排序二叉树的实现            bTree.Delete(8);
 20排序二叉树的实现            bTree.InOrder();
 21排序二叉树的实现           // Console.WriteLine(bTree.GetSuccessor(8));
 22排序二叉树的实现            //Console.WriteLine(bTree.FindMax());
 23排序二叉树的实现            //Console.WriteLine(bTree.FindMin());
 24排序二叉树的实现            //Console.WriteLine(bTree.Delete(99));
 25排序二叉树的实现        }

 26排序二叉树的实现    }

 27排序二叉树的实现
 28排序二叉树的实现   public class Node
 29排序二叉树的实现    {
 30排序二叉树的实现        int date;
 31排序二叉树的实现       //节点数据
 32排序二叉树的实现        public int Date
 33排序二叉树的实现        {
 34排序二叉树的实现            get return date; }
 35排序二叉树的实现            set { date = value; }
 36排序二叉树的实现        }

 37排序二叉树的实现        Node left;
 38排序二叉树的实现//左子树
 39排序二叉树的实现        public Node Left
 40排序二叉树的实现        {
 41排序二叉树的实现            get return left; }
 42排序二叉树的实现            set { left = value; }
 43排序二叉树的实现        }

 44排序二叉树的实现        Node right;
 45排序二叉树的实现//右子树
 46排序二叉树的实现        public Node Right
 47排序二叉树的实现        {
 48排序二叉树的实现            get return right; }
 49排序二叉树的实现            set { right = value; }
 50排序二叉树的实现        }

 51排序二叉树的实现
 52排序二叉树的实现       public Node()
 53排序二叉树的实现       {
 54排序二叉树的实现       }

 55排序二叉树的实现       public Node(int date)
 56排序二叉树的实现       {
 57排序二叉树的实现           this.date = date;
 58排序二叉树的实现       }

 59排序二叉树的实现    }

 60排序二叉树的实现
 61排序二叉树的实现    public class BinarySearchTree//排序二叉树
 62排序二叉树的实现    {
 63排序二叉树的实现        Node root;
 64排序二叉树的实现        public BinarySearchTree()
 65排序二叉树的实现        {
 66排序二叉树的实现            root = null;
 67排序二叉树的实现        }

 68排序二叉树的实现
 69排序二叉树的实现//插入数据
 70排序二叉树的实现        public void Insert(int i)
 71排序二叉树的实现        {
 72排序二叉树的实现            Node newNode = new Node(i);
 73排序二叉树的实现            if (root == null)
 74排序二叉树的实现            {
 75排序二叉树的实现                root = newNode;
 76排序二叉树的实现                return;
 77排序二叉树的实现            }

 78排序二叉树的实现            Node current = root;
 79排序二叉树的实现            Node parent;
 80排序二叉树的实现            while (true)
 81排序二叉树的实现            {
 82排序二叉树的实现                parent = current;
 83排序二叉树的实现                if (i < current.Date)
 84排序二叉树的实现                {
 85排序二叉树的实现                    current = current.Left;
 86排序二叉树的实现                    if (current == null)
 87排序二叉树的实现                    {
 88排序二叉树的实现                        parent.Left = newNode;
 89排序二叉树的实现                        break;
 90排序二叉树的实现                    }

 91排序二叉树的实现                }

 92排序二叉树的实现                else
 93排序二叉树的实现                {
 94排序二叉树的实现                    current = current.Right;
 95排序二叉树的实现                    if (current == null)
 96排序二叉树的实现                    {
 97排序二叉树的实现                        parent.Right = newNode;
 98排序二叉树的实现                        break;
 99排序二叉树的实现                    }

100排序二叉树的实现                }

101排序二叉树的实现            }
    
102排序二叉树的实现        }

103排序二叉树的实现
104排序二叉树的实现        public void InOrder()//中序遍历
105排序二叉树的实现        {
106排序二叉树的实现            InOrder(root);
107排序二叉树的实现        }

108排序二叉树的实现        private void InOrder(Node root)
109排序二叉树的实现        {
110排序二叉树的实现            if(root!=null)
111排序二叉树的实现            {
112排序二叉树的实现            InOrder(root.Left);
113排序二叉树的实现            Console.WriteLine(root.Date);
114排序二叉树的实现            InOrder(root.Right);
115排序二叉树的实现            }

116排序二叉树的实现        }

117排序二叉树的实现
118排序二叉树的实现        public int FindMax()//查找最大值
119排序二叉树的实现        {
120排序二叉树的实现            Node current = root;
121排序二叉树的实现            while (current.Right!= null)
122排序二叉树的实现            {
123排序二叉树的实现                current = current.Right;
124排序二叉树的实现            }

125排序二叉树的实现            return current.Date;
126排序二叉树的实现        }

127排序二叉树的实现
128排序二叉树的实现        public int FindMin()//查找最小值
129排序二叉树的实现        {
130排序二叉树的实现            Node current = root;
131排序二叉树的实现            while (current.Left != null)
132排序二叉树的实现            {
133排序二叉树的实现                current = current.Left;
134排序二叉树的实现            }

135排序二叉树的实现            return current.Date;
136排序二叉树的实现        }

137排序二叉树的实现
138排序二叉树的实现
139排序二叉树的实现        public Node GetSuccessor(Node delNode)//获得当前节点的下一个节点(中序位置)
140排序二叉树的实现        {
141排序二叉树的实现            Node parent = delNode;
142排序二叉树的实现            Node current = delNode.Right;
143排序二叉树的实现            while (current.Left != null)
144排序二叉树的实现            {
145排序二叉树的实现                parent = current;
146排序二叉树的实现                current = current.Left;
147排序二叉树的实现            }
//找到要删除节点右子树的最小节点
148排序二叉树的实现            if (current != delNode.Right)
149排序二叉树的实现            {
150排序二叉树的实现                parent.Left = current.Right;
151排序二叉树的实现                current.Right = delNode.Right;
152排序二叉树的实现            }
//将最小节点从原位置移出,并将拟删除节点的右子树挂到其右子树上
153排序二叉树的实现            return current;
154排序二叉树的实现            
155排序二叉树的实现        }

156排序二叉树的实现
157排序二叉树的实现        public bool Delete(int key)
158排序二叉树的实现        {
159排序二叉树的实现            Node current = root;
160排序二叉树的实现            Node parent = root;
161排序二叉树的实现            bool isLeft = false;
162排序二叉树的实现            //找到要删除的节点
163排序二叉树的实现            while (current.Date != key)
164排序二叉树的实现            {
165排序二叉树的实现                parent = current;
166排序二叉树的实现                if (current.Date > key)
167排序二叉树的实现                {
168排序二叉树的实现                    current = current.Left;
169排序二叉树的实现                    isLeft = true;
170排序二叉树的实现                }

171排序二叉树的实现                else
172排序二叉树的实现                {
173排序二叉树的实现                    current = current.Right;
174排序二叉树的实现                    isLeft = false;
175排序二叉树的实现                }

176排序二叉树的实现                if (current == null)
177排序二叉树的实现                    return false;
178排序二叉树的实现            }

179排序二叉树的实现            //如果要删除的是叶子节点
180排序二叉树的实现            if (current.Left == null && current.Right == null)
181排序二叉树的实现            {
182排序二叉树的实现                if (current == root)
183排序二叉树的实现                {
184排序二叉树的实现                    root = null;
185排序二叉树的实现                }

186排序二叉树的实现                else if (isLeft)
187排序二叉树的实现                {
188排序二叉树的实现                    parent.Left = null;
189排序二叉树的实现                }

190排序二叉树的实现                else
191排序二叉树的实现                {
192排序二叉树的实现                    parent.Right = null;
193排序二叉树的实现                }

194排序二叉树的实现            }

195排序二叉树的实现               //如果要删除的节点只有右子树
196排序二叉树的实现            else if (current.Left == null)
197排序二叉树的实现            {
198排序二叉树的实现                if (current == root)
199排序二叉树的实现                {
200排序二叉树的实现                   root = current.Right;
201排序二叉树的实现                }

202排序二叉树的实现                else if (isLeft)
203排序二叉树的实现                {
204排序二叉树的实现                    parent.Left = current.Right;
205排序二叉树的实现                }

206排序二叉树的实现                else
207排序二叉树的实现                {
208排序二叉树的实现                    parent.Right = current.Right;
209排序二叉树的实现                }

210排序二叉树的实现            }

211排序二叉树的实现                //如果拟删除的节点只有左子树
212排序二叉树的实现            else if (current.Right == null)
213排序二叉树的实现            {
214排序二叉树的实现                if (current == root)
215排序二叉树的实现                {
216排序二叉树的实现                    root = current.Left;
217排序二叉树的实现                }

218排序二叉树的实现                else if (isLeft)
219排序二叉树的实现                {
220排序二叉树的实现                    parent.Left = current.Left;
221排序二叉树的实现                }

222排序二叉树的实现                else
223排序二叉树的实现                {
224排序二叉树的实现                    parent.Right = current.Left;
225排序二叉树的实现                }

226排序二叉树的实现            }
//如果删除的节点既有左子树,又有右子树
227排序二叉树的实现            else
228排序二叉树的实现            {
229排序二叉树的实现                Node successor = GetSuccessor(current);
230排序二叉树的实现                if (current == root)
231排序二叉树的实现                {
232排序二叉树的实现                    root = successor;
233排序二叉树的实现                }

234排序二叉树的实现                else if (isLeft)
235排序二叉树的实现                {
236排序二叉树的实现                    parent.Left = successor;
237排序二叉树的实现                }

238排序二叉树的实现                else
239排序二叉树的实现                {
240排序二叉树的实现                    parent.Right = successor;
241排序二叉树的实现                }

242排序二叉树的实现
243排序二叉树的实现                successor.Left = current.Left;
244排序二叉树的实现            }

245排序二叉树的实现            
246排序二叉树的实现            return true;
247排序二叉树的实现
248排序二叉树的实现        }

249排序二叉树的实现    }

250排序二叉树的实现
251排序二叉树的实现}

252排序二叉树的实现