二叉树的递归和非递归

阅读量：2242 次

发布时间：2019-05-09

本文共 8742 字，大约阅读时间需要 29 分钟。

二叉树

递归 非递归

递归版本

构造一颗二叉树

代码

Node* _CreatTree(T* a, size_t n, const T& invalid, size_t& index)    {
          assert(NULL != a && n > 0);        Node* root = NULL;        if (index < n && a[index] != invalid)        {
              root = new Node(a[index]);            root->_Lchild = _CreatTree(a, n, invalid, ++index);            root->_Rchild = _CreatTree(a, n, invalid, ++index);        }        return root;    }

中序创建一颗树，碰到invalid就返回，先构造根节点，构造左子树，构造右子树

图示

CreatTree

先序遍历

代码

void  _PreOder(Node* root)    {
          if (NULL == root){
   return;}        cout<
    
     _data<<" ";        _PreOder(root->_Lchild);        _PreOder(root->_Rchild);    }

图示

PreOder

先读取节点数据随后遍历左子树，再遍历右子树。

中序遍历

代码

void  _InOder(Node* root)    {
          if (NULL == root){
   return;}        _InOder(root->_Lchild);        cout<
    
     _data<<" ";        _InOder(root->_Rchild);    }

后序遍历

代码

void  _PostOder(Node* root)    {
          if (NULL == root){
   return;}        _PostOder(root->_Lchild);        _PostOder(root->_Rchild);        cout<
    
     _data<<" ";    }

当前节点的左孩子为空时访问数据，随后将他的右孩子当成子问题继续访问

析构

代码

void  _Destroy(Node* root)    {
          if (NULL == root){
   return;}        _Destroy(root->_Lchild);        _Destroy(root->_Rchild);        //cout<
    
     _data<<" ";        delete root;    }

注意最后释放根节点数据

Find

代码

Node* _Find(Node* root, const T& data)    {
          if (NULL == root){
   return NULL;}        if (data == root->_data){
   return root;}        Node* Left = _Find(root->_Lchild,data);        return Left != NULL ? Left:_Find(root->_Rchild,data);    }

当前根节点找到就返回，else遍历左子树将结果给left，left如果为空时再遍历右子树寻找

Size

代码

size_t _Size(Node* root)    {
          if (NULL == root){
   return NULL;}        return _Size(root->_Lchild) + _Size(root->_Rchild) + 1;    }

返回左子树节点个数+右子树节点个数+1(1是根节点)

LeafSize

代码

