学步园

二叉树以及其节点的实现

1. 二叉树节点的定义及实现
根据二叉树的特点可知,二叉树的子节点最多有两个子树,分别是左子树和右子树。所以，一个二叉树的节点应有三个部分组成：

² 当前节点数据<T>；

² 左子节点的引用；

² 右子节点的引用。

 

如下图左部分的Node类定义。

 

Node类的实现：

/// <summary>
    /// 二叉树节点代码
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class Node<T>
    {
        private T _data;
        private Node<T> _lChild;
        private Node<T> _rChild;

        /// <summary>
        /// 二叉树当前节点的数据
        /// </summary>
        public T Data
        {
            get { return _data; }
            set { _data = value; }
        }

        /// <summary>
        /// 二叉树左子节点的引用
        /// </summary>
        public Node<T> LChild
        {
            get { return _lChild; }
            set { _lChild = value; }
        }

        /// <summary>
        /// 二叉树右子节点的引用
        /// </summary>
        public Node<T> RChild
        {
            get { return _rChild; }
            set { _rChild = value; }
        }

        public Node()
        {
            _data = default(T);
            _lChild = null;
            _rChild = null;
        }

        public Node(T _data)
        {
            this._data = _data;
            _lChild = null;
            _rChild = null;
        }

        public Node(T _data, Node<T> _lChild, Node<T> _rChild)
        {
            this._data = _data;
            this._lChild = _lChild;
            this._rChild = _rChild;
        }

        public Node(Node<T> _lChild, Node<T> _rChild)
        {
            this._lChild = _lChild;
            this._rChild = _rChild;
        }

    }

 

2 二叉树的实现

二叉树的实现主要有能下几个功能：

Ø 构造一个新的二叉树

Ø 插入指定节点的左子节点；

Ø 插入指定节点的右子节点；

Ø 删除指定节点的左子节点；

Ø 删除指定节点的右子节点；

Ø 判断二叉树是否为空；

Ø 判断节点是否为叶子节点。

代码实现如下： 

  1 /**//// <summary>
  2    /// 二叉树的操作实现
  3    /// </summary>
  4    /// <typeparam name="T"></typeparam>
  5    public class BinaryTree<T>
  6    {
  7        private Node<T> _header;
  8
  9
 10        ..构造函数..#region ..构造函数..
 11
 12        public BinaryTree()
 13        {
 14            _header = null;
 15        }
 16
 17        public BinaryTree(T _data)
 18        {
 19            Node<T> _headerNode = new Node<T>(_data);
 20            this._header = _headerNode;
 21        }
 22
 23        public BinaryTree(T _data, Node<T> _lChild, Node<T> _rChild)
 24        {
 25            Node<T> _headerNode = new Node<T>(_data, _lChild, _rChild);
 26            this._header = _headerNode;
 27        }
 28
 29        #endregion
 30
 31        /**//// <summary>
 32        /// 二叉树根节点(头节点)
 33        /// </summary>
 34        public Node<T> Header
 35        {
 36            get { return _header; }
 37            set { _header = value; }
 38        }
 39
 40        /**//// <summary>
 41        /// 插入左子节点
 42        /// </summary>
 43        /// <param name="_fNode"></param>
 44        /// <param name="_data"></param>
 45        public void InsertL(Node<T> _fNode, T _data)
 46        {
 47            /**//*
 48             * 步骤:
 49             * 1 New新的节点
 50             * 2 新节点引用要原父节点的左子节点
 51             * 3 父节点的左子节点引用新节点
 52             */
 53            Node<T> _node = new Node<T>(_data);
 54            _node.LChild = _fNode.LChild;
 55            _fNode.LChild = _node;
 56        }
 57
 58        /**//// <summary>
 59        /// 插入右子节点
 60        /// </summary>
 61        /// <param name="_fNode"></param>
 62        /// <param name="_data"></param>
 63        public void InsertR(Node<T> _fNode, T _data)
 64        {
 65            //思路同插入左子节点
 66            Node<T> _node = new Node<T>(_data);
 67            _node.LChild = _fNode.RChild;
 68            _fNode.RChild = _node;
 69        }
 70
 71
 72        /**//// <summary>
 73        /// 删除指定节点的左子节点
 74        /// </summary>
 75        /// <param name="node"></param>
 76        public Node<T> DeleteL(Node<T> node)
 77        {
 78            if (node == null || node.LChild == null)
 79            {
 80                return null;
 81            }
 82            /**//*
 83             * 步骤:
 84             * 1 获取左子节点的引用
 85             * 2 把指定节点的左子节点引用设为NULL
 86             * 3 返回左子节点的引用
 87             */
 88            Node<T> lChild = node.LChild;
 89            node.LChild = null;
 90            return lChild;
 91        }
 92
 93        /**//// <summary>
 94        /// 删除指定节点的右子节点
 95        /// </summary>
 96        /// <param name="node"></param>
 97        /// <returns></returns>
 98        public Node<T> DeleteR(Node<T> node)
 99        {
100            if (node == null || node.RChild == null)
101            {
102                return null;
103            }
104            //步骤同删除指定节点的左子节点相同,只不过是首先获取的是右子节点的引用
105            Node<T> rChild = node.RChild;
106            node.RChild = null;
107            return rChild;
108        }
109
110        /**//// <summary>
111        /// 判断是否为空
112        /// </summary>
113        /// <returns></returns>
114        public bool IsEmpty()
115