递归创建二叉树以及一些基本操作

这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。二叉树的遍历是进行二叉树其他操作的基础，如二叉树的线索化、二叉树的构造、二叉树的还原等等，都要用到二叉树的遍历算法。对于数据结构这门课是我们的重中之重：数据结构作为核心内容应该是算法二叉排序树的实现，所以大家在后续复习的时候，比如说线性表的算法二叉排序树的实现，树好二叉树的算法，图的算法，这些算法是希望大家完全掌握的，包括手动计算以及程序设计。

之前我们在学习例如顺序表链表，栈和队列，会涉及到增删查改，但是在二叉树的基本部分我们不会涉及到增删查改，因为二叉树的实际用处不是很大，我们最重要的是需要了解二叉树的基本结构，为以后的搜索树和平衡树的学习打下基础。二叉树的遍历是目前阶段我们需要熟练掌握的内容。

二叉树的遍历方式有三种：前序、中序和后序。 在学习二叉树的时候，把二叉树分为三部分：根结点，左子树和右子树，所谓遍历方式即访问这三部分的先后顺序。

我对于二叉树遍历的方式的理解是這样的：

前序遍历：先访问根结点，再访问左子树，最后访问右子树。

中序遍历：先访问左子树，再访问根节点，最后访问右子树。

后序遍历：先访问左子树，再访问右子树，最后访问根结点。

以一个简单的二叉树为例子

该二叉树一共有六个结点，将6个整数放置其中。

一个结点里面分为三个部分，一个部分存放数据，另外两个存放指向左子树根结点的指针和指向右子树根结点的指针。

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<assert.h>
#include<stack>
#include<queue>
using namespace std;
template<class T>
struct BinaryTreeNode
{
    T _data;
    BinaryTreeNode<T>* _left;
    BinaryTreeNode<T>* _right;
    BinaryTreeNode(const T& d)
         :_data(d)
         ,_left(NULL)
         , _right(NULL)
    {
         cout << "构造二叉树结点" << endl;
    }
};
template<class T>
class BinaryTree
{
    typedef BinaryTreeNode<T> Node;
private:
    Node* _root;
protected:
    Node* _CreateTree(T* a, size_t n, const T& invalid, size_t& index)  //這里的index由调用這个函数的那个函数里面给传进来；但是這里出现了问题，还是因为栈帧的原因，在往根节点回的时候，下层的index并不会影响上层的index从而导致错 误解决方案是： &
    {
         //index = 0;  //注意：這里不能给下标一个初值，递归会出现问题
         Node* root = NULL;
         if (index < n && a[index] != invalid)
         {
             root = new Node(a[index]);
             root->_left = _CreateTree(a, n, invalid, ++index);    //出现的问题：  我一开始写的是index++，但是出现了无限循环，注意创建的新的栈帧就会产生新的index
             root->_right = _CreateTree(a, n, invalid, ++index);
         }
         return root;
    }
    void _PrevOrder(Node* root)    //前序遍历
    {
         if (root == NULL)       //返回条件
             return;
         cout << root->_data << " ";
         _PrevOrder(root->_left);
         _PrevOrder(root->_right);
    }
    void _InOrder(Node* root)    //中序遍历
    {
         if (root == NULL)       //返回条件
             return;
         _InOrder(root->_left);             
         cout << root->_data << " ";
         _InOrder(root->_right);
    }
    void _PostOrder(Node* root)   //后序遍历
    {
         if (root == NULL)        //返回条件
             return;
         _PostOrder(root->_left);
         _PostOrder(root->_right);
         cout << root->_data << " ";
    }
    void _LevelOrder(Node* root)     // 层序遍历  使用非递归  利用queue的先进先出原则                                             [*]
    {
         queue<Node*> q;
         if (root)                       //根结点入队
             q.push(root);
         else
             return;
         while (!q.empty())              
         {
             Node* cur = q.front();
             cout << cur->_data << " ";
             if (cur->_left)
                 q.push(cur->_left);
             if (cur->_right)
                 q.push(cur->_right);
             q.pop();    //這里实际上是通过pop让树往下走的，完成了类似于递归的作用
         }
         cout << endl;
    }
    size_t _Size(Node* root)         //求结点个数
    {
       if (root == NULL)
             return 0;
       if (root->_left == NULL && root->_right == NULL)//  在這个递归中的返回条件
             return 1;
         return _Size(root->_left) + _Size(root->_right) + 1;                                         //這里记得+1   因为有根结点
    }
    size_t _LeafSize(Node* root)     //求叶子结点个数
    {
         if (root == NULL)
             return 0;
         if (root->_left == NULL&&root->_right == NULL)
             return 1;
         return _LeafSize(root->_left) + _LeafSize(root->_right);
    }
    size_t _GetKLevel(Node* root, size_t k)    //求第K层结点个数
    {
         if (root == NULL)
             return 0;                         
         if (k == 1)
             return 1;
         if (k > 1)
             return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);      //尾递归
         else
         {
             cout << "'k' is wrong" << " ";
             return 0;
         }
    }
    size_t _Depth(Node* root)          //求二叉树的深度
    {
         if (root == NULL)
             return 0;
         if (root->_left == NULL && root->_right == NULL)
             return 1;
         size_t leftdepth = _Depth(root->_left);        //分两边进行比较
         size_t rightdepth = _Depth(root->_right);
         return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;               //不要忘记+1 根结点
    }
    Node* _Find(Node* root,const T& t) //查找                                                                                     [*]
    {
         /*if (root == NULL)
              return NULL;
          Node* tmp = _Find(root->_left, t);
          if (root->_data == t)
          {
              return root;
          }
          _Find(root->_right, t);*/
         if (root == NULL)
             return NULL;
         if (root->_data == t)
             return root;
         Node* tmp = _Find(root->_left, t);
         if (tmp)
             return tmp;
         return _Find(root->_right, t);
    }
    Node* _Copy(Node* root)      //拷贝     [*]
    {
         if (root == NULL)
             return NULL;
         Node* copyroot = new Node(root->_data);
         copyroot->_left = _Copy(root->_left);
         copyroot->_right = _Copy(root->_right);
         return copyroot;
    }
    void Destory(Node* root)
    {
         if (root == NULL)
             return;
         Destory(root->_left);
         Destory(root->_right);
         delete root;              //释放当前结点
         root = NULL;
    }
