binarysorttree.cs

数据结构排序部分的二叉树排序

using System;
using System.Collections.Generic;
using System.Collections ;
using System.Text;

namespace binarytreesort
{
    public  class binarysorttree 
    {
        private binarysorttreenode root = new binarysorttreenode();  
      //*******************create a binary tree with the specified datas
        public  binarysorttree(int[] datas)
        {
            int i=0;
            int n=datas .Length ;
            root = null;         
            while (i < datas.Length)
            {
                insert(ref root, datas[i]);
                i++;
            }
        }
      //**********************insert a node to the binarysorttree
        public void insert(ref binarysorttreenode  root, int data)
        {
            binarysorttreenode p = null, s = null, f = null;
            if (search(root, data, ref p,ref f) == -1)
            {
                s = new binarysorttreenode ();
                s.LCHILD = null;
                s.RCHILD = null;
                s.DATA = data;
                if (p == null){  root = s;}    
                else
                {
                    if (p.DATA > data){ p.RCHILD =s;}
                    if (p.DATA < data){ p.LCHILD =s;}
                }
            }
            else
            { 
            }  
        }
      //**********************delete data  from the binarysorttree

        public void delete(ref binarysorttreenode  root, int data)
        {
            binarysorttreenode  p = new binarysorttreenode ();
            binarysorttreenode  f= new binarysorttreenode ();
            p=null;f=null;
          

            if (search(root, data, ref p, ref f) == 1)
            {
                if (p.LCHILD!=null)
                {
                    if (p.RCHILD!=null)
                    {
                        binarysorttreenode  newnote = new binarysorttreenode ();
                        binarysorttreenode  father = new binarysorttreenode ();
                        newnote = p.LCHILD;
                        father=p;
                        while (newnote.RCHILD!=null)
                        {
                            father = newnote;
                            newnote = newnote.RCHILD;
                        }
                        p.DATA = newnote.DATA;
                        father.RCHILD = newnote.LCHILD;
                    }
                    else
                    {
                        if (f == null)
                        {
                            root = p.LCHILD;
                        }
                        else
                        {
                            if (p == f.LCHILD) { f.LCHILD = p.LCHILD; }
                            if (p == f.RCHILD) { f.RCHILD = p.LCHILD; }
                        }
                    }
                }
                else
                {                 
                        if (f == null) { root = p.RCHILD; }
                        else
                        {
                            if (p == f.LCHILD) { f.LCHILD = p.RCHILD; }
                            if (p == f.RCHILD) { f.RCHILD = p.RCHILD; }
                        }
                }
            }
            else
            {
                
            }
        }
      //***********************search data in the binarysorttree,if it is found then return 1 
      //********************if it is not found or the tree is null then return -1
        public int search(binarysorttreenode  root, int data, ref binarysorttreenode  p, ref binarysorttreenode  father)
        {
            binarysorttreenode  q = new binarysorttreenode ();
            q = root;
            p = null;
            father = null;
            while (q!=null)
            {   
                if (q.DATA == data)
                {
                    p = q;
                    return 1;
                }
                else
                {
                    father = q;
                    if (q.DATA < data)
                    {
                        p = q;
                        q = q.LCHILD;
                    }
                    else
                    {
                        p = q;
                        q = q.RCHILD;
                    }
                }
            }
            return -1;
        }
     //**************************traverse the binarysorttree inorderly and output the data 
        public void inordertraverse(ref binarysorttreenode root, ref ArrayList array)
        {
            stacknode STACKS = new stacknode();
            binarysorttreenode p = new binarysorttreenode();
            p = root;


            while (p != null || STACKS.DATA != default(binarysorttreenode))
            {
                stacknode tmp = new stacknode();
               
                if (p != null)
                {
                    tmp.DATA  =p;                  
                    tmp.NEXTNODE = STACKS;
                    STACKS = tmp;
                    p = p.LCHILD;
                }
                else
                { 
                    tmp = STACKS;
                    array.Add(tmp.DATA.DATA );
                    STACKS = STACKS.NEXTNODE;
                    p =tmp.DATA.RCHILD;
                }
            }
        }
        #region-----
        public binarysorttreenode ROOT
        {
            get { return  this.root; }
            set { this.root = value; }
        }
        #endregion----
    }
    public class binarysorttreenode
    {
        private int data;
        private binarysorttreenode  lchild;
        private binarysorttreenode  rchild;

        public binarysorttreenode()
        {
           
        }
        public binarysorttreenode(int newdata)
        {
            this.data=newdata;
            this.lchild =null;
            this.rchild =null;
        }
       #region---------attributes
        public int DATA
        {
            get { return this.data ;}
            set { this.data = value; }
        }
        public binarysorttreenode  LCHILD
        {
            get {return this.lchild ;}
            set {this.lchild = value;}         
        }
        public binarysorttreenode  RCHILD
        {
            get {return this.rchild ;}          
            set {this.rchild = value;}
        }
       #endregion------attributes
    }
    public class stacknode
    {
        private binarysorttreenode data;
        private stacknode nextnode;

        public stacknode()
        {
            this.data = default(binarysorttreenode);
            this.nextnode = null;
        }
        public stacknode(binarysorttreenode newdata)
        {
            this.data = newdata;
            this.nextnode = null;
        }
        public binarysorttreenode DATA
        {
            get { return this.data; }
            set { this.data = value; }
        }
        public stacknode NEXTNODE
        {
            get { return this.nextnode; }
            set { this.nextnode = value; }
        }
    }
}