注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天涯倦客的博客

祝福你朋友永远快乐!

 
 
 

日志

 
 

二叉树的实现  

2013-09-12 17:00:10|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 [STAThread]
        static void Main()
        {
           
            #region

            int index = 1;
            TreeNode head = new TreeNode { NodeVale = index.ToString(), AddDate = DateTime.Now.ToString() };
            BiTree<TreeNode> bt = new BiTree<TreeNode>(head);

            index++;
            TreeNode node = new TreeNode() { NodeVale = index.ToString(), AddDate = DateTime.Now.ToString() };
            bt.InsertL(node, bt.Head);

            index++;
            node = new TreeNode() { NodeVale = index.ToString(), AddDate = DateTime.Now.ToString() };
            bt.InsertR(node, bt.Head);

            Node<TreeNode> lnode = bt.Head.LChild;
            index++;
            node = new TreeNode() { NodeVale = index.ToString(), AddDate = DateTime.Now.ToString() };
            bt.InsertR(node, lnode);


            Node<TreeNode> rnode = bt.Head.RChild;
            index++;
            node = new TreeNode() { NodeVale = index.ToString(), AddDate = DateTime.Now.ToString() };
            bt.InsertR(node, rnode);

            List<TreeNode> list=bt.InOrder2(bt.Head);
            Console.WriteLine("InOrder2 begin----------------------");
            foreach (var treeNode in list)
            {
                Console.WriteLine(treeNode.NodeVale+"--"+treeNode.AddDate);
            }
            Console.WriteLine("InOrder2 end----------------------");


            list = bt.LevelOrder2(bt.Head);
            Console.WriteLine("LevelOrder2 begin----------------------");
            foreach (var treeNode in list)
            {
                Console.WriteLine(treeNode.NodeVale + "--" + treeNode.AddDate);
            }
            
            Console.WriteLine("LevelOrder2 end----------------------");
        }

 public class Node<T>
        {
            private T data;
            private Node<T> _lChild;
            private Node<T> _rChild;

            //构造器
            public Node(T val, Node<T> lp, Node<T> rp)
            {
                data = val;
                _lChild = lp;
                _lChild = rp;
            }
            //构造器
            public Node(Node<T> lp, Node<T> rp)
            {
                data = default(T);
                _lChild = lp;
                _rChild = rp;
            }

            //构造器
            public Node(T val)
            {
                data = val;
                _lChild = null;
                _rChild = null;
            }
            //构造器
            public Node()
            {
                data = default(T);
                _lChild = null;
                _rChild = null;
            }
            //数据属性
            public T Data
            {
                get
                {
                    return data;
                }
                set
                {
                    value = data;
                }
            }
            //左孩子属性
            public Node<T> LChild
            {
                get
                {
                    return _lChild;
                }
                set
                {
                    _lChild = value;
                }
            }
            //右孩子属性
            public Node<T> RChild
            {
                get
                {
                    return _rChild;
                }
                set
                {
                    _rChild = value;
                }
            }

        }

        public  struct TreeNode
        {
          public String NodeVale { get; set; }
          public String AddDate { get; set; }
        }

        public class BiTree<T>
        {
            private Node<T> head; //头引用
            //头引用属性
            public Node<T> Head
            {
                get
                {
                    return head;
                }
                set
                {
                    head = value;
                }
            }
            //构造器
            public BiTree()
            {
                head = null;
            }
            //构造器
            public BiTree(T val)
            {
                Node<T> p = new Node<T>(val);
                head = p;

            }
            //构造器
            public BiTree(T val, Node<T> lp, Node<T> rp)
            {
                Node<T> p = new Node<T>(val, lp, rp);
                head = p;
            }
            //判断是否是空二叉树
            public bool IsEmpty()
            {
                if (head == null)
                {
                    return true;
                }
                return false;
            }

            //获取根结点
            public Node<T> Root()
            {
                return head;
            }
            //获取结点的左孩子结点
            public Node<T> GetLChild(Node<T> p)
            {
                return p.LChild;
            }
            //获取结点的右孩子结点
            public Node<T> GetRChild(Node<T> p)
            {
                return p.RChild;
            }
            //将结点p的左子树插入值为val的新结点,
            //原来的左子树成为新结点的左子树
            public void InsertL(T val, Node<T> p)
            {

                Node<T> tmp = new Node<T>(val);
                tmp.LChild = p.LChild;
                p.LChild = tmp;
            }
            //将结点p的右子树插入值为val的新结点,
            //原来的右子树成为新结点的右子树
            public void InsertR(T val, Node<T> p)
            {
                Node<T> tmp = new Node<T>(val);
                tmp.RChild = p.RChild;
                p.RChild = tmp;
            }
            //若p非空,删除p的左子树
            public Node<T> DeleteL(Node<T> p)
            {
                if ((p == null) || (p.LChild == null))
                {
                    return null;
                }
                Node<T> tmp = p.LChild;
                p.LChild = null;
                return tmp;
            }
            //若p非空,删除p的右子树
            public Node<T> DeleteR(Node<T> p)
            {
                if ((p == null) || (p.RChild == null))
                {
                    return null;
                }
                Node<T> tmp = p.RChild;
                p.RChild = null;
                return tmp;
            }
            //判断是否是叶子结点
            public bool IsLeaf(Node<T> p)
            {
                if ((p != null) && (p.LChild == null) && (p.RChild == null))
                {
                    return true;
                }
                return false;
            }


            public void PreOrder(Node<T> root)
            {
                //根结点为空
                if (root == null)
                {
                    return;
                }
                //处理根结点
                Console.WriteLine("{0}", root.Data);
                //先序遍历左子树
                PreOrder(root.LChild);
                //先序遍历右子树
                PreOrder(root.RChild);
            }

            public void InOrder(Node<T> root)
            {
                //根结点为空
                if (root == null)
                {
                    return;
                }
                //中序遍历左子树
                InOrder(root.LChild);
                //处理根结点
                Console.WriteLine("{0}", root.Data);
                //中序遍历右子树
                InOrder(root.RChild);
            }

            List<T> list = new List<T>();
            public List<T> InOrder2(Node<T> root)
            {
               
                //根结点为空
                if (root == null)
                {
                    return list;
                }
                //中序遍历左子树
                InOrder2(root.LChild);
                //处理根结点
                list.Add(root.Data);
                //Console.WriteLine("{0}", root.Data);
                //中序遍历右子树
                InOrder2(root.RChild);

                return list;
            }

            public void PostOrder(Node<T> root)
            {
                //根结点为空
                if (root == null)
                {
                    return;
                }
                //后序遍历左子树
                PostOrder(root.LChild);
                //后序遍历右子树
                PostOrder(root.RChild);
                //处理根结点
                Console.WriteLine("{0}", root.Data);
            }


            public void LevelOrder(Node<T> root)
            {
                //根结点为空
                if (root == null)
                {
                    return;
                }
                //设置一个队列保存层序遍历的结点
                Queue<Node<T>> sq = new Queue<Node<T>>();
                //根结点入队
                sq.Enqueue(root);
                //队列非空,结点没有处理完
                while (sq.Count>0)
                {
                    //结点出队
                    Node<T> tmp = sq.Dequeue();
                    //处理当前结点
                    Console.WriteLine("{0}", tmp.Data);
                    //将当前结点的左孩子结点入队
                    if (tmp.LChild != null)
                    {
                        sq.Enqueue(tmp.LChild);
                    }
                    if (tmp.RChild != null)
                    {
                        sq.Enqueue(tmp.RChild);
                    }
                }
            }

            public List<T> LevelOrder2(Node<T> root)
            {
                list.Clear();
                //根结点为空
                if (root == null)
                {
                    return null;
                }
                //设置一个队列保存层序遍历的结点
                Queue<Node<T>> sq = new Queue<Node<T>>();
                //根结点入队
                sq.Enqueue(root);
                //队列非空,结点没有处理完
                while (sq.Count > 0)
                {
                    //结点出队
                    Node<T> tmp = sq.Dequeue();
                    //处理当前结点
                    list.Add(tmp.Data);
                   /// Console.WriteLine("{0}", tmp.Data);
                    //将当前结点的左孩子结点入队
                    if (tmp.LChild != null)
                    {
                        sq.Enqueue(tmp.LChild);
                    }
                    if (tmp.RChild != null)
                    {
                        sq.Enqueue(tmp.RChild);
                    }
                }
                return list;
            }


            //编写算法,在二叉树中查找值为value的结点
            public Node<T> Search(Node<T> root, T value)
            {
                Node<T> p = root;

                if (p == null)
                {
                    return null;
                }

                if (!p.Data.Equals(value))
                {
                    return p;
                }

                if (p.LChild != null)
                {
                    return Search(p.LChild, value);
                }

                if (p.RChild != null)
                {
                    return Search(p.RChild, value);
                }

                return null;
            }

            //统计出二叉树中叶子结点的数目
            public int CountLeafNode(Node<T> root)
            {
                if (root == null)
                {
                    return 0;
                }
                else
                    if (root.RChild == null && root.RChild == null)
                    {
                        return 1;
                    }
                    else
                    {
                        return (CountLeafNode(root.LChild) + CountLeafNode(root.RChild));
                    }
            }

            //编写算法,求二叉树的深度
            public int GetHeight(Node<T> root)
            {
                int lh;
                int rh;

                if (root == null)
                {
                    return 0;
                }
                else
                    if (root.LChild == null && root.RChild == null)
                    {
                        return 1;
                    }
                    else
                    {
                        lh = GetHeight(root.RChild);
                        rh = GetHeight(root.RChild);
                        return (lh > rh ? lh : rh) + 1;
                    }
            }

        }
  评论这张
 
阅读(446)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017