public:
    BinaryTree()              //无参构造函数
         : _root(NULL)
    {
    }
    BinaryTree(T* a, size_t n, const T& invalid)  //带参的构造函数               //注意：无参的递归是不能写在公有的成员函数里面的
    {
         size_t index = 0;     //注意這里为什么我们把index单独拿出来给初始化0
         _root = _CreateTree(a, n, invalid, index);
    }
    BinaryTree(const BinaryTree<T>& t)                     //拷贝构造
    {
         _root = _Copy(t._root);
    }
    BinaryTree<T>& operator=(const BinaryTree<T>& t)             //赋值运算符重载
    {
         if (_root)
             Destory(_root);
         _root = _Copy(t._root);
         return *this;
    }
    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 LeafSize()                                         //叶子结点个数
    {
         return _LeafSize(_root);
    }
    size_t GetKLevel(size_t k)                                 //K层结点
    {
         return _GetKLevel(_root, k);
    }
    size_t Depth()                                            //树的深度
    {
         return _Depth(_root);
    }
    Node* Find(const T& d)                                    //查找
    {
         return _Find(_root, d);
    }
    ~BinaryTree()                                             //析构
    {
         Destory(_root);
         _root = NULL;
         cout << "析构" << endl;
    }
};
void test()               //———————— 测试 ——————————
{
    int arr[] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
    BinaryTree<int> t1(arr,sizeof(arr)/sizeof(arr[0]),'#');
    t1.PrevOrder();
    t1.InOrder();
    t1.PostOrder();
    t1.LevelOrder();
    cout << t1.Size() << endl;
    cout << t1.LeafSize() << endl;
    cout<<t1.GetKLevel(3)<<endl;
    cout << t1.Find(3) << endl;
    BinaryTree<int> t2(t1);
    t2.PrevOrder();
    t2.InOrder();
    t2.PostOrder();
    t2.LevelOrder();
    cout << t2.Size() << endl;
    cout << t2.LeafSize() << endl;
    cout << t2.GetKLevel(3) << endl;
    cout << t2.Find(3) << endl;
    BinaryTree<int> t3;
    t3 = t1;
    t3.PrevOrder();
    t3.InOrder();
    t3.PostOrder();
    t3.LevelOrder();
}
int main()
{
    test();
    return 0;
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-115983-1.html