size_t _LeafSize(Node* root)    {
          if (NULL == root){
   return NULL;}        if (NULL == root->_Lchild && NULL == root->_Rchild){
   return 1;}   //找到一个叶子节点        return  _LeafSize(root->_Lchild) + _LeafSize(root->_Rchild);    }

若当前节点同时无左右孩子返回1,最后返回左子树+右子树的叶子节点

GetKLevelSize

代码

size_t _GetKLevelSize(Node* root,size_t K)    {
          if (NULL == root){
   return NULL;}        if (K == 1){
   return 1;} //到达第K层                     /*右子树的第K-1层阶节点数   +   左子树的第K-1层阶节点数*/        return _GetKLevelSize(root->_Lchild,K-1) + _GetKLevelSize(root->_Rchild,K-1);    }

到达第K层时当前函数返回1，递归实现左树+右树第K-1层结点个数

Depth

代码

size_t _Depth(Node* root)    {
          if (NULL == root){
   return NULL;}        if (NULL == root->_Lchild && NULL == root->_Rchild){
   return 1;}        size_t Left = _Depth(root->_Lchild);        size_t Right = _Depth(root->_Rchild);        return Left > Right? Left + 1:Right+1;    }

分别递归求左子树和右子树的深度，返回深的那个

非递归

先序遍历

代码

void PreOderNoR()     {
           if (NULL == _root){
   return;}         Node* cur = _root;         stack
    
      s;         while (cur || !s.empty())         {
               while(cur)             {
                   s.push(cur);                 cout<
     
      _data<<" ";                 cur = cur->_Lchild;             }             //右子树走完了             Node*top = s.top(); //将最右端的节点拿出来             s.pop();             cur = top->_Rchild; //将最右端节点的左节点当成子问题         }         cout<

中序遍历

代码

void InOderNoR()     {
           if (NULL == _root){
   return;}         stack
    
      s;         Node* cur = _root;         while (cur || !s.empty())         {
               while (cur)             {
                   s.push(cur);                 cur = cur->_Lchild;             }             //右子树走完             Node* top = s.top();             s.pop();             cout<
     
      _data<<" ";             cur = top->_Rchild;         }         cout<

后序遍历

代码

void PostOderNoR()     {
           if (NULL == _root){
   return;}         stack
    
      s;         Node* cur = _root;         Node* prev = NULL;         while (cur || !s.empty())         {
               while (cur)             {
                   s.push(cur);                 cur = cur->_Lchild;             }             Node* front = s.top();             /*这里注意判断根节点的左子树是否已经访问过了*/             if (NULL == front->_Rchild || prev == front->_Rchild)             {
                   cout<
     
      _data<<" ";                 prev = front;                 s.pop();             }             else             {
                   cur = front->_Rchild;             }         }            cout<

后序遍历的条件要注意，在走完右子树返回根节点是要判断一下右子树是否走过，如果走过就不能再走

All_Code

#ifndef __BINARYTREE_H__ #define __BINARYTREE_H__ #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; template 
         
           struct BinaryNode { T _data; BinaryNode
          
           * _Lchild; BinaryNode
           
            * _Rchild; BinaryNode
            
             (const T& data) :_data(data) ,_Lchild(NULL) ,_Rchild(NULL) {} }; template 
             
               class BinaryTree { typedef BinaryNode
              
                Node; public: BinaryTree() :_root(NULL) {} BinaryTree(T* a, size_t n, const T& invalid) { size_t index = 0; _root = _CreatTree(a, n, invalid, index); } BinaryTree(const BinaryTree
               
                & t) { _root = _CopyBinaryTree(t._root); } /*BinaryTree
                
                  operator=(const BinaryTree
                 
                   tree) { _root = _OperatorCopy(tree._root); }*/ BinaryTree
                  
                    operator=(BinaryTree
                   
                     tree) { swap(_root, tree._root); return *this; } ~BinaryTree() { _Destroy(_root); } void PreOder() { _PreOder(_root); cout<
                    
                      s; while (cur || !s.empty()) { while(cur) { s.push(cur); cout<
                     
                      _data<<" "; cur = cur->_Lchild; } //右子树走完了 Node*top = s.top(); //将最右端的节点拿出来 s.pop(); cur = top->_Rchild; //将最右端节点的左节点当成子问题 } cout<
                      
                        s; Node* cur = _root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_Lchild; } //右子树走完 Node* top = s.top(); s.pop(); cout<
                       
                        _data<<" "; cur = top->_Rchild; } cout<
                        
                          q; if (NULL != _root){q.push(_root);} //先将根节点放入队列中 while (!q.empty()) { Node* front = q.front();//把上一个节点节点拿出来访问 cout<
                         
                          _data<<" "; if (front->_Lchild) //访问右子树 { q.push(front->_Lchild); } if (front->_Rchild) //访问左子树 { q.push(front->_Rchild); } q.pop(); //将上一个根节点pop掉 } cout<
                          
                            s; Node* cur = _root; Node* prev = NULL; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_Lchild; } Node* front = s.top(); if (NULL == front->_Rchild || prev == front->_Rchild) { cout<
                           
                            _data<<" "; prev = front; s.pop(); } else { cur = front->_Rchild; } } cout<
                            
                             _data);//拷贝当前根节点 NewNode->_Lchild = (_CopyBinaryTree(root->_Lchild));//拷贝左子树 NewNode->_Rchild = (_CopyBinaryTree(root->_Rchild));//拷贝右子树 return NewNode; } Node* _CreatTree(T* a, size_t n, const T& invalid, size_t& index) { assert(NULL != a && n > 0); Node* root = NULL; if (index < n && a[index] != invalid) { root = new Node(a[index]); root->_Lchild = _CreatTree(a, n, invalid, ++index); root->_Rchild = _CreatTree(a, n, invalid, ++index); } return root; } Node* _OperatorCopy(Node* root) { if (_root != root) { ~BinaryTree(); } return _CopyBinaryTree(root); } Node* _Find(Node* root, const T& data) { if (NULL == root){ return NULL;} if (data == root->_data){ return root;} Node* Left = _Find(root->_Lchild,data); return Left != NULL ? Left:_Find(root->_Rchild,data); } void _Destroy(Node* root) { if (NULL == root){ return;} _Destroy(root->_Lchild); _Destroy(root->_Rchild); //cout<
                             
                              _data<<" "; delete root; } void _PreOder(Node* root) { if (NULL == root){ return;} cout<
                              
                               _data<<" "; _PreOder(root->_Lchild); _PreOder(root->_Rchild); } void _PostOder(Node* root) { if (NULL == root){ return;} _PostOder(root->_Lchild); _PostOder(root->_Rchild); cout<
                               
                                _data<<" "; } void _InOder(Node* root) { if (NULL == root){ return;} _InOder(root->_Lchild); cout<
                                
                                 _data<<" "; _InOder(root->_Rchild); } size_t _Size(Node* root) { if (NULL == root){ return NULL;} return _Size(root->_Lchild) + _Size(root->_Rchild) + 1; } size_t _LeafSize(Node* root) { if (NULL == root){ return NULL;} if (NULL == root->_Lchild && NULL == root->_Rchild){ return 1;} //找到一个叶子节点 return _LeafSize(root->_Lchild) + _LeafSize(root->_Rchild); } size_t _GetKLevelSize(Node* root,size_t K) { if (NULL == root){ return NULL;} if (K == 1){ return 1;} //到达第K层 /*右子树的第K-1层阶节点数 + 左子树的第K-1层阶节点数*/ return _GetKLevelSize(root->_Lchild,K-1) + _GetKLevelSize(root->_Rchild,K-1); } size_t _Depth(Node* root) { if (NULL == root){ return NULL;} if (NULL == root->_Lchild && NULL == root->_Rchild){ return 1;} size_t Left = _Depth(root->_Lchild); size_t Right = _Depth(root->_Rchild); return Left > Right? Left + 1:Right+1; } protected: Node* _root; }; void TestBinaryTree() { int a[] = { 1,2,3,'#','#',4,'#','#',5,6}; int b[] = { 1,2,4,'#','#',5,8,'#',9,10,'#','#','#','#',3,6,'#',11,'#',12,13,'#',14,'#','#','#',7}; //BinaryTree
                                 
                                   tree(a,sizeof(a)/sizeof(a[0]),'#'); BinaryTree
                                  
                                    tree(b,sizeof(b)/sizeof(b[0]),'#'); } #endif //__BINARYTREE_H__