学习笔记二叉树排序，面试经常考的题目

二叉树代码

using System;

namespace System.MySortNS
{
    //表示二叉树，所有树节点根据严格的二叉规则聚合得到的集合
    public sealed class BinaryTree
    {
        //二叉树节点
        sealed class TreeNode
        {
            private int _nodevalue;//节点值
            private TreeNode _leftnode;//左子节点
            private TreeNode _rightnode;//右子节点

            public TreeNode(int nodevalue)
            {
                this._nodevalue = nodevalue;
                this._leftnode = null;
                this._rightnode = null;
            }
            public int NodeValue
            {
                get
                {
                    return this._nodevalue;
                }
            }
            public TreeNode LeftNode
            {
                get
                {
                    return this._leftnode;
                }
                set
                {
                    if (value != null)
                    {
                        if (this.LeftNode == null)
                        {
                            this._leftnode = value;
                        }
                        else
                        {
                            //nothing to do here!
                        }
                    }
                    else
                    {
                        //nothing to do here!
                    }
                }
            }
            public TreeNode RightNode
            {
                get
                {
                    return this._rightnode;
                }
                set
                {
                    if (value != null)
                    {
                        if (this.RightNode == null)
                        {
                            this._rightnode = value;
                        }
                        else
                        {
                            //nothing to do here!
                        }
                    }
                    else
                    {
                        //nothing to do here!
                    }
                }
            }
        }

        private TreeNode _rootnode;//根节点

        public BinaryTree()
        {
            this._rootnode = null;
        }

        public void AddNumber(int num)
        {
            if (this._rootnode == null)//尚未有根节点时，新节点自然占据根节点的地位
            {
                this._rootnode = new TreeNode(num);
            }
            else
            {
                TreeNode newnode = new TreeNode(num);
                TreeNode currentnode = this._rootnode;
                this.addTreeNode(newnode, currentnode);
            }
        }
        //递归方法，在已存在的树中寻找新节点的合理位置并添加
        //需要了解的数据：待添加节点，当前操作到的节点
        //添加规则：与当前节点比较，小向左，大向右，先来着为大
        private void addTreeNode(TreeNode node,TreeNode currentnode)
        {
            if (node.NodeValue <= currentnode.NodeValue)//后来者为小，向左走
            {
                if (currentnode.LeftNode == null)
                {
                    currentnode.LeftNode = node;
                    //done!
                }
                else//转换比较场地，继续递归比较
                {
                    this.addTreeNode(node,currentnode.LeftNode);
                }
            }
            else//后来者大了，向右走
            {
                if (currentnode.RightNode == null)
                {
                    currentnode.RightNode = node;
                    //done!
                }
                else//转换比较场地，继续递归比较
                {
                    this.addTreeNode(node, currentnode.RightNode);
                }
            }
        }

        //使用中序遍历，获取已添加的二叉树之有序节点值结果
        public System.Collections.Generic.List<int> GetSortedList()
        {
            System.Collections.Generic.List<int> list;
            list = new System.Collections.Generic.List<int>();
            //递归进行中序遍历，获取有序数据，填充到已定义的动态数组中
            TreeNode currentnode = this._rootnode;
            this.fillNumber(currentnode, list);

            return list;
        }
        //递归中序遍历填充方法
        private void fillNumber(TreeNode currentnode, System.Collections.Generic.List<int> list)
        {
            if (currentnode != null)
            {
                //递归遍历左分支
                this.fillNumber(currentnode.LeftNode, list);
                //访问并填充当前节点值
                list.Add(currentnode.NodeValue);
                //递归遍历右分支
                this.fillNumber(currentnode.RightNode, list);
            }
            else//下级节点为空，不予继续处理本次分支
            {
                //nothing to do here!
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            string input = null;
            Console.WriteLine("请逐次输入希望参与排序的整数，输入EXIT则结束！");
            int num = 0;

            BinaryTree tree = new BinaryTree();
            while (true)
            {
                Console.Write("请输入整数：");
                input = Console.ReadLine();
                if (input.Trim().ToUpper() == "EXIT")
                {
                    Console.WriteLine("添加结束！");
                    break;
                }
                else
                {
                    //nothing to do here!
                }
                num = Int32.Parse(input);
                tree.AddNumber(num);
            }
            Console.WriteLine("如想要看到排序后的列表，请回车！");
            Console.ReadLine();
            Console.Write("\n---------------------------\n");
            System.Collections.Generic.List<int> result = tree.GetSortedList();
            foreach (int n in result)
            {
                Console.Write(n.ToString());
                Console.Write("\t");
            }
            Console.Write("\n---------------------------\n");
        }
    }
}