C# 创建以及操作二叉树

这是我用C#编写的关于二叉树的一个类，它是一个Windows程序的一部分（用于图形化显示一棵二叉树，并能插入、寻找、删除任意节点，最后还可以将一棵非平衡的二叉树平衡化）。

    下面仅对其中的两个函数做下说明：   
    private void Insert(TreeNode root, int num)    //用一般的要求建立一棵二叉树
    private TreeNode AVLTreeInsertNode(int num, ref TreeNode root)    //按照动态平衡的要求建立一棵二叉树


using System.Drawing; 
using System.Collections; 
 
namespace nsBinaryTree 
{ 
    // 定义树节点类 
    public class TreeNode 
    { 
        private int data;    // 节点数据 
        public TreeNode left_child;     // 左子女 
        public TreeNode right_child;    // 右子女 
        public TreeNode parent;        // 父节点 
 
        // 节点在树中的高度，平衡处理时，用节点在树中的高度代替平衡因子 
        public int Height; 
         
        // data访问器 
        public int Data 
        { 
            get 
            { 
                return data; 
            } 
            set 
            { 
                data = value; 
            } 
        } 
 
        // 左子女访问器 
        public TreeNode LeftChild 
        { 
            get 
            { 
                return left_child; 
            } 
            set 
            { 
                left_child = value; 
            } 
        } 
 
        // 右子女访问器 
        public TreeNode RightChild 
        { 
            get 
            { 
                return right_child; 
            } 
            set 
            { 
                right_child = value; 
            } 
        } 
 
        // 父节点访问器 
        public TreeNode Parent 
        { 
            get 
            { 
                return parent; 
            } 
            set 
            { 
                parent = value; 
            } 
        }      
 
        // 构造函数，初始化左右子女为空 
        public TreeNode() 
        { 
            data = 0; 
            left_child = null; 
            right_child = null;
         parent = null; 
        } 
    } 
 
    // 定义二叉树类 
    public class BinaryTree 
    { 
        public TreeNode root;    //根节点 
 
        // 根节点的访问器 
        public TreeNode Root 
        { 
            get 
            { 
                return root; 
            } 
            set 
            { 
                root = value; 
            } 
        } 
 
        // 构造函数 
        public BinaryTree() 
        { 
            root = null; 
        } 
 
        // 判断树是否为空 
        public bool IsNullOrEmpty() 
        { 
            if (root == null) 
            { 
                return true; 
            } 
            else 
            { 
                return false; 
            } 
        }         
 
        // Insert a node to the tree. 
        public void Insert(int num) 
        { 
            if (root == null) 
            { 
                root = new TreeNode(); 
                root.Data = num; 
                root.parent = null; 
            } 
            else 
            { 
                Insert(root, num); 
            } 
        } 
 
        // 插入元素，重载函数 
        private void Insert(TreeNode root, int num) 
        { 
            if (num == root.Data) 
            { 
                return; 
            } 
            else if (num < root.Data) 
            { 
                if (root.LeftChild == null) 
                { 
                    TreeNode temp_node = new TreeNode(); 
                    temp_node.Data = num; 
                    temp_node.Parent = root; 
 
                    root.LeftChild = temp_node; 
                } 
                else 
                { 
                    Insert(root.LeftChild, num); 
                } 
            } 
            else 
            { 
                if (root.RightChild == null) 
                { 
                    TreeNode temp_node = new TreeNode(); 
                    temp_node.Data = num; 
                    temp_node.Parent = root; 
 
                    root.RightChild = temp_node; 
                } 
                else 
                { 
                    Insert(root.RightChild, num); 
                } 
            } 
        } 
 
        // 查找是否存在某一个数值，如果存在，返回该节点，否则返回null 
        public TreeNode Search(int num) 
        { 
            TreeNode searched_node = new TreeNode(); 
            searched_node = Search(root, num); 
            return searched_node; 
        } 
 
        // 查找是否存在该元素，重载函数 
        private TreeNode Search(TreeNode root, int num) 
        { 
            TreeNode searched_node = new TreeNode(); 
 
            if (root.Data == num) 
            { 
                searched_node = root; 
            } 
            else 
            { 
                if (num < root.Data) 
                { 
                    if (root.LeftChild != null) 
                    { 
                        searched_node = Search(root.LeftChild, num); 
                    } 
                } 
                else 
                { 
                    if (root.RightChild != null) 
                    { 
                        searched_node = Search(root.RightChild, num); 
                    } 
                } 
            } 
 
            return searched_node; 
        } 
 
        // 遍历二叉树，从而设置其所有节点的Brush属性为默认值 
        public void SetTreeNodeBrush() 
        { 
            SetTreeNodeBrush(root); 
        } 
 
