二叉树详解及二叉树的遍历（递归与非递归C++算法实现） _非递归

莫问天涯路几重，轻衫侧帽且从容。这篇文章主要讲述二叉树详解及二叉树的遍历（递归与非递归C++算法实现）相关的知识，希望能为你提供帮助。
?# 二叉树详解及二叉树的遍历（递归与非递归C++算法实现）
二叉树简介树（Tree）
是一种由多个节点组成的有限集合T，有且仅有一个节点称为根（root），其余结点分为m（大于等于0）个互不相交的有限集合T1，T2,T3...; 每个集合本身又是棵树，被称为这个根的子树。
在树的定义中规定了树含有结点数必须大于0，这表明空集不可以称为树；他又规定结点可以为1，该结点就是根节点。
节点、根节点、父节点、子节点、兄弟节点
② 一棵树可以没有任何节点，成为空树
③ 一棵树可以只有1个节点，也就是只有根节点
④ 子树、左子树、右子树
⑤ 节点的度(degree)：子树的个数
⑥ 树的度：所有节点度中的最大值
⑦ 叶子节点(leaf): 度为0的节点
⑧ 非叶子节点：度不为0的节点
树的存储结构

结点异构型

根据结点的子树数设置相应的指针域，同时在结点的数据中再增加一个表示结点的度的域，以了解这个结点具有的指针域。

结点同构型

以这棵树的度作为结点的指针域数目，每个结点的长度一样，但是树中很多结点的度小于树的度，导致存储浪费。
二叉树(Binary Tree)
二叉树的特点

每个节点的度最大为2(最多拥有2棵子树)
左子树和右子树是有顺序的
即使某节点只有一颗子树，也要区分左右子树。

二叉树具有五种基本形态：

空二叉树。
只有一个根节点
根节点只有左子树
根节点只有右子树
根节点既有左子树又有右子树。

满二叉树
在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点有：

叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
非叶子结点的度一定是2。
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多

文章图片

