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

Node* _BinaryTree(T* a, size_t n, const T& invalid, size_t& index)

注意上面的构造函数里面的index使用了引用

如果不使用引用就会出现问题

原因是什么呢？我的理解是這样的：

aload index 当前frame的局部变量数组中下标为index的引用型局部变量进栈.。当自动变量有结构体和数组等较大的构造型数据的时候，需要在栈上开辟较大的空间。引用变量就相当于是为数组或对象起的一个名称，以后就可以在程序中使用栈中的引用变量来访问堆中的数组或对象。

二叉树在建造的时候的栈帧图：

（图中的代码已经简化不具有严格的正确性只是作为示意）

此二叉树在遍历（前序）的时候栈帧：

1.递归求第K层的叶子结点数：

代码：

size_t _KLevelSize(Node* root,const size_t& K)       [*]
    {
         if (root == NULL)
             return 0;
         if (K == 1)
             return 1;
         if (K > 1)
     return _KLevelSize(root->_left, K - 1) + _KLevelSize(root->_right, K - 1);   
         else
             perror("K is wrong!");
    }

调用栈帧示意：

2.递归求数的深度（左树与右树相比）

代码：

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是加上根结点    
    }

3.递归查找 *

注：查找即一旦找到了就返回（返回到最顶上的栈空间） 结束整个递归的过程

代码：

Node* _Find(Node* root, const T& d)                     //查找[*]
    {
         if (root == NULL)
             return NULL;
         if (root->_data == d)
             return root;
         /*else                            //這样写有问题
          {
              _Find(root->_left,d);
              _Find(root->_right, d);
          }*/
         Node* tmp = _Find(root->_left,d);          
         if (tmp != NULL)                        //注意這个判断放的位置
             return tmp;                     
         _Find(root->_right, d);              //子问题思想
    }

4.递归 析构树（Destory函数）

如果foo没有一个虚拟析构函数，编译器只会生成一个对ibar隐式空析构函数的调用，而foo的构析函数并没有被调用，因此会造成内存漏泄。 ’\0’3 函数的嵌套调用：一个函数可以调用其他的函数，其他函数还可再调用别的函数（除了main函数）4 函数的递归调用：函数自己调用自己，注意调用要有必要的出口使得运行能够结束。在对象生命周期调用结束时，__del__ 方法会被调用，可以将__del__理解为“构析函数”。

代码：

void Destory(Node* root)              //[*]
    {
         if (root == NULL)
             return;
         Destory(root->_left);
         Destory(root->_right);
         delete root;             //注意這里的delete一定要放在最后  相当于后序析构，因为先析构根结点子树就找不到了，没办法析构
    }

5.递归 拷贝树（Copy函数）

注意：针对于实现二叉树的拷贝构造和赋值运算符的重载的时候 使用到了拷贝函数，這里也需要建立子问题的思想

代码：

Node* _Copy(Node* root)
    {
         Node* newroot = NULL;
         if (root == NULL)
             return NULL;
         newroot = new Node(root->_data);
         newroot->_left = _Copy(root->_left);
         newroot->_right = _Copy(root->_right);
         return newroot;
    }

以上只是递归实现

◆详细讨论了递归编程的用法，包括大量难度各异的编程示例和练习，如简单的递归函数，分析双人游戏的最小最大(minimax)策略，等等。只要把思路理清楚了现实起来其实还是挺容易的，只要我们熟悉了一种二叉树的非递归遍历方式，其他几种非递归方式就容易多了，照着葫芦画瓢，下面是中序遍历的递归方式，中序遍历的思想是：先访问左孩子节点，在访问根节点，最后访问右节点。虽然这三种遍历递归方式都比较简单，但非递归方式就不是那么容易了，当时我在实现的时候都卡了半天，真的是说起来容易做起来南啊，在实现遍历前我们首先要来实现的是栈，因为在非递归遍历的时候会用到栈，那到底什么是栈呢，这里我就简单介绍下吧，有兴趣的朋友可以去维基百科有权威的定义，栈和队列也是一种数据结构，栈存放数据的时候是先进先出，而队列是先进后出。

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