二叉树排序树

左子树<根节点<右节点

链式存储

节点类

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 二叉排序树 { class BsNode { public BsNode Parents; public BsNode LeftChild; public BsNode RightChild; public int Data { get; set; } public BsNode(int item) { Data = item; } } }

树类

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 二叉排序树 { class BsTree { private BsNode root=null; public void Add(int item) { BsNode newNode = new BsNode(item); if(root==null) { root = newNode; } else { BsNode tempNode = null; tempNode = root; while (true) { if(tempNode.Data<=newNode.Data) { if(tempNode.RightChild==null) { tempNode.RightChild = newNode; newNode.Parents = tempNode; break; } else { tempNode = tempNode.RightChild; } } else { if(tempNode.LeftChild==null) { tempNode.LeftChild = newNode; newNode.Parents = tempNode; break; } else { tempNode = tempNode.LeftChild; } } } } } public void MiddleTravelSal() { MiddleTravelSal(root); } private void MiddleTravelSal(BsNode node) { if(node==null) { return; } MiddleTravelSal(node.LeftChild); Console.Write(node.Data+" "); MiddleTravelSal(node.RightChild); } public bool Find(int index) { return Find(root, index); } public bool Find1(int index) { return Find1(root, index); } private bool Find(BsNode node,int index) { if(node==null) { return false; } if(node.Data==index) { return true; } else { if(Find(node.RightChild, index)) { return true; } if (Find(node.LeftChild, index)) { return true; } //Find(node.RightChild, index); //Find(node.LeftChild, index); } return false; } private bool Find1(BsNode node,int index) { if(node == null) { return false; } if(node.Data==index) { return true; } else { if(index<node.Data) { return Find1(node.LeftChild, index); } else { return Find(node.RightChild, index); } } } public bool Find3(int index) { BsNode tempNode = root; while(true) { if (tempNode == null) { return false; } if (tempNode.Data==index) { return true; } else { if(index<tempNode.Data) { tempNode = tempNode.LeftChild; } else { tempNode = tempNode.RightChild; } } } } public bool Delete(int index) { BsNode tempNode = root; while(true) { if(tempNode==null) { return false; } if(tempNode.Data==index) { Delete(tempNode); return true; } else { if (index < tempNode.Data) { tempNode = tempNode.LeftChild; } else { tempNode = tempNode.RightChild; } } } } private void Delete(BsNode node) { //头节点的话直接把头节点清空 if (node.Parents == null) { root = null; } //如果是叶节点 if (node.RightChild == null&&node.LeftChild==null) { if (node.Parents.LeftChild==node) { node.Parents.LeftChild = null; } if(node.Parents.RightChild==node) { node.Parents.RightChild = null; } return; } //只有左节点或右节点 if(node.RightChild == null && node.LeftChild != null) { node.Data= node.LeftChild.Data; if (node==node.Parents.LeftChild) { node.Parents.LeftChild = node.LeftChild; } else if(node == node.Parents.RightChild) { node.Parents.RightChild = node.LeftChild; } return; } if (node.RightChild != null && node.RightChild == null) { node.Data = node.RightChild.Data; if(node==node.Parents.LeftChild) { node.Parents.LeftChild = node.RightChild; } else if(node ==node.Parents.RightChild) { node.Parents.RightChild = node.RightChild; } return; } //左右节点都有 else { BsNode tempNode = node.RightChild ; while(true) { //找到他最左边的，因为最左边的是最小的 if (tempNode.LeftChild!=null) { tempNode = tempNode.LeftChild; } else { break; } } node.Data = tempNode.Data; // tempNode = null; 得把这个值删除而不是变为空，因为他为空他下边可能还有元素 //删除这个节点是根据他指针，是否有子节点或者是否有父母，而不是根据他的data值所以不必担心他的node节点被删除 Delete(tempNode); } } } } using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 二叉排序树 { class Program { static void Main(string[] args) { BsTree tree = new BsTree(); int[] data = new int[] { 62, 58, 88, 47, 73, 99, 35, 51, 93, 37,48 }; for(int i=0;i<data.Length;i++) { tree.Add(data[i]); } // Console.WriteLine(tree.Find3(100)); Console.WriteLine(tree.Find3(88)); /* tree.MiddleTravelSal(); Console.WriteLine(tree.Delete(47)); tree.MiddleTravelSal();*/ Console.WriteLine(); Console.ReadKey(); } } }