学步园

       首先，我們定義一個節點類：

 

 1     public class Node
 2     {
 3         public int Data;
 4         public Node Left;
 5         public Node Right;
 6         public void DisplayNode()
 7         {
 8             Console.Write(Data + " ");
 9         }
10     }

 

      再定義二叉樹：

包括二叉樹節點的插入和刪除

 

  1     /// <summary>
  2     /// 二叉查找樹類
  3     /// </summary>
  4     public class BinarySearchTree
  5     {
  6         public Node root;
  7         public BinarySearchTree()
  8         {
  9             root = null;
 10         }
 11 
 12         /// <summary>
 13         /// 插入節點方法
 14         /// </summary>
 15         /// <param name="i">節點鍵值</param>
 16         public void insert(int i)
 17         {
 18             Node newNode = new Node();
 19             newNode.Data = i;
 20 
 21             if (root == null)
 22             {
 23                 root = newNode;
 24             }
 25             else
 26             {
 27                 Node current = root;
 28                 Node parent;
 29 
 30                 while (true)
 31                 {
 32                     parent = current;
 33 
 34                     if (i < current.Data)
 35                     {
 36                         current = current.Left;
 37                         if (current == null)
 38                         {
 39                             parent.Left = newNode;
 40                             break;
 41                         }
 42                     }
 43                     else
 44                     {
 45                         current = current.Right;
 46                         if (current == null)
 47                         {
 48                             parent.Right = newNode;
 49                             break;
 50                         }
 51                     }
 52                 }
 53             }
 54         }
 55 
 56 
 57 
 58         /// <summary>
 59         /// 刪除二叉樹節點
 60         /// </summary>
 61         /// <param name="key">所要刪除的節點</param>
 62         public bool delete(int key)
 63         {
 64             Node current = root;
 65             Node parent = root;
 66             bool isLeftChild = true;
 67 
 68             while (current.Data != key)
 69             {
 70                 parent = current;
 71                 if (key < current.Data)
 72                 {
 73                     isLeftChild = true;
 74                     current = current.Left;
 75 
 76                 }
 77                 else
 78                 {
 79                     isLeftChild = false;
 80                     current = current.Right;
 81                 }
 82                 if (current == null)
 83                     return false;
 84             }
 85             if ((current.Left == null) && (current.Right == null))
 86             {
 87                 if (current == root)
 88                     root = null;
 89 
 90                 else if (isLeftChild)
 91 
 92                     parent.Left = null;
 93             }
 94             else if (current.Right == null)
 95             {
 96                 if (current == root)
 97                     root = current.Left;
 98                 else if (isLeftChild)
 99                     parent.Left = current.Left;
100                 else
101                     parent.Right = current.Right;
102 
103             }
104             else if (current.Left == null)
105             {
106                 if (current == root)
107                     root = current.Left;
108                 else if (isLeftChild)
109                     parent.Left = current.Left;
110                 else
111                     parent.Right = current.Right;
112             }
113 
114             else
115             {
116                 Node successor = GetSuccessor(current);
117                 if (current == root)
118                     root = successor;
119                 else if (isLeftChild)
120                     parent.Left = successor;
121                 else
122                     parent.Right = successor;
123                 successor.Left = current.Left;
124             }
125             return true;
126         }
127 
128         /// <summary>
129         /// 找某節點的后繼節點
130         /// </summary>
131         /// <param name="delNode">某節點</param>
132         /// <returns></returns>
133         public Node GetSuccessor(Node delNode)
134         {
135             Node successorParent = delNode;
136             Node successor = delNode;
137             Node current = delNode.Right;
138             while (!(current == null))
139             {
140                 if (current.Left != null)
141                     successorParent = current;
142 
143                 successor = current;
144                 current = current.Left;
145             }
146             if (!(successor == delNode.Right))
147             {
148                 successorParent.Left = successor.Right;
149                 successor.Right = delNode.Right;
150             }
151             return successor;
152         }
153     }