二叉树的基本操作方式

太过爱你忘了你带给我的痛 2022-06-16 05:40 201阅读 0赞

二叉树的一些基本操作都是通过递归来实现的  
在用递归解决二叉树的问题时要善于二叉树划分为根节点左子树和右子树。  
![这里写图片描述][SouthEast]

二叉树递归创建的具体函数调用过程

![这里写图片描述][SouthEast 1]

二叉树的递归实现的基本操作
    #include<iostream>
    #include<stdlib.h>
    #include<queue>
    using namespace std;
    template<class T>
    struct BinaryTreeNode
    {
            BinaryTreeNode( const T &x)
            :Lchild( NULL)
            , Rchild( NULL)
            , value( x)
            {
    
            }
             BinaryTreeNode<T >* Lchild;
             BinaryTreeNode<T >* Rchild;
             T value;
    };
    template<class T>
    class BinaryTree
    {
    public:
             typedef BinaryTreeNode <T> Node;
            BinaryTree()
                   :_Root( NULL)
            {
    
            } //一颗空树
            BinaryTree( T*a , int size, int invalid )
            {
                    int index = 0;
                   _root=_CreatBinaryTree( a,size ,invalid,index);
            }
            BinaryTree( const BinaryTree &t)
            {
                   _root=_Copy( t._root);
            }
             BinaryTree& operator=(const BinaryTree& t)
            {
                    return _assign(t ._root);
            }
            ~BinaryTree()
            {
                   _Delete(_root);
            }
             void PrevOrder()
            {
                   _PrevOrder(_root);
                   cout << endl;
            }
             void InOrder()
            {
                   _InOrder(_root);
                   cout << endl;
            }
             void PostOrder()
            {
                   _PostOrder(_root);
                   cout << endl;
            }
             void LevelOrder()
            {
                   _LevelOrder(_root);
            }
             size_t Size()
            {
                    return _Size(_root);
            }
             size_t _Size(Node *root)
            {
                    if (root == NULL)
                   {
                            return 0;
                   }
                    else
                   {
                            return _Size(root ->Lchild) + _Size(root->Rchild) + 1;
                   }
            }
             size_t LeafSize()
            {
                    return _LeafSize(_root);
            }
             size_t  _LeafSize(Node *root)
            {
                    if (root == NULL)
                   {
                            return 0;
                   }
                    if (root ->Lchild == NULL&& root->Rchild == NULL)
                   {
                            return 1;
                   }
                    else
                   {
                            return _LeafSize(root ->Lchild) + _LeafSize(root->Rchild);
                   }
    
            }
             size_t GetKLevel(size_t k)
            {
                    return _GetKLevel(_root, k );
            }
             size_t Depth()
            {
                    return _Depth(_root);
            }
             Node* Find(const T& x)
            {
                    return _Find(_root, x );
            }
    protected:
             Node* _Copy(Node *root) //拷贝构造
            {
                    Node* tmp = NULL ;
                    if (root != NULL)
                   {
                           tmp = new Node (root->value);
                           tmp->Lchild = _Copy( root->Lchild);
                           tmp->Rchild = _Copy( root->Rchild);
                   }
                    return tmp;
            }
    
             BinaryTree&_assign(Node *root) //赋值运算符
            {
                    if (_root != NULL )
                   {
                           _Delete(_root);
                   }
                    Node* tmp = NULL ;
                    if (root != NULL)
                   {
                           tmp = new Node (root->value);
                           tmp->Lchild = _Copy( root->Lchild);
                           tmp->Rchild = _Copy( root->Rchild);
                   }
                   _root = tmp;
                    return *this ;
            }
             Node* _CreatBinaryTree(const T*a, int size, int invalid, int & index)
            {
                    Node* root = NULL ;
                    if (index < size&& a[index ] != invalid)
                   {
                           root = new Node (a[index]);
                           root->Lchild = _CreatBinaryTree( a, size , invalid, ++index );
                           root->Rchild = _CreatBinaryTree( a, size , invalid, ++index );
                   }
                    return root;
            }
             void _Delete(Node *root)
            {
                    if (root != NULL)
                   {
                           _Delete( root->Lchild);
                           _Delete( root->Rchild);
                           delete root ;
                           root = NULL ;
                   }
    
            }
             void _PrevOrder(Node *root)
            {
                    if (root != NULL)
                   {
                           cout << root->value << " " ;
                           _PrevOrder( root->Lchild);
                           _PrevOrder( root->Rchild);
                   }
            }
             void _InOrder(Node *root)
            {
                    if (root != NULL)
                   {
                           _InOrder( root->Lchild);
                           cout << root->value << " " ;
                           _InOrder( root->Rchild);
                   }
            }
             void _PostOrder(Node *root)
            {
                    if (root != NULL)
                   {
                           _PostOrder( root->Lchild);
                           _PostOrder( root->Rchild);
                           cout << root->value << " " ;
                   }
            }
             void _LevelOrder(Node *root)
            {
                    queue<Node *>q;
                    if (root )
                   {
                           q.push( root);
                   }
                    while (!q.empty())
                   {
                            Node*tmp = q.front();
                           q.pop();
                           cout << tmp->value << " ";
                            if (tmp->Lchild)
                           {
                                  q.push(tmp->Lchild);
                           }
                            if (tmp->Rchild)
                           {
                                  q.push(tmp->Rchild);
                           }
                   }
            } //利用了队列先进先出的特点进行了广度优先遍历
             size_t _GetKLevel(Node *root, size_t k )
            {
                    if (root == NULL)
                   {
                            return 0;
                   }
                    if (k == 1)
                   {
                            return 1;
                   }
                    return _GetKLevel(root ->Lchild, k - 1) + _GetKLevel(root->Rchild, k - 1);
            }
             size_t _Depth(Node *root) //思想比较左右字数的大小，左子树比右子树大则返回左子树的大小+1
            {
                    if (root == NULL)
                   {
                            return 0;
                   }
                    size_t left = _Depth(root ->Lchild);
                    size_t right = _Depth(root ->Rchild);
                    return left > right ? left + 1 : right + 1;
            }
             Node* _Find(Node *root, const T &x)
            {
                    if (root == NULL)
                   {
                            return NULL ;
                   }
                    if (root ->value == x)
                   {
                            return root ;
                   }
                    Node*ret = _Find(root ->Lchild, x);
                    if (ret != NULL )
                   {
                            return ret;
                   }
                    return _Find(root ->Rchild, x);
            }
    protected:
             Node* _root;
    };
    void FunTest()
    {
             int array1[10] = { 1, 2, 3, '#' , '#', 4, '#', '#' , 5, 6 };
             int array2[10] = { 7, 8, 9, '#' , '#', 10, '#', '#' , 11, 12 };
             BinaryTree<int > t1(array1, sizeof(array1) / sizeof(array1[0]), '#' );
             BinaryTree<int > t2(array2, sizeof(array2) / sizeof(array2[0]), '#' );
            t1.PrevOrder();
            t2.PrevOrder();
            t2 = t1;
            t2.PrevOrder();
            t2.LevelOrder();
            cout << t2.Size()<<endl;
            cout << t2.LeafSize() << endl;
            cout << t2.Find(4)<<endl;
            cout << "Depth:" << t2.Depth()<< endl;
            cout << "GetKLevel:" << t2.GetKLevel(2)<<endl;
    }
    int main()
    {
            FunTest();
            system( "pause");
             return 0;
    }

[SouthEast]: /images/20220616/e8219f665aab4303be73ae4144d01882.png
[SouthEast 1]: /images/20220616/c5c78343265a487ca84330799d43bf60.png