完全二叉树
对一颗具有n个结点的二叉树按层编号，如果编号为i(1< =i< =n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

文章图片

二叉树的基本性质

【二叉树详解及二叉树的遍历（递归与非递归C++算法实现）】二叉树的第i层至多有2^(n-1)个结点；
深度为k的二叉树至多有2^k - 1个结点
对任意一颗二叉树，若2度结点数为N2 ,则叶子数为 N0 = N2 + 1;

完全二叉树的重要性质：

在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[x]是向下取整。
若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点; (2) 若 2i> n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1> n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。

二叉树的遍历（递归与非递归C++算法实现）先序遍历
遍历顺序：

先访问根结点
先序遍历左子树
先序遍历右子树

文章图片

文章图片

```c++
/**

非递归实现先序遍历
先访问根结点，再访问左子树，再访问右子树
@param root 根结点
/
void pre_traversal(BTreeNode root)
stack< BTreeNode*> node_stack; //用来暂存节点的栈
while (root != nullptr || !node_stack.empty())
if (root != nullptr)//若当前的节点非空，
cout < < root-> val < < " " ; //则输出该节点的值
node_stack.push(root); //该节点压入栈中。
root = root-> leftchild; // 我们继续向左子树前进

else
root = node_stack.top();
node_stack.pop();
root = root-> rightchild;

/**

递归实现先序遍历
先访问根结点，再访问左子树，再访问右子树
@param root 根结点
/
void PreOrder(BTreeNode root)
if(root!=NULL)
visit(root);
PreOrder(root-> leftchild);
PreOrder(root-> rightchild);

中序遍历
按照以下顺序进行遍历

中序遍历左子树
访问根结点
中序遍历右子树

文章图片

```c++
/**

非递归实现中序遍历
先访问左子树，再访问根结点，再访问右子树
通过栈来存储二叉树结点
@param root 根结点
/
void in_traversal(BTreeNode root)
stack< BTreeNode*> stack_node;
while (root != nullptr || !stack_node.empty())
if (root != nullptr)
stack_node.push(root);
root = root-> leftchild;

else
root = stack_node.top();
cout < < root-> val < < " " ;
stack_node.pop();
root = root-> rightchild;

/**

递归实现中序遍历
先访问左子树，再访问根结点，再访问右子树
@param root 根结点
/
void InOrder(BTreeNode root)
if(root!=NULL)
InOrder(root-> leftchild);
visit(root);
InOrder(root-> rightchild);

后序遍历
按照以下顺序进行遍历

后序遍历左子树
后序遍历右子树
访问根节点

文章图片

```c++
/**

非递归实现后序遍历
先访问左子树，再访问右子树，再访问根结点
通过栈来存储二叉树结点
@param root 根结点
/
void post_traversal(BTreeNode root)
stack< BTreeNode> stack_node;
BTreeNode lastvisit = root;
while (root != nullptr || !stack_node.empty())
if (root != nullptr)
stack_node.push(root);
root = root-> leftchild;

else
root = stack_node.top();
if (root-> rightchild == nullptr || root-> rightchild == lastvisit)

cout < < root-> val < < " "; stack_node.pop(); lastvisit = root; root = nullptr; else root = root-> rightchild;

/**

递归实现后序遍历
先访问左子树，再访问右子树，再访问根结点
@param root 根结点
/
void PostOrder(BTreeNode root)
if(root!=NULL)
PostOrder(root-> leftchild);
PostOrder(root-> rightchild);
visit(root);

层次遍历
```c++
void LevelOrder(BTreeNode root)
BTreeNode p; // 创建辅助队列
queue< BTreeNode*> q;
q.push(root); //根结点入队
while(!q.empty())
p = q.front();
visit(p); //访问结点
q.pop(); //对头结点出队
if(p-> leftchild!=NULL)
q.push(p-> leftchild);

if(p-> rightchild!=NULL)
q.push(p-> rightchild);

### **遍历总结**：#### 结果：通过二叉树遍历规律得出的结果如下图所示：![在这里插入图片描述](https://s4.51cto.com/images/blog/202201/14151427_61e122d3e0f0c47685.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)#### 练习：这里给出另外一个二叉树及其先中后序遍历及层次遍历的结果，可以试着自己遍历试试看，是否得到同样的结果。 ![在这里插入图片描述](https://s4.51cto.com/images/blog/202201/14151428_61e122d41517d38988.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)### 代码实现通过运行代码实现效果如下所示：![在这里插入图片描述](https://s4.51cto.com/images/blog/202201/14151427_61e122d3e576187323.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)### 完整代码```c++ // // Created by caifl on 12/7/2021. // /** * 二叉树的先序、中序、后序、层序遍历思路及算法实现 */#include "iostream" #include "vector" #include "stack" #include "queue" using namespace std; struct BTreeNode//二叉树结点 int val; BTreeNode* leftchild; //左子树结点 BTreeNode* rightchild; //右子树结点 // 二叉树结点结构体构造函数 BTreeNode(char const& _val, BTreeNode* _leftchild=NULL, BTreeNode* _rightchild=NULL) : val(_val), leftchild(_leftchild), rightchild(_rightchild) ; /** * 访问结点值 * @param node 树结点 */ void visit(BTreeNode* node) cout< < char(node-> val)< < " "; /** * 非递归实现先序遍历 * 先访问根结点，再访问左子树，再访问右子树 * @param root 根结点 */ void pre_traversal(BTreeNode* root) stack< BTreeNode*> node_stack; //用来暂存节点的栈 while (root != nullptr || !node_stack.empty()) if (root != nullptr)//若当前的节点非空， visit(root); //则输出该节点的值 node_stack.push(root); //该节点压入栈中。 root = root-> leftchild; // 我们继续向左子树前进else root = node_stack.top(); node_stack.pop(); root = root-> rightchild; /** * 非递归实现中序遍历 * 先访问左子树，再访问根结点，再访问右子树 * 通过栈来存储二叉树结点 * @param root 根结点 */ void in_traversal(BTreeNode* root) stack< BTreeNode*> stack_node; while (root != nullptr || !stack_node.empty()) if (root != nullptr) stack_node.push(root); root = root-> leftchild; else root = stack_node.top(); visit(root); stack_node.pop(); root = root-> rightchild; /** * 非递归实现后序遍历 * 先访问左子树，再访问右子树，再访问根结点 * 通过栈来存储二叉树结点 * @param root 根结点 */ void post_traversal(BTreeNode* root) stack< BTreeNode*> stack_node; BTreeNode* lastvisit = root; while (root != nullptr || !stack_node.empty()) if (root != nullptr) stack_node.push(root); root = root-> leftchild; else root = stack_node.top(); if (root-> rightchild == nullptr || root-> rightchild == lastvisit) visit(root); stack_node.pop(); lastvisit = root; root = nullptr; else root = root-> rightchild; /** * 递归实现先序遍历 * 先访问根结点，再访问左子树，再访问右子树 * @param root 根结点 */ void PreOrder(BTreeNode* root) if(root!=NULL) visit(root); PreOrder(root-> leftchild); PreOrder(root-> rightchild); /** * 递归实现中序遍历 * 先访问左子树，再访问根结点，再访问右子树 * @param root 根结点 */ void InOrder(BTreeNode* root) if(root!=NULL) InOrder(root-> leftchild); visit(root); InOrder(root-> rightchild); /** * 递归实现后序遍历 * 先访问左子树，再访问右子树，再访问根结点 * @param root 根结点 */ void PostOrder(BTreeNode* root) if(root!=NULL) PostOrder(root-> leftchild); PostOrder(root-> rightchild); visit(root); /** * 层次遍历二叉树 */ void LevelOrder(BTreeNode* root) BTreeNode* p; // 创建辅助队列 queue< BTreeNode*> q; q.push(root); //根结点入队 while(!q.empty()) p = q.front(); visit(p); //访问结点 q.pop(); //对头结点出队 if(p-> leftchild!=NULL) q.push(p-> leftchild); if(p-> rightchild!=NULL) q.push(p-> rightchild); /** * 测试方法 */ void test() //构建二叉树 BTreeNode* A = new BTreeNode(A); BTreeNode* B = new BTreeNode(B); BTreeNode* C = new BTreeNode(C); BTreeNode* D = new BTreeNode(D); BTreeNode* E = new BTreeNode(E); BTreeNode* F = new BTreeNode(F); BTreeNode* G = new BTreeNode(G); BTreeNode* H = new BTreeNode(H); BTreeNode* I = new BTreeNode(I); BTreeNode* J = new BTreeNode(J); BTreeNode* K = new BTreeNode(K); A-> leftchild=B; A-> rightchild=C; B-> leftchild=D; B-> rightchild=E; C-> leftchild=F; C-> rightchild=G; D-> leftchild=H; D-> rightchild=I; E-> rightchild=J; F-> rightchild=K; /** * 非递归实现 */ cout< < "非递归实现："< < endl < < "Pre order traversal:" < < endl; pre_traversal(A); //先序遍历 cout < < endl< < "In order traversal:" < < endl; in_traversal(A); //中序遍历 cout < < endl < < "Post order traversal:" < < endl; post_traversal(A); //后序遍历/** * 递归实现 */ cout< < endl< < "递归实现"< < endl; cout< < "先序遍历："< < endl; PreOrder(A); cout< < endl< < "中序遍历："< < endl; InOrder(A); cout< < endl< < "后序遍历："< < endl; PostOrder(A); //层次遍历 cout< < endl< < "层次遍历："< < endl; LevelOrder(A);

Referencehttps://blog.csdn.net/chinesekobe/article/details/110874773