首页 > 代码库 > C#实现二叉树 二叉链表结构
C#实现二叉树 二叉链表结构
二叉链表存储结构：
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：
其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表，如图5-8所示。
C#实现代码
1 Binary Tree 2 3 using System; 4 using System.Collections.Generic; 5 using System.Linq; 6 using System.Text; 7 8 namespace DataStructure 9 { 10 /// <summary> 11 /// 二叉链表结点类 12 /// </summary> 13 /// <typeparam name="T"></typeparam> 14 public class TreeNode<T> 15 { 16 private T data; //数据域 17 private TreeNode<T> lChild; //左孩子 树中一个结点的子树的根结点称为这个结点的孩子 18 private TreeNode<T> rChild; //右孩子 19 20 public TreeNode(T val, TreeNode<T> lp, TreeNode<T> rp) 21 { 22 data =http://www.mamicode.com/ val; 23 lChild = lp; 24 rChild = rp; 25 } 26 27 public TreeNode(TreeNode<T> lp, TreeNode<T> rp) 28 { 29 data = http://www.mamicode.com/default(T); 30 lChild = lp; 31 rChild = rp; 32 } 33 34 public TreeNode(T val) 35 { 36 data =http://www.mamicode.com/ val; 37 lChild = null; 38 rChild = null; 39 } 40 41 public TreeNode() 42 { 43 data = http://www.mamicode.com/default(T); 44 lChild = null; 45 rChild = null; 46 } 47 48 public T Data 49 { 50 get { return data; } 51 set { data =http://www.mamicode.com/ value; } 52 } 53 54 public TreeNode<T> LChild 55 { 56 get { return lChild; } 57 set { lChild = value; } 58 } 59 60 public TreeNode<T> RChild 61 { 62 get { return rChild; } 63 set { rChild = value; } 64 } 65 66 } 67 68 /// <summary> 69 /// 定义索引文件结点的数据类型 70 /// </summary> 71 public struct indexnode 72 { 73 int key; //键 74 int offset; //位置 75 public indexnode(int key, int offset) 76 { 77 this.key = key; 78 this.offset = offset; 79 } 80 81 //键属性 82 public int Key 83 { 84 get { return key; } 85 set { key = value; } 86 } 87 //位置属性 88 public int Offset 89 { 90 get { return offset; } 91 set { offset = value; } 92 } 93 94 95 } 96 97 98 public class LinkBinaryTree<T> 99 {100 private TreeNode<T> head; //头引用101 102 public TreeNode<T> Head103 {104 get { return head; }105 set { head = value; }106 }107 108 public LinkBinaryTree()109 {110 head = null;111 }112 113 public LinkBinaryTree(T val)114 {115 TreeNode<T> p = new TreeNode<T>(val);116 head = p;117 }118 119 public LinkBinaryTree(T val, TreeNode<T> lp, TreeNode<T> rp)120 {121 TreeNode<T> p = new TreeNode<T>(val, lp, rp);122 head = p;123 }124 125 //判断是否是空二叉树126 public bool IsEmpty()127 {128 if (head == null)129 return true;130 else131 return false;132 }133 134 //获取根结点135 public TreeNode<T> Root()136 {137 return head;138 }139 140 //获取结点的左孩子结点141 public TreeNode<T> GetLChild(TreeNode<T> p)142 {143 return p.LChild;144 }145 146 public TreeNode<T> GetRChild(TreeNode<T> p)147 {148 return p.RChild;149 }150 151 //将结点p的左子树插入值为val的新结点，原来的左子树称为新结点的左子树152 public void InsertL(T val, TreeNode<T> p)153 {154 TreeNode<T> tmp = new TreeNode<T>(val);155 tmp.LChild = p.LChild;156 p.LChild = tmp;157 }158 159 //将结点p的右子树插入值为val的新结点，原来的右子树称为新节点的右子树160 public void InsertR(T val, TreeNode<T> p)161 {162 TreeNode<T> tmp = new TreeNode<T>(val);163 tmp.RChild = p.RChild;164 p.RChild = tmp;165 }166 167 //若p非空 删除p的左子树168 public TreeNode<T> DeleteL(TreeNode<T> p)169 {170 if ((p == null) || (p.LChild == null))171 return null;172 TreeNode<T> tmp = p.LChild;173 p.LChild = null;174 return tmp;175 }176 177 //若p非空 删除p的右子树178 public TreeNode<T> DeleteR(TreeNode<T> p)179 {180 if ((p == null) || (p.RChild == null))181 return null;182 TreeNode<T> tmp = p.RChild;183 p.RChild = null;184 return tmp;185 }186 187 //编写算法 在二叉树中查找值为value的结点188 189 public TreeNode<T> Search(TreeNode<T> root, T value)190 {191 TreeNode<T> p = root;192 if (p == null)193 return null;194 if (!p.Data.Equals(value))195 return p;196 if (p.LChild != null)197 {198 return Search(p.LChild, value);199 }200 if (p.RChild != null)201 {202 return Search(p.RChild, value);203 }204 return null;205 }206 207 //判断是否是叶子结点208 public bool IsLeaf(TreeNode<T> p)209 {210 if ((p != null) && (p.RChild == null) && (p.LChild == null))211 return true;212 else213 return false;214 }215 216 217 //中序遍历218 //遍历根结点的左子树->根结点->遍历根结点的右子树 219 public void inorder(TreeNode<T> ptr)220 {221 if (IsEmpty())222 {223 Console.WriteLine("Tree is Empty !");224 return;225 }226 if (ptr != null)227 {228 inorder(ptr.LChild);229 Console.WriteLine(ptr.Data + " ");230 inorder(ptr.RChild);231 }232 }233 234 235 //先序遍历236 //根结点->遍历根结点的左子树->遍历根结点的右子树 237 public void preorder(TreeNode<T> ptr)238 {239 if (IsEmpty())240 {241 Console.WriteLine("Tree is Empty !");242 return;243 }244 if (ptr != null)245 {246 Console.WriteLine(ptr.Data + " ");247 preorder(ptr.LChild);248 preorder(ptr.RChild);249 }250 }251 252 253 //后序遍历254 //遍历根结点的左子树->遍历根结点的右子树->根结点255 public void postorder(TreeNode<T> ptr)256 {257 if (IsEmpty())258 {259 Console.WriteLine("Tree is Empty !");260 return;261 }262 if (ptr != null)263 {264 postorder(ptr.LChild);265 postorder(ptr.RChild);266 Console.WriteLine(ptr.Data + "");267 }268 }269 270 271 //层次遍历272 //引入队列 273 public void LevelOrder(TreeNode<T> root)274 {275 if (root == null)276 {277 return;278 }279 CSeqQueue<TreeNode<T>> sq = new CSeqQueue<TreeNode<T>>(50);280 sq.EnQueue(root);281 while (!sq.IsEmpty())282 {283 //结点出队284 TreeNode<T> tmp = sq.DeQueue();285 //处理当前结点286 Console.WriteLine("{0}", tmp);287 //将当前结点的左孩子结点入队288 if (tmp.LChild != null)289 {290 sq.EnQueue(tmp.LChild);291 }292 if (tmp.RChild != null)293 {294 sq.EnQueue(tmp.RChild);295 }296 }297 }298 }299 300 /// <summary>301 /// 二叉搜索树：结点的左子节点的值永远小于该结点的值，而右子结点的值永远大于该结点的值 称为二叉搜索树302 /// </summary>303 public class LinkBinarySearchTree : LinkBinaryTree<indexnode>304 {305 //定义增加结点的方法306 public void insert(indexnode element)307 {308 TreeNode<indexnode> tmp, parent = null, currentNode = null;309 //调用FIND方法310 find(element, ref parent, ref currentNode);311 if (currentNode != null)312 {313 Console.WriteLine("Duplicates words not allowed");314 return;315 }316 else317 {318 //创建结点319 tmp = new TreeNode<indexnode>(element);320 if (parent == null)321 Head = tmp;322 else323 {324 if (element.Key < parent.Data.Key)325 parent.LChild = tmp;326 else327 parent.RChild = tmp;328 }329 }330 }331 332 //定义父结点333 public void find(indexnode element, ref TreeNode<indexnode> parent, ref TreeNode<indexnode> currentNode)334 {335 currentNode = Head;336 parent = null;337 while ((currentNode != null) && (currentNode.Data.Key.ToString() != element.Key.ToString()) && (currentNode.Data.Offset .ToString() != element.Offset .ToString()))//338 {339 parent = currentNode;340 if (element.Key < currentNode.Data.Key)341 currentNode = currentNode.LChild;342 else343 currentNode = currentNode.RChild;344 }345 }346 347 //定位结点348 public void find(int key)349 {350 TreeNode<indexnode> currentNode = Head;351 while ((currentNode != null) && (currentNode.Data.Key.ToString () != key.ToString ()))352 {353 Console.WriteLine(currentNode.Data.Offset.ToString());354 if (key < currentNode.Data.Key)355 currentNode = currentNode.LChild;356 else357 currentNode = currentNode.RChild;358 }359 }360 361 //中序遍历362 //遍历根结点的左子树->根结点->遍历根结点的右子树 363 public void inorderS(TreeNode<indexnode> ptr)364 {365 if (IsEmpty())366 {367 Console.WriteLine("Tree is Empty !");368 return;369 }370 if (ptr != null)371 {372 inorderS(ptr.LChild);373 Console.WriteLine(ptr.Data.Key + " ");374 inorderS(ptr.RChild);375 }376 }377 378 379 //先序遍历380 //根结点->遍历根结点的左子树->遍历根结点的右子树 381 public void preorderS(TreeNode<indexnode> ptr)382 {383 if (IsEmpty())384 {385 Console.WriteLine("Tree is Empty !");386 return;387 }388 if (ptr != null)389 {390 Console.WriteLine(ptr.Data.Key + " ");391 preorderS(ptr.LChild);392 preorderS(ptr.RChild);393 }394 }395 396 397 //后序遍历398 //遍历根结点的左子树->遍历根结点的右子树->根结点399 public void postorderS(TreeNode<indexnode> ptr)400 {401 if (IsEmpty())402 {403 Console.WriteLine("Tree is Empty !");404 return;405 }406 if (ptr != null)407 {408 postorderS(ptr.LChild);409 postorderS(ptr.RChild);410 Console.WriteLine(ptr.Data.Key + "");411 }412 }413 }414 415 416 /// <summary>417 /// 循环顺序队列418 /// </summary>419 /// <typeparam name="T"></typeparam>420 class CSeqQueue<T>421 {422 private int maxsize; //循环顺序队列的容量423 private T[] data; //数组，用于存储循环顺序队列中的数据元素424 private int front; //指示最近一个已经离开队列的元素所占有的位置 循环顺序队列的对头425 private int rear; //指示最近一个进入队列的元素的位置 循环顺序队列的队尾426 427 public T this[int index]428 {429 get { return data[index]; }430 set { data[index] = value; }431 }432 433 //容量属性434 public int Maxsize435 {436 get { return maxsize; }437 set { maxsize = value; }438 }439 440 //对头指示器属性441 public int Front442 {443 get { return front; }444 set { front = value; }445 }446 447 //队尾指示器属性448 public int Rear449 {450 get { return rear; }451 set { rear = value; }452 }453 454 public CSeqQueue()455 {456 457 }458 459 public CSeqQueue(int size)460 {461 data = http://www.mamicode.com/new T[size];462 maxsize = size;463 front = rear = -1;464 }465 466 //判断循环顺序队列是否为满467 public bool IsFull()468 {469 if ((front == -1 && rear == maxsize - 1) || (rear + 1) % maxsize == front)470 return true;471 else472 return false;473 }474 475 //清空循环顺序列表476 public void Clear()477 {478 front = rear = -1;479 }480 481 //判断循环顺序队列是否为空482 public bool IsEmpty()483 {484 if (front == rear)485 return true;486 else487 return false;488 }489 490 //入队操作491 public void EnQueue(T elem)492 {493 if (IsFull())494 {495 Console.WriteLine("Queue is Full !");496 return;497 }498 rear = (rear + 1) % maxsize;499 data[rear] = elem;500 }501 502 //出队操作503 public T DeQueue()504 {505 if (IsEmpty())506 {507 Console.WriteLine("Queue is Empty !");508 return default(T);509 }510 front = (front + 1) % maxsize;511 return data[front];512 }513 514 //获取对头数据元素515 public T GetFront()516 {517 if (IsEmpty())518 {519 Console.WriteLine("Queue is Empty !");520 return default(T);521 }522 return data[(front + 1) % maxsize];//front从-1开始523 }524 525 //求循环顺序队列的长度526 public int GetLength()527 {528 return (rear - front + maxsize) % maxsize;529 }530 }531 532 533 /// <summary>534 /// 哈夫曼树结点类535 /// </summary>536 public class HNode537 {538 private int weight; //结点权值539 private int lChild; //左孩子结点540 private int rChild; //右孩子结点541 private int parent; //父结点542 543 public int Weight544 {545 get { return weight; }546 set { weight = value; }547 }548 549 public int LChild550 {551 get { return lChild; }552 set { lChild = value; }553 }554 555 public int RChild556 {557 get { return rChild; }558 set { rChild = value; }559 }560 561 public int Parent562 {563 get { return parent; }564 set { parent = value; }565 }566 567 public HNode()568 {569 weight = 0;570 lChild = -1;571 rChild = -1;572 parent = -1;573 }574 }575 class BinaryTree576 {577 578 static void Main(string[] args)579 {580 LinkBinarySearchTree bs = new LinkBinarySearchTree();581 while (true)582 {583 //菜单584 Console.WriteLine("\nMenu");585 Console.WriteLine("1.创建二叉搜索树");586 Console.WriteLine("2.执行中序遍历");587 Console.WriteLine("3.执行先序遍历");588 Console.WriteLine("4.执行后序遍历");589 Console.WriteLine("5.显示搜索一个结点的路径");590 Console.WriteLine("6.exit");591 592 Console.WriteLine("\n输入你的选择(1-5)");593 char ch = Convert.ToChar(Console.ReadLine());594 Console.WriteLine();595 596 switch (ch)597 {598 case ‘1‘:599 {600 int key, offset;601 string flag;602 do603 {604 Console.WriteLine("请输入键：");605 key = Convert.ToInt32(Console.ReadLine());606 Console.WriteLine("请输入位置：");607 offset = Convert.ToInt32(Console.ReadLine());608 indexnode element = new indexnode(key, offset);609 bs.insert(element);610 Console.WriteLine("继续添加新的结点(Y/N)？");611 flag = Console.ReadLine();612 } while (flag == "Y" || flag == "y");613 }614 break;615 case ‘2‘:616 {617 bs.inorderS(bs.Head);618 }619 break;620 case ‘3‘:621 {622 bs.preorderS(bs.Head);623 }624 break;625 case ‘4‘:626 {627 bs.postorderS(bs.Head);628 }629 break;630 case ‘5‘:631 {632 int key;633 Console.WriteLine("请输入键");634 key = Convert.ToInt32(Console.ReadLine());635 bs.find(key);636 }637 break;638 case ‘6‘:639 return;640 default:641 {642 Console.WriteLine("Invalid option");643 break;644 }645 }646 }647 }648 }
C#实现二叉树 二叉链表结构
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。