C#实现二叉树

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace BinaryTree
  8 {
  9     class Program
 10     {
 11         static void Main(string[] args)
 12         {
 13             Tree<int> myTree = new Tree<int>(5);
 14             for (int i = 0; i < 10; i++)
 15             {
 16                 myTree.Insert(i);
 17             }
 18             //myTree.WideOrderTree();
 19             //myTree.PreOrderTree(myTree);
 20             //myTree.InOrderTree(myTree);
 21             myTree.PostOrderTree(myTree);
 22         }
 23 
 24         //定义二叉树
 25         public class Tree<T> where T : IComparable<T>
 26         {
 27             private T data;
 28             private Tree<T> leftTree;
 29             private Tree<T> rightTree;
 30 
 31             //属性
 32             public T Data
 33             {
 34                 get
 35                 {
 36                     return data;
 37                 }
 38                 set
 39                 {
 40                     data = value;
 41                 }
 42             }
 43 
 44             public Tree<T> LeftTree
 45             {
 46                 get
 47                 {
 48                     return leftTree;
 49                 }
 50                 set
 51                 {
 52                     leftTree = value;
 53                 }
 54             }
 55 
 56             public Tree<T> RightTree
 57             {
 58                 get
 59                 {
 60                     return rightTree;
 61                 }
 62                 set
 63                 {
 64                     rightTree = value;
 65                 }
 66             }
 67 
 68             //构造函数，定义二叉树根节点
 69             public Tree(T data)
 70             {
 71                 this.data = data;
 72                 leftTree = null;
 73                 rightTree = null;
 74             }
 75 
 76             /// <summary>
 77             /// 向二叉树中插入一个新的结点
 78             /// 小于根节点插入左子树
 79             /// 大于根节点插入右子树
 80             /// </summary>
 81             public void Insert(T data)
 82             {
 83                 T dataNow = Data;
 84                 if (data.CompareTo(dataNow) < 0)
 85                 {
 86                     if (LeftTree == null)
 87                     {
 88                         LeftTree = new Tree<T>(data);
 89                     }
 90                     else
 91                     {
 92                         LeftTree.Insert(data);
 93                     }
 94                 }
 95                 else
 96                 {
 97                     if (RightTree == null)
 98                     {
 99                         RightTree = new Tree<T>(data);
100                     }
101                     else
102                     {
103                         RightTree.Insert(data);
104                     }
105                 }
106             }
107 
108             /// <summary>
109             /// 前序遍历：中左右
110             /// </summary>
111             public void PreOrderTree(Tree<T> root)
112             {
113                 if (root != null)
114                 {
115                     Console.WriteLine(root.Data);
116                     PreOrderTree(root.LeftTree);
117                     PreOrderTree(root.RightTree);
118                 }
119             }
120 
121             /// <summary>
122             /// 中序遍历：左中右
123             /// </summary>
124             public void InOrderTree(Tree<T> root)
125             {
126                 if (root != null)
127                 {
128                     InOrderTree(root.LeftTree);
129                     Console.WriteLine(root.Data);
130                     InOrderTree(root.RightTree);
131                 }
132             }
133 
134             /// <summary>
135             /// 后序遍历：左右中
136             /// </summary>
137             public void PostOrderTree(Tree<T> root)
138             {
139                 if (root != null)
140                 {
141                     PostOrderTree(root.LeftTree);
142                     PostOrderTree(root.RightTree);
143                     Console.WriteLine(root.Data);
144                 }
145             }
146 
147             /// <summary>
148             /// 逐层遍历：
149             /// 1. 从根节点开始，访问一个节点然后将其左右子树的根节点一次放入链表，然后删除该根节点。
150             /// 2. 依次遍历链表中的元素，直到链表中元素数量为0。
151             /// </summary>
152             public void WideOrderTree()
153             {
154                 List<Tree<T>> nodeList = new List<Tree<T>>();
155                 nodeList.Add(this);
156                 Tree<T> temp = null;
157                 while (nodeList.Count > 0)
158                 {
159                     Console.WriteLine(nodeList[0].Data);
160                     temp = nodeList[0];
161                     nodeList.RemoveAt(0);
162                     if (temp.LeftTree != null)
163                     {
164                         nodeList.Add(temp.LeftTree);
165                     }
166                     if (temp.RightTree != null)
167                     {
168                         nodeList.Add(temp.RightTree);
169                     }
170                 }
171             }
172         }
173     }
174 }