tree.cs

二叉树的创建与打印 二叉树的创建与打印

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

namespace BinaryTree
{
    /// <summary>
    /// 实现基本的数据结构
    /// 提供二叉树的基本操作
    /// 包括构造一个空树,插入,查找,删除
    /// </summary>
    public class BinaryTree
    {
        public TreeNode root;     //根节点
        bool found = false;        //默认查找不存在

        /// <summary>
        /// 构造函数-构造一个空树
        /// </summary>
        public BinaryTree()
        {
            root = null;
        }

        public TreeNode TreeNode
        {
            get
            {
                throw new System.NotImplementedException();
            }
            set
            {
            }
        }

        internal TreeGraph TreeGraph
        {
            get
            {
                throw new System.NotImplementedException();
            }
            set
            {
            }
        }

        /// <summary>
        /// 获得树的高度
        /// </summary>
        /// <returns></returns>
        public int Height()
        {
            if (root == null)
            {
                return 1;
            }

            return Math.Max(Height(root.LeftNode), Height(root.RightNode)) + 1;
        }

        /// <summary>
        /// 删除元素
        /// </summary>
        /// <param name="data">要删除的元素的值</param>
        public void Remove(int data)
        {
            if (root == null)
            {
                return;
            }

            if (!Search(data))
            {
                return;
            }

            if (root.data == data)
            {
                TreeNode tmp = Min(root.RightNode);
                if (tmp == null)
                {
                    root = root.LeftNode;
                }
                else
                {
                    root.data = tmp.data;
                    Remove(root, root.RightNode, 1, tmp.data);
                }
            }
            else if (root.data < data)
            {
                Remove(root, root.RightNode, 1, data);
            }
            else
            {
                Remove(root, root.LeftNode, 0, data);
            }
        }

        /// <summary>
        /// 查找是否存在该元素
        /// </summary>
        /// <param name="data">要查找的元素的值</param>
        /// <returns></returns>
        public bool Search(int data)
        {
            if (root == null)
            {
                return false;
            }

            bool temp = false;
            found = false;
            if (root.data == data)
            {
                temp = true;
            }
            else
            {
                temp = Search(root, data);
            }
            return temp;
        }

        /// <summary>
        /// 插入元素
        /// </summary>
        /// <param name="data">要插入的元素的值</param>
        public void Insert(int data)
        {
            if (Search(data))
            {
                return;
            }

            if (root == null)
            {
                root = new TreeNode();
                root.data = data;
            }
            else
            {
                Insert(root, data);
            }
        }

        /// <summary>
        /// 打印
        /// </summary>
        public void Print()
        {
            if (root == null)
            {
                Console.WriteLine("Empty");
            }
            else
            {
                Print(root);
                Console.WriteLine();
            }
        }

        /// <summary>
        /// 获得树的高度,递归
        /// </summary>
        /// <param name="parent"></param>
        /// <returns></returns>
        private int Height(TreeNode parent)
        {
            if (parent == null)
            {
                return 0;
            }

            return Math.Max(Height(parent.LeftNode), Height(parent.RightNode)) + 1;
        }

        /// <summary>
        /// 获得该节点最小右子女，用于删除元素使用
        /// </summary>
        /// <param name="parent"></param>
        /// <returns></returns>
        private TreeNode Min(TreeNode parent)
        {
            TreeNode temp = parent;
            while (temp != null)
            {
                if (temp.LeftNode == null)
                    return temp;
                else
                    temp = temp.LeftNode;
            }
            return null;
        }

        /// <summary>
        /// 删除元素递归
        /// </summary>
        /// <param name="parent"></param>
        /// <param name="cur"></param>
        /// <param name="direction"></param>
        /// <param name="data"></param>
        private void Remove(TreeNode parent, TreeNode cur, int direction, int data)
        {
            if (cur == null)
            {
                return;
            }

            if (cur.data == data)
            {
                if (cur.LeftNode == null)
                {
                    if (direction == 0)
                        parent.LeftNode = cur.RightNode;
                    else
                        parent.RightNode = cur.RightNode;
                }
                else if (cur.RightNode == null)
                {
                    if (direction == 0)
                        parent.LeftNode = cur.LeftNode;
                    else
                        parent.RightNode = cur.LeftNode;
                }
                else
                {
                    TreeNode tmp = Min(cur.RightNode);
                    cur.data = tmp.data;
                    Remove(cur, cur.RightNode, 1, tmp.data);
                }
            }
            else if (cur.data > data)
            {
                Remove(cur, cur.LeftNode, 0, data);
            }
            else
            {
                Remove(cur, cur.RightNode, 1, data);
            }
        }

        /// <summary>
        /// 查找是否存在该元素，递归
        /// </summary>
        /// <param name="node"></param>
        /// <param name="data"></param>
        /// <returns></returns>
        private bool Search(TreeNode node, int data)
        {
            if (node.data == data)
            {
                found = true;
            }
            else
            {
                if (node.data > data)
                {
                    if (node.LeftNode != null)
                    {
                        Search(node.LeftNode, data);
                    }
                }
                else
                {
                    if (node.RightNode != null)
                    {
                        Search(node.RightNode, data);
                    }
                }
            }
            return found;
        }

        /// <summary>
        /// 插入元素，递归
        /// </summary>
        /// <param name="node"></param>
        /// <param name="data"></param>
        private void Insert(TreeNode node, int data)
        {
            if (node.data > data)
            {
                if (node.LeftNode == null)
                {
                    TreeNode temp = new TreeNode();
                    temp.data = data;
                    node.LeftNode = temp;
                }
                else
                {
                    Insert(node.LeftNode, data);
                }
            }
            else
            {
                if (node.RightNode == null)
                {
                    TreeNode temp = new TreeNode();
                    temp.data = data;
                    node.RightNode = temp;
                }
                else
                {
                    Insert(node.RightNode, data);
                }
            }
        }

        /// <summary>
        /// 打印,递归
        /// </summary>
        /// <param name="node"></param>
        private void Print(TreeNode node)
        {
            if (node == null)
            {
                return;
            }

            Console.Write(node.data);
            Console.Write(" ");
            Print(node.LeftNode);
            Print(node.RightNode);
        }
    }


    /// <summary>
    /// 树类型的节点
    /// </summary>
    public class TreeNode
    {
        public int data;               //节点数据
        public TreeNode LeftNode;      //左子女
        public TreeNode RightNode;     //右子女
        /// 
        /// 构造函数，初始化左右子女为空
        /// 
        public TreeNode()
        {
            LeftNode = RightNode = null;
        }
    }

}