Xây dựng cấu trúc dữ liệu của cây nhị phân tìm kiếm trong lập trình C#

**thanhtungbooking** · 30-05-2007, 04:58 PM

Mã:

namespace BSTStructure{    public class BSTree    {        public int data;        public BSTree left;        public BSTree right;        public BSTree(int key)        {            data = key;            left = right = null;        }        public BSTree Left        {            get            {                return left;            }            set            {                left = value;            }        }        public BSTree Right        {            get            {                return right;            }            set            {                right = value;            }        }        public int Data        {            get            {                return data;            }            set            {                data = value;            }        }        public void Insert(int key)        {            if (key < data)            {                if (left == null) left = new BSTree(key);                else left.Insert(key);            }            if (key > data)            {                if (right==null) right= new BSTree(key);                else right.Insert(key);            }        }    }     public class Tree    {        public BSTree root;        public Tree()        {            root = null;        }        public void InsertNode(int key)        {            if (root == null)                root = new BSTree(key);            else root.Insert(key);        }        public void PreorderTraverse(BSTree node)        {            if (node == null) return;            Console.Write(node.data + " ");            PreorderTraverse(node.left);            PreorderTraverse(node.right);        }        public void InorderTraverse(BSTree node)        {            if (node == null) return;            InorderTraverse(node.left);            Console.Write(node.data + " ");            InorderTraverse(node.right);        }        public void PostorderTraverse(BSTree node)        {            if (node == null) return;            PostorderTraverse(node.left);            PostorderTraverse(node.right);            Console.Write(node.data + " ");        }        public bool Search(BSTree node, int key)        {            if (node == null) return false;            if (node.data == key) return true;            if (node.data > key)                return Search(node.left, key);            else if (node.data < key)                return Search(node.right, key);            else return false;        }    }}

Một ví dụ minh họa:

Mã:

using System;using System.Collections.Generic;using System.Text;using BSTStructure;namespace ConsoleApplication1{    class Program    {        static void Main(string[] args)        {            Tree tree = new Tree();            int key;            Console.WriteLine("Cac gia tri duoc them vao cay:");            Random random = new Random();            for (int i = 1; i <= 10; i++)            {                key = random.Next(100);                Console.Write(key + " ");                tree.InsertNode(key);            }            Console.WriteLine("

Duyet tien tu:");            tree.PreorderTraverse(tree.root);            Console.WriteLine("

Duyet trung tu:");            tree.InorderTraverse(tree.root);            Console.WriteLine("

Duyet hau tu:");            tree.PostorderTraverse(tree.root);            Console.Write("

Nhap khoa can tim kiem:");            int keysearch = int.Parse(Console.ReadLine());            bool result = tree.Search(tree.root, keysearch);            if (result) Console.WriteLine("Tim thay {0} trong cay nhi phan tim kiem",keysearch);            else Console.WriteLine("Khong tim thay {0} trong cay nhi phan tim kiem",keysearch);        }    }}