        // 前序遍历，重载函数 
        private void SetTreeNodeBrush(TreeNode root) 
        { 
            if (root != null) 
            { 
                // TODO: 添加遍历要做的事，比如我希望在PictureBox中绘制节点，那么可以在这里设置节点的画刷属性:
               //root.Brush = new SolidBrush(Color.Turquoise);    //重新设置节点的画刷 
 
                if (root.LeftChild != null) 
                { 
                    SetTreeNodeBrush(root.LeftChild); 
                } 
                 
                if (root.RightChild != null) 
                { 
                    SetTreeNodeBrush(root.RightChild); 
                }             
            } 
        } 
 
        // 获得该节点最小右子女（另一种方法是取它的最大左子女），用于删除节点 
        TreeNode MinRightChild(TreeNode parent) 
        { 
            TreeNode temp = parent; 
            while (temp != null) 
            { 
                if (temp.LeftChild == null) 
                { 
                    return temp; 
                } 
                else 
                { 
                    temp = temp.LeftChild;  
                } 
            } 
 
            return null; 
        } 
          
        // 删除节点 
        public void DeleteNode(int num) 
        { 
            if (root == null) 
            { 
                return; 
            }  
            else if(root.Data == num) 
            { 
                TreeNode tmp = MinRightChild(root.RightChild); 
                if(tmp == null) 
                { 
                    root = root.LeftChild; 
                } 
                else 
                { 
                    root.Data = tmp.Data; 
                    DeleteNode(root, root.RightChild, 1, tmp.Data); 
                } 
            } 
            else if (root.Data < num) 
            { 
                DeleteNode(root, root.RightChild, 1, num); 
            } 
            else 
            { 
                DeleteNode(root, root.LeftChild, 0, num); 
            }      
        } 
 
        // 删除节点，重载函数 
        private void DeleteNode(TreeNode parent, TreeNode cur, int direction, int num) 
        { 
            if (cur.Data == num) 
            { 
                if (cur.LeftChild == null) 
                { 
                    if (direction == 0) 
                    { 
                        parent.LeftChild = cur.RightChild; 
                    } 
                    else 
                    { 
                        parent.RightChild = cur.RightChild; 
                    } 
                } 
                else if (cur.RightChild == null) 
                { 
                    if (direction == 0) 
                    { 
                        parent.LeftChild = cur.LeftChild; 
                    } 
                    else 
                    { 
                        parent.RightChild = cur.LeftChild; 
                    } 
                } 
                else 
                { 
                    TreeNode tmp = MinRightChild(cur.RightChild); 
                    cur.Data = tmp.Data; 
                    DeleteNode(cur, cur.RightChild, 1, tmp.Data); 
                } 
            } 
            else if (cur.Data > num) 
            { 
                DeleteNode(cur, cur.LeftChild, 0, num); 
            } 
            else 
            { 
                DeleteNode(cur, cur.RightChild, 1, num); 
            } 
        } 
 
        // 求树的深度 
        private int TreeHeight(TreeNode root) 
        { 
            if (root == null) 
            { 
                return 0; 
            } 
            else 
            { 
                int left_depth = TreeHeight(root.left_child); 
                int right_depth = TreeHeight(root.right_child); 
 
                if (left_depth > right_depth) 
                { 
                    return left_depth + 1; 
                } 
                else 
                { 
                    return right_depth + 1; 
                } 
            } 
        } 
 
        // 判断一棵树是否为平衡二叉树 
        public bool IsBalance() 
        { 
            return IsBalance(root); 
        } 
 
        //  判断一棵树是否为平衡二叉树，重载函数 
        private bool IsBalance(TreeNode root) 
        { 
            if (root == null) 
            { 
                return true; 
            } 
 
            int dis = TreeHeight(root.left_child) - TreeHeight(root.right_child); 
 
            if (dis > 1 || dis < -1) 
            { 
                return false; 
            } 
            else 
            { 
                return IsBalance(root.left_child) && IsBalance(root.right_child); 
            } 
        } 
 
        // 平衡二叉树 
        public void Balance() 
        { 
            Balance(ref root); 
        } 
 
        // 平衡二叉树，重载函数 
        // 大体过程：先将树的所有节点Data值存入到一个数组中，然后再按照平衡二叉树的要求逐个插入Data，从而得到平衡二叉树 
        private void Balance(ref TreeNode root) 
        { 
            if (this.IsBalance() == true)    // 判断树是否已经平衡 
            { 
                return; 
            } 
            else 
            { 
                ArrayList array_list = new ArrayList(); 
                SaveTreeNode(root, array_list);    //将树内所有结点的Data值存入到一个ArrayList中 
          
                BinaryTree btree = new BinaryTree(); 
                for (int i = 0; i < array_list.Count; i++) 
                { 
                    root = AVLTreeInsertNode((int)array_list[i], ref btree.root); 
                } 
            } 
        } 
 
