C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)

C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)

二叉树的性质:

二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子。

例:

实例代码:

#include <iostream>
#include <Windows.h>
#include <stack>
using namespace std; 

template <class T>
struct BinaryTreeNode
{
 int _data;
 BinaryTreeNode<T>* _left; //左孩子
 BinaryTreeNode<T>* _right;  //右孩子
 BinaryTreeNode(const T& data)
  :_data(data)
  , _left(NULL)
  , _right(NULL)
 {}
}; 

template <class T>
class BinaryTree
{
 typedef BinaryTreeNode<T> Node;
public:
 BinaryTree()
  :_root(NULL)
 {} 

 BinaryTree(T* arr, size_t n, const T& invalid=T())
 {
  size_t index = 0;
  _root = _CreatTree(arr, n, invalid, index);
 } 

 void PreOrderR()  //前序遍历 递归
 {
  _PreOrderR(_root);
 } 

 void PreOrder()  //前序遍历 非递归
 {
  _PreOrder(_root);
 } 

 void InOrderR() //中序遍历 递归
 {
  _InOrderR(_root);
 } 

 void InOrder()   //中序遍历  非递归
 {
  _InOrder(_root);
 } 

 void PostOrderR()  //后序遍历 左 右 根  递归
 {
  _PostOrderR(_root);
 } 

 void PostOrder()  //后序遍历 左 右 根  非递归
 {
  _PostOrder(_root);
 } 

 ~BinaryTree()
 {} 

protected:
 //建树 arr:建树使用的数组 n:数组大小 invalid:非法值 index:当前下标
 Node* _CreatTree(T* arr, size_t n, const T& invalid, size_t& index)
 {
  Node* root = NULL;
  if (index < n && arr[index] != invalid)
  {
   root = new Node(arr[index]); //根节点
   root->_left = _CreatTree(arr, n, invalid, ++index);
   root->_right = _CreatTree(arr, n, invalid, ++index);
  }
  return root;
 } 

 void _PreOrderR(Node* root)  //前序遍历 递归
 {
  if (root == NULL)
  {
   return;
  }
  cout << root->_data << " ";
  _PreOrderR(root->_left);
  _PreOrderR(root->_right);
 } 

 void _PreOrder(Node* root)  //前序遍历 非递归
 {
  stack<Node*> tty;
  while (root != NULL || !tty.empty())
  {
   if (root)
   {
    cout << root->_data << " ";
    tty.push(root);
    root = root->_left;
   }
   else
   {
    Node* temp = tty.top();
    tty.pop();
    root = temp->_right;
   }
  }
 } 

 void _InOrderR(Node* root) //中序遍历 递归
 {
  if (root == NULL)
  {
   return;
  }
  _InOrderR(root->_left);
  cout << root->_data << " ";
  _InOrderR(root->_right);
 } 

 void _InOrder(Node* root) //中序遍历 非递归
 {
  if (root == NULL)
  {
   return;
  }
  stack<Node*> tty;
  while (root != NULL || !tty.empty())
  {
   while (root)
   {
    tty.push(root);
    root = root->_left;
   }
   //此时出了循环走到了最左叶子节点
   Node* temp = tty.top();
   tty.pop();
   cout << temp->_data << " ";
   root = temp->_right;
  }
 } 

 void _PostOrderR(Node* root)  //后序遍历 左 右 根  递归
 {
  if (root == NULL)
  {
   return;
  }
  _PostOrderR(root->_left);
  _PostOrderR(root->_right);
  cout << root->_data << " ";
 } 

 void _PostOrder(Node* root)  //后序遍历 左 右 根  非递归
 {
  if (root == NULL)
  {
   return;
  }
  stack<Node*> tty;
  Node* PreNode = NULL; //上一个访问的结点
  tty.push(root);
  while (!tty.empty())
  {
   Node* cur = tty.top();
   //访问的当前节点左右孩子均为空或者当前节点左右子树均已经访问过
   if ((cur->_left == NULL && cur->_right == NULL) || ((PreNode != NULL) && (PreNode == cur->_left || PreNode == cur->_right)))
   {
    cout << cur->_data << " ";
    tty.pop();
    PreNode = cur;
   }
   else
   {
    if (cur->_right != NULL)
    {
     tty.push(cur->_right);
    }
    if (cur->_left != NULL)
    {
     tty.push(cur->_left);
    }
   }
  }
 } 

protected:
 Node* _root;
};
#include "源.h" 

