递归与非递归实现二叉树-创新互联
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^(i - 1)个结点;深度为k的二叉树至多有2^k - 1个结点。由于树的定义是递归实现的,所以在进行二叉树的前序、中序和后序遍历可通过递归实现,但也可通过非递归的栈来实现,二叉树的层次遍历可通过队列实现。
目前创新互联已为上千多家的企业提供了网站建设、域名、虚拟主机、成都网站托管、企业网站设计、白沙黎族网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。下面我对二叉树及前序、中序、后序遍历二叉树等方法进行实现
例如二叉树:
测试用例:
int arrary[10] = {1,2,3,'$','$',4,'$','$',5,6};
arrary为上图所示二叉树,通过前序存储的,'$'表示非法值,即没有结点
二叉树的结构:
templatestruct BinaryTreeNode { BinaryTreeNode * _left; BinaryTreeNode * _right; T _data; BinaryTreeNode(); BinaryTreeNode(const T& x); }; template class BinaryTree { typedef BinaryTreeNode Node; public: BinaryTree(); BinaryTree(const T* a, size_t size, const T& invalid); BinaryTree(const BinaryTree & t); BinaryTree & operator=(BinaryTree t); ~BinaryTree(); void PrevOrder();//前序遍历-递归 void InOrder();//中序遍历-递归 void PostOrder();//后序遍历-递归 void PrevOrder_NonR();//前序遍历-非递归 void InOrder_NonR();//中序遍历-非递归 void PostOrder_NonR();//后序遍历-非递归 void LevelOrder();//层次遍历 size_t Size();//结点个数 size_t Depth();//树的深度 size_t LeafSize();//叶子结点个数 size_t GetkLevel();//第k层结点个数 protected: Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid);//树的建立 Node* _CopyTree(Node* t);//复制树 void _Distory(Node* root);//清空结点,先释放子树,再释放根结点 void _PrevOrder(Node* root);//前序遍历 void _InOrder(Node* root);//中序遍历 void _PostOrder(Node* root);//后序遍历 size_t _Size(Node* root);//结点个数 size_t _Depth(Node* root);//树的深度 //size_t _LeafSize(Node* root);//叶子结点个数 size_t _LeafSize(Node* root,size_t& size);//叶子结点个数 //size_t _GetkLevel(int k, Node* root);//第k层结点个数 size_t _GetkLevel(int k, Node* root, int& size, int level);//第k层结点个数 private: Node* _root;// BinaryTreeNode * _root; };
二叉树的构造、拷贝构造、赋值运算和析构的实现,由于二叉树存在左子树和右子树,故用递归实现其功能,具体实现如下:
templateBinaryTreeNode ::BinaryTreeNode() :_left(NULL) , _right(NULL) , _data(0) {} template BinaryTreeNode ::BinaryTreeNode(const T& x) : _left(NULL) , _right(NULL) , _data(x) {} template BinaryTree ::BinaryTree() :_root(NULL) {} template BinaryTree ::~BinaryTree() { _Distory(_root); } template void BinaryTree ::_Distory(Node* root)//清空结点,先释放子树,再释放根结点 { if (root == NULL) { return; } if (root->_left)//递归释放子结点 { _Distory(root->_left); } if (root->_right) { _Distory(root->_right); } delete root; root = NULL; } template BinaryTree ::BinaryTree(const T* a, size_t size, const T& invalid) { size_t index = 0;//标记数组下标 _root = _CreateTree(a, size, index, invalid); } template BinaryTreeNode * BinaryTree ::_CreateTree(const T* a, size_t size, size_t& index, const T& invalid)//树的建立 { Node* root = NULL; if (index < size && a[index] != invalid)//indx _left = _CreateTree(a, size, ++index, invalid);//左子树递归 root->_right = _CreateTree(a, size, ++index, invalid);//右子树递归 } return root; } template BinaryTree ::BinaryTree(const BinaryTree & t) { _root = _CopyTree(t._root); } template BinaryTreeNode * BinaryTree ::_CopyTree(Node* t)//此处的返回类型不能用Node表示 { Node* root = NULL; if (t != NULL) { root = new Node(t->_data); root->_left = _CopyTree(t->_left); root->_right = _CopyTree(t->_right); } return root; } template BinaryTree & BinaryTree ::operator=(BinaryTree t)//现代写法 { if (this != &t) { BinaryTree tmp = t; swap(_root, tmp._root); } return *this; }
前序遍历(先根遍历):(1)先访问根节点;(2)前序访问左子树;(3)前序访问右子树.【1 2 3 4 5 6】
下面分别用递归和非递归两种方法实现。
二叉树的递归实现前序遍历
//递归实现 templatevoid BinaryTree ::PrevOrder()//前序遍历(先根结点) { _PrevOrder(_root); } template void BinaryTree ::_PrevOrder(Node* root) { if (root == NULL) { return; } cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); }
二叉树的非递归实现前序序列,利用栈实现。
由于栈是后进先出,对于二叉树的前序遍历先访问左子树后访问右子树,故右结点比左结点先进栈
//非递归实现(利用栈实现) templatevoid BinaryTree ::PrevOrder_NonR()//前序遍历-非递归 { stack s; if (_root) { s.push(_root); } while (!s.empty()) { Node* top = s.top();//访问栈顶元素 cout << top->_data << " "; s.pop(); //右结点比左结点先进栈 if (top->_right) { s.push(top->_right); } if (top->_left) { s.push(top->_left); } } cout << endl; }
中序遍历:(1)中序访问左子树;(2)访问根节点;(3)中序访问右子树.【3 2 4 1 6 5】
下面分别用递归和非递归两种方法实现
二叉树的递归实现中序序列
templatevoid BinaryTree ::InOrder()//中序遍历(中根结点) { _InOrder(_root); } template void BinaryTree ::_InOrder(Node* root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); }
二叉树的非递归实现中序序列
//非递归实现(利用栈实现) templatevoid BinaryTree ::InOrder_NonR()//中序遍历-非递归 { if (_root == NULL) { return; } stack s; Node* cur = _root; while (cur || !s.empty()) { //压一棵树的左结点,直到最左结点 while (cur) { s.push(cur); cur = cur->_left; } if (!s.empty()) { Node* top = s.top(); cout << top->_data << " "; s.pop(); cur = top->_right;//使cur指向最左结点top的右结点 } } cout << endl; }
后序遍历(后根遍历):(1)后序访问左子树;(2)后序访问右子树;(3)访问根节点.【3 4 2 6 5 1】
下面分别用递归和非递归两种方法实现
二叉树的递归实现后序序列
//递归实现 templatevoid BinaryTree ::PostOrder()//后序遍历(后根结点) { _PostOrder(_root); } template void BinaryTree ::_PostOrder(Node* root)//后序遍历 { if (root == NULL) { return; } _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } //非递归实现(利用栈实现)
二叉树的非递归实现后序序列
templatevoid BinaryTree ::PostOrder_NonR()//后序遍历-非递归 { if (_root == NULL) { return; } stack s; Node* cur = _root; Node* prev = NULL; while (cur || !s.empty()) { //压一棵树的左结点,直到最左结点 while (cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); if (top->_right == NULL || top->_right == prev) { cout << top->_data << " "; s.pop(); prev = top; } else//当未访问过栈顶的右子树,则继续右子树的访问 { cur = top->_right; } cout << endl; } }
层序遍历:一层层节点依次遍历。【1 2 5 3 4 6】
下面用非递归方法实现,利用队列进行访问。
//递归实现 templatevoid BinaryTree ::LevelOrder()//层次遍历,通过队列实现 { queue q;//建立队列存放Note*类型值 if (_root != NULL) { q.push(_root); } while (!q.empty()) { Node* front = q.front(); cout << front->_data << " ";//访问队头 q.pop();//队头出队列 if (front->_left != NULL)//存在左或右结点入队列 { q.push(front->_left); } if (front->_right != NULL) { q.push(front->_right); } } cout << endl; }
求树的结点个数,递归实现:
templatesize_t BinaryTree ::Size()//结点个数 { return _Size(_root); } template size_t BinaryTree ::_Size(Node* root) { if (root == NULL) { return 0; }//root不为0,则Size+1 return _Size(root->_left) + _Size(root->_right) + 1; }
求树的深度,递归实现:
templatesize_t BinaryTree ::Depth()//树的深度 { return _Depth(_root); } template size_t BinaryTree ::_Depth(Node* root) { if (root == NULL) { return 0; } size_t LeftDepth = _Depth(root->_left); size_t RightDepth = _Depth(root->_right); if (LeftDepth > RightDepth)//root不为0,则深度+1 { return LeftDepth + 1; } else { return RightDepth + 1; } }
求树的叶子结点个数,递归实现:
//方法一 templatesize_t BinaryTree ::LeafSize()//叶子结点个数 { return _LeafSize(_root); } template size_t BinaryTree ::_LeafSize(Node* root) { if (root == 0) { return 0; } if (root->_left == 0 && root->_right == 0) { return 1; } return _LeafSize(root->_left) + _LeafSize(root->_right); } //方法二:在LeafSize中定义_size表示叶子结点个数 template size_t BinaryTree ::LeafSize()//叶子结点个数 { size_t _size = 0; return _LeafSize(_root, _size); } template size_t BinaryTree ::_LeafSize(Node* root, size_t& size) { if (root == 0) { return 0; } if (root->_left == 0 && root->_right == 0) { ++size; return size; } _LeafSize(root->_left, size); _LeafSize(root->_right, size); return size; }
二叉树中第k层结点的个数,递归实现:
//方法一 templatesize_t BinaryTree ::GetkLevel(int k) { assert(k>0); return _GetkLevel(k, _root); } template size_t BinaryTree ::_GetkLevel(int k, Node* root)//第k层结点个数 { if (root == NULL) { return 0; } if (k == 1)//利用递归使k递减,k==1结束 { return 1; } size_t size1 = _GetkLevel(k - 1, root->_left); size_t size2 = _GetkLevel(k - 1, root->_right); return size1 + size2; } //方法二:在GetkLevel中定义size表示第k层结点个数 template size_t BinaryTree ::GetkLevel(int k) { assert(k > 0); int size = 0;//size为二叉树第level层结点个数 int level = 1;//第level层 return _GetkLevel(k, _root, size, level); } template size_t BinaryTree ::_GetkLevel(int k, Node* root, int& size, int level)//第k层结点个数 { if (root == NULL) { return 0; } if (level == k) { ++size; return size; } _GetkLevel(k, root->_left, size, level+1); _GetkLevel(k, root->_right, size, level+1); return size; }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻标题:递归与非递归实现二叉树-创新互联
链接分享:http://scyanting.com/article/ddsssd.html