        // 通过前序遍历的方式，将树内所有结点的Data值存入到一个ArrayList中，为建立平衡二叉树做准备 
        private void SaveTreeNode(TreeNode root, ArrayList array_list) 
        { 
            if (root != null) 
            { 
                array_list.Add(root.Data); 
 
                if (root.left_child != null) 
                { 
                    SaveTreeNode(root.left_child, array_list); 
                } 
 
                if (root.right_child != null) 
                { 
                    SaveTreeNode(root.right_child, array_list); 
                } 
            } 
        } 
         
        // 按平衡二叉树的要求插入节点 
        private TreeNode AVLTreeInsertNode(int num, ref TreeNode root) 
        { 
            if (root == null) 
            { 
                root = new TreeNode(); 
                root.Data = num; 
                root.Height = 0; 
                root.left_child = root.right_child = null; 
            } 
            else if (num < root.Data)    // 插入到左子树中 
            { 
                root.left_child = AVLTreeInsertNode(num, ref root.left_child); 
                if (TreeHeight(root.left_child) - TreeHeight(root.right_child) == 2)    // AVL树不平衡 
                { 
                    if (num < root.left_child.Data) 
                    { 
                        root = SingleRotateWithLeft(root);    // 插入到了左子树左边, 做单旋转 
                    } 
                    else 
                    { 
                        root = DoubleRotateWithLeft(root);    // 插入到了左子树右边, 做双旋转 
                    } 
                } 
            } 
            else if (num > root.Data)    // 插入到右子树中 
            { 
                root.right_child = AVLTreeInsertNode(num, ref root.right_child); 
                if (TreeHeight(root.right_child) - TreeHeight(root.left_child) == 2)    // AVL树不平衡 
                { 
                    if (num > root.right_child.Data) 
                    { 
                        root = SingleRotateWithRight(root);    // 插入到了右子树右边, 做单旋转 
                    } 
                    else 
                    { 
                        root = DoubleRotateWithRight(root);    // 插入到了右子树左边, 做双旋转 
                    } 
                } 
            } 
 
            root.Height = Max(TreeHeight(root.left_child), TreeHeight(root.right_child)) + 1; 
 
            return root; 
        } 
 
        // 左单旋转 
        private TreeNode SingleRotateWithLeft(TreeNode root) 
        { 
            TreeNode node = new TreeNode(); 
 
            node = root.left_child; 
            root.left_child = node.right_child; 
            node.right_child = root; 
 
            // 结点的位置改变了, 更新其高度值 
            root.Height = Max(TreeHeight(root.left_child), TreeHeight(root.right_child)) + 1; 
            node.Height = Max(TreeHeight(node.left_child), root.Height) + 1; 
 
            return node; 
        } 
 
        // 右单旋转 
        private TreeNode SingleRotateWithRight(TreeNode root) 
        { 
            TreeNode node = new TreeNode(); 
 
            node = root.right_child; 
            root.right_child = node.left_child; 
            node.left_child = root; 
 
            // 结点的位置改变了, 更新其高度值 
            root.Height = Max(TreeHeight(root.left_child), TreeHeight(root.right_child)) + 1; 
            node.Height = Max(TreeHeight(node.right_child), root.Height) + 1; 
 
            return node; 
        } 
 
        // 先左后右双旋转 
        private TreeNode DoubleRotateWithLeft(TreeNode root) 
        { 
            root.left_child = SingleRotateWithRight(root.left_child); 
            return SingleRotateWithLeft( root); 
        } 
 
        // 先右后左双旋转 
        private TreeNode DoubleRotateWithRight(TreeNode root) 
        { 
            root.right_child = SingleRotateWithLeft(root.right_child); 
            return SingleRotateWithRight(root); 
        } 
 
        // 求两个整数中较大的数 
        private int Max(int a, int b) 
        { 
            return a > b ? a : b; 
        } 
 
        // 删除树 
        public void DeleteTree() 
        { 
            DeleteTree(ref root); 
        } 
 
        // 删除树，重载函数 
        private void DeleteTree(ref TreeNode root) 
        { 
            if (root != null) 
            { 
                if (root.LeftChild != null) 
                { 
                    DeleteTree(ref root.left_child); 
                } 
                if (root.RightChild != null) 
                { 
                    DeleteTree(ref root.right_child); 
                } 
 
                if (root.LeftChild != null && root.Parent != null) 
                { 
                    root.Parent.left_child = null; 
                } 
 
                if (root.RightChild != null && root.Parent != null) 
                { 
                    root.Parent.right_child = null; 
                }  
                 
                root = null;  
            }           
        } 
    } 
}

C# 创建以及操作二叉树,布布扣,bubuko.com

C# 创建以及操作二叉树

原文：http://www.cnblogs.com/hongwei8455/p/3658574.html