void Test()
{
 int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
 BinaryTree<int> p(array, sizeof(array) / sizeof(array[0]), '#');
 cout << "前序递归遍历: " << "";
 p.PreOrderR();
 cout << endl; 

 cout << "前序非递归遍历: " << "";
 p.PreOrder();
 cout << endl; 

 cout << "中序递归遍历: " << "";
 p.InOrderR();
 cout << endl; 

 cout << "中序非递归遍历: " << "";
 p.InOrder();
 cout << endl; 

 cout << "后序递归遍历: " << "";
 p.PostOrderR();
 cout << endl; 

 cout << "后序非递归遍历: " << "";
 p.PostOrder();
 cout << endl;
} 

int main()
{
 Test();
 system("pause");
 return 0;
}

实现效果:

以上就是数据结构二叉树的详解,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

    本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法.分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> using std::cout; using std::cin; using std::endl; using std::stack; /*二叉树结点定义*/

  • C++非递归建立二叉树实例

    本文实例讲述了C++非递归建立二叉树的方法.分享给大家供大家参考.具体分析如下: 思路: 设置一个标记变量flag并初始化为1. flag = 1表示现在需要创建当前结点的左孩子,2表示需要创建右孩子,3则表示当前结点的左右孩子都已经创建完毕,需要执行出栈操作,直到当前结点不是父结点的右孩子为止. 以先序创建如图所示二杈树: 实现代码: PBTree create() { char ch[20]; scanf("%s",ch); int len = strlen(ch); PBTree

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C++基于递归和非递归算法求二叉树镜像的方法

    本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st

  • 数据结构 二叉树的递归与非递归

    数据结构 二叉树的递归与非递归 实例代码: #include <iostream> #include <queue> #include <stack> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T

  • C++非递归队列实现二叉树的广度优先遍历

    本文实例讲述了C++非递归队列实现二叉树的广度优先遍历.分享给大家供大家参考.具体如下: 广度优先非递归二叉树遍历(或者说层次遍历): void widthFirstTraverse(TNode* root) { queue<TNode*> q; // 队列 q.enqueue(root); TNode* p; while(q.hasElement()) { p = q.dequeue(); // 队首元素出队列 visit(p); // 访问p结点 if(p->left) q.enqu

  • C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

    本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同.分享给大家供大家参考,具体如下: /*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二

  • C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • Python 递归式实现二叉树前序,中序,后序遍历

    目录 1.前序遍历 2.中序遍历 3.后序遍历 4.测试 5.结果 6.补充 6.1N叉树前序遍历 记忆点: 前序:VLR 中序:LVR 后序:LRV 举例: 一颗二叉树如下图所示: 则它的前序.中序.后序遍历流程如下图所示: 1.前序遍历 class Solution:     def preorderTraversal(self, root: TreeNode):              def preorder(root: TreeNode):             if not ro

  • C++二叉树的前序中序后序非递归实现方法详细讲解

    目录 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 总结 二叉树的前序遍历 前序遍历的顺序是根.左.右.任何一颗树都可以认为分为左路节点,左路节点的右子树.先访问左路节点,再来访问左路节点的右子树.把访问左路节点的右子树看成一个子问题,就可以完整递归访问了. 先定义栈st存放节点.v存放值,TreeNode* cur,cur初始化为root. 当cur不为空或者栈不为空的时候(一开始栈是空的,cur不为空),循环继续:先把左路节点存放进栈中,同时把值存入v中,一直循环,直到此时的左路节点

  • Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

    本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

  • 深入遍历二叉树的各种操作详解(非递归遍历)

    先使用先序的方法建立一棵二叉树,然后分别使用递归与非递归的方法实现前序.中序.后序遍历二叉树,并使用了两种方法来进行层次遍历二叉树,一种方法就是使用STL中的queue,另外一种方法就是定义了一个数组队列,分别使用了front和rear两个数组的下标来表示入队与出队,还有两个操作就是求二叉树的深度.结点数... 复制代码 代码如下: #include<iostream>#include<queue>#include<stack>using namespace std;/

  • C++ 中二分查找递归非递归实现并分析

    C++ 中二分查找递归非递归实现并分析 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x) { asse

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

    如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

  • c语言版本二叉树基本操作示例(先序 递归 非递归)

    复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

  • PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

随机推荐