数据结构--二叉树(1)

二叉树

构建：二叉树的构建采用的是先序遍历，->先储存根节点然后左右节点，用递归的思想将所有数据放在树中。

代码实现：实现了4种访问方法，先序，中序，后序，和层序的访问方法都采用递归的方式。

#include#include#includeusing namespace std;template struct rootnode{        T _value;        rootnode *_leftnode;        rootnode *_rightnode;        rootnode(T value)                : _value(value),                _leftnode(NULL),                _rightnode(NULL)        {}};template class BinaryTree{public:        BinaryTree( T *str)        {                T *tmp = str;                _root = _BinaryTree(tmp);        }        ~BinaryTree()        {                _Clear(_root);        }        BinaryTree (BinaryTree &t)        {                _root=_Copy(t._root);        }        BinaryTree& operator=(BinaryTree t)        {                if (*this != t)                {                        swap(_root, t._root);                }        }        void Fastorder()        {                _Fastorder(_root);        }        void Inorder()        {                _Inorder(_root);        }        void Postorder()        {                _Postorder(_root);        }        void Levelorder()        {                queue*> q;                        if (_root == NULL)                        {                                return;                        }                        q.push(_root);                        while (!q.empty())                        {                                rootnode* root = q.front();                                cout << root->_value;                                q.pop();                                if (root->_leftnode != NULL)                                {                                        q.push(root->_leftnode);                                }                                if (root->_rightnode != NULL)                                {                                        q.push(root->_rightnode);                                }                        }               }        int leafnum()        {                int num = 0;                num=_Leafnum(_root,num);                return num;        }        int Size()        {                int size = 0;                _Size(_root,size);                return size;        }        int Depth()        {                int Depth = _Depth(_root);                return Depth;        }        void NRfastorder()        {                stack*> s;                if (_root != NULL)                {                        s.push(_root);                }                while (!s.empty())                {                        rootnode* front=s.top();                        cout<_value;                        s.pop();                        if (front->_rightnode != NULL)                        {                                s.push(front->_rightnode);                        }                        if (front->_leftnode != NULL)                        {                                s.push(front->_leftnode);                        }                }        }        void NRinorder()        {                stack*>s;                rootnode*cur = _root;                rootnode* top = NULL;                while (cur||!s.empty())                {                        while (cur)                        {                                s.push(cur);                                cur = cur->_leftnode;                        }                                               if (top != s.top()->_rightnode)                        {                                top = s.top();                                cout << top->_value;                                s.pop();                                cur = top->_rightnode;                        }                        else                        {                                top = s.top();                                cout << top->_value;                                s.pop();                        }                }        }        void NRpostorder()        {                rootnode*cur = _root;                stack*> s;                rootnode*top = NULL;                while (cur || !s.empty())                {                        while (cur)                        {                                s.push(cur);                                cur = cur->_leftnode;                        }                        if (s.top()->_rightnode != NULL&&top != s.top()->_rightnode)                        {                                top = s.top();                                cur = top->_rightnode;                                                }                        else                        {                                top = s.top();                                s.pop();                                cout << top->_value;                        }                                }        }protected:        rootnode* _BinaryTree(T *&str)        {                rootnode *root = NULL;                if (*str != '#'&&*str != '\0')                {                        root = new rootnode(*str);                        str++;                        root->_leftnode = _BinaryTree(str);                        str++;                        root->_rightnode = _BinaryTree(str);                }                return root;        }        void _Fastorder(rootnode *&root)        {                if (root == NULL)                {                                                return;                }                else                {                        cout << root->_value;                        _Fastorder(root->_leftnode);                        _Fastorder(root->_rightnode);                                        }        }        void _Inorder(rootnode *root)        {                if (root == NULL)                {                        return;                }                _Inorder(root->_leftnode);                cout << root->_value;                _Inorder(root->_rightnode);        }        void _Postorder(rootnode *root)        {                if (root == NULL)                {                        return;                }                _Postorder(root->_leftnode);                _Postorder(root->_rightnode);                cout << root->_value;        }        void _Clear(rootnode *root)        {                if (root == NULL)                {                        return;                }                rootnode *tmp = root->_leftnode;                rootnode *tmp2 = root->_rightnode;                delete root;                _Clear(tmp);                _Clear(tmp2);        }        rootnode* _Copy(rootnode *root)        {                rootnode *newroot = NULL;                if (root == NULL)                {                        return newroot;                }                newroot = new rootnode(root->_value);                newroot->_leftnode = _Copy(root->_leftnode);                newroot->_rightnode = _Copy(root->_rightnode);                return newroot;        }        int _Size(rootnode *root,int &size)        {                if (root == NULL)                {                        return 0;                }                size++;                _Size(root->_leftnode,size);                _Size(root->_rightnode,size);                return size;        }        int _Depth(rootnode *root)        {                if (root==NULL)                {                        return 0;                }                int hight = 1;                int left = 0;                int right = 0;                left += _Depth(root->_leftnode) + hight;                right += _Depth(root->_rightnode) + hight;                if (left > right)                {                        return left;                }                else                {                        return right;                }                        }        int _Leafnum(rootnode* root,int &num)        {                if (root == NULL)                {                        return 0;                }                if (root->_leftnode == NULL&&root->_rightnode == NULL)                {                        num++;                }                _Leafnum(root->_leftnode, num);                _Leafnum(root->_rightnode, num);                return num;        }private:        rootnode *_root;};void Test1(){        char *str = "123##45##6##78###";        BinaryTree b1(str);        BinaryTree b2(b1);        BinaryTree b3 = b2;        b1.Fastorder();        cout << endl;        b1.Inorder();        cout << endl;        b1.Postorder();        cout << endl;        b2.Fastorder();        cout << endl;        b3.Fastorder();        cout << endl;        cout << b3.Size()<