首页 > 二叉树(C++)：创建，前中后序遍历（递归+非递归），获取叶子节点个数，获取树的高度

二叉树(C++)：创建，前中后序遍历（递归+非递归），获取叶子节点个数，获取树的高度

文章目录

        • 前言
        • 创建二叉树
        • 先序遍历
        • 中序遍历
        • 后序遍历
        • 获取叶子节点个数
        • 获取树的高度
        • 测试代码

前言

现有如下二叉树:

在这里插入图片描述

关于二叉树的相关操作，我们能够发现二叉树从根节点到子节点，以及每个中间节点基本都能够拆分为若干个子节点的操作，且每个子节点的操作都和其头节点操作一致。

所以我们针对二叉树的操作都可以使用分治算+回溯/归并算法进行

完整测试代码见文末

创建二叉树

二叉树数据结构:

typedef struct tree
{ char data;struct tree *left;struct tree *right;
}Tree,*TreeNode;

我们使用先序方式，创建如上二叉树：

输入如下: ABD***CE**FG***

创建过程

/*创建二叉树*/
void createTree(TreeNode *root) { char val = 0;cin >> val; //持续输入，直到完成一个二叉树的构建if (val == '*') { //输入为*则代表当前节点为空(*root) = NULL;} else { (*root) = (Tree *)malloc(sizeof(tree));if ((*root) == NULL) { cout << "create node failed " << endl;exit(-1);} else { (*root)->data = val;//为输入的节点赋值createTree(&(*root)->left);//分治左孩子节点createTree(&(*root)->right);//分治右孩子节点}}
}

先序遍历

先序遍历二叉树指:先遍历二叉树的根节点，再遍历当前根节点所有左子树，再遍历当前根节点所有右子树

因为这个过程针对子节点的遍历和根节点是没有任何区别的，所以可以使用分治进行处理

/*递归先序遍历*/
void preOrder(Tree *root) { if (root == NULL) { return;}cout << root->data;preOrder(root->left);preOrder(root->right);
}

同样可以使用栈进行非递归的先序遍历,即

栈可以保存遍历过程中的左节点，因为先序遍历是先访问根节点，其次就是左节点

while(p) { cout << p ->data; //访问根节点s.push(p); //保存左子节点p = p->left;
}

接着再弹栈，直到获取一个右节点

while(!s.empty()) { p = s.top();s.pop();p = p -> right;
}

接着再重复对右节点进行同样的访问操作，具体过程如下

/*非递归先序遍历*/
void preOrderNoRecur(Tree *root) { if (root == NULL) { return;}stack<TreeNode> s;Tree *p = root;while(!s.empty() || p) { while(p) { cout << p ->data;s.push(p);p = p->left;}while(!s.empty()) { p = s.top();s.pop();p = p -> right;}}cout << endl;
}

中序遍历

中序遍历二叉树是指：先访问左节点，中间访问根节点，最后访问右节点

分治过程如下:

void inorder(Tree *root) { if (root == NULL) { return;}inorder(root -> left);cout << root -> data;inorder(root -> right);
}

中序遍历二叉树的非递归方式和先序类似，支持访问的时机是在先访问第一轮所有的左节点，再获取右节点之前进行根节点的访问，实现过程如下:

/*非递归中序遍历*/
void inorderNoRecur(Tree *root) { if (root == NULL) { return;}stack<TreeNode> s;Tree *p = root;while(!s.empty() || p) { while(p) { s.push(p);p = p ->left;}while(!s.empty()) { p = s.top();cout << p->data;s.pop();p = p->right;}}cout << endl;
}

后序遍历

后序遍历二叉树是指：先访问左节点，再访问右节点，最后访问根节点

分治过程如下:

/*递归后序遍历*/
void lastorder(Tree *root) { if (root == NULL) { return;}lastorder(root -> left);lastorder(root -> right);cout << root -> data;
}

非递归的访问过程和先序/中序遍历有差异，因为后序遍历需要优先访问完左节点、右节点

所以根节点的访问前提是：

  1. 右子节点为空
  2. 右子节点已经访问过

所以实现的过程中需要保存已经访问过的右子节点

void lastorderNoRecur(Tree *root) { if (root == NULL) { return;}stack<TreeNode> s;Tree *p = root;Tree *lastvisit = NULL;//保存已经访问过的右子节点/*先获取到左子节点*/while(p) { s.push(p);p = p ->left;}while(!s.empty()) { p = s.top();s.pop();/*右节点已经为空或者已经访问过，那么认为右节点已经访问完，可以访问根节点了*/if (p -> right == NULL || p ->right == lastvisit) { cout << p->data;lastvisit = p;} else { //否则，将右节点以及右节点的子节点入栈从而继续访问s.push(p);p = p -> right;/*每获取到一个非空右节点，就将该右节点的左节点放入栈中*/while(p) { s.push(p);p = p -> left;}}}cout << endl;
}

获取叶子节点个数

叶子节点的条件就是：左右子树都为空

此时返回值应该为1

分治+归并获取叶子节点的个数

int getLeavesNode(Tree *root) { if (root == NULL) { return 0;} else { if (root -> left == NULL && root ->right == NULL) { return 1;}return getLeavesNode(root -> left) + getLeavesNode(root -> right);}
}

获取树的高度

树的高度为左右子节点的 层数较大的一个数值

实现过程如下:

int heightTree(Tree *root) { int height = 0;if (root == NULL) { return 0;} else { int l_height = heightTree(root -> left);int r_height = heightTree(root -> right);height = l_height > r_height? l_height +1 :r_height+1;}return height;
}

测试代码

#include 
#include 
#include 
#include 
#include 
#include using namespace std;typedef struct tree
{ char data;struct tree *left;struct tree *right;
}Tree,*TreeNode;/*创建二叉树*/
void createTree(TreeNode *root) { char val = 0;cin >> val;if (val == '*') { (*root) = NULL;} else { (*root) = (Tree *)malloc(sizeof(tree));if ((*root) == NULL) { cout << "create node failed " << endl;exit(-1);} else { (*root)->data = val;createTree(&(*root)->left);createTree(&(*root)->right);}}
}/*递归先序遍历*/
void preOrder(Tree *root) { if (root == NULL) { return;}cout << root->data;preOrder(root->left);preOrder(root->right);
}/*非递归先序遍历*/
void preOrderNoRecur(Tree *root) { if (root == NULL) { return;}stack<TreeNode> s;Tree *p = root;while(!s.empty() || p) { while(p) { cout << p ->data;s.push(p);p = p->left;}while(!s.empty()) { p = s.top();s.pop();p = p -> right;}}cout << endl;}/*递归中序遍历*/
void inorder(Tree *root) { if (root == NULL) { return;}inorder(root -> left);cout << root -> data;inorder(root -> right);
}/*非递归中序遍历*/
void inorderNoRecur(Tree *root) { if (root == NULL) { return;}stack<TreeNode> s;Tree *p = root;while(!s.empty() || p) { while(p) { s.push(p);p = p ->left;}while(!s.empty()) { p = s.top();cout << p->data;s.pop();p = p->right;}}cout << endl;
}/*递归后序遍历*/
void lastorder(Tree *root) { if (root == NULL) { return;}lastorder(root -> left);lastorder(root -> right);cout << root -> data;
}void lastorderNoRecur(Tree *root) { if (root == NULL) { return;}stack<TreeNode> s;Tree *p = root;Tree *lastvisit = NULL;while(p) { s.push(p);p = p ->left;}while(!s.empty()) { p = s.top();s.pop();/*右节点已经为空或者已经访问过，那么认为右节点已经访问完，可以访问根节点了*/if (p -> right == NULL || p ->right == lastvisit) { cout << p->data;lastvisit = p;} else { //否则，将右节点以及右节点的子节点入栈从而继续访问s.push(p);p = p -> right;while(p) { s.push(p);p = p -> left;}}}cout << endl;
}int getLeavesNode(Tree *root) { if (root == NULL) { return 0;} else { if (root -> left == NULL && root ->right == NULL) { return 1;}return getLeavesNode(root -> left) + getLeavesNode(root -> right);}
}int heightTree(Tree *root) { int height = 0;if (root == NULL) { return 0;} else { int l_height = heightTree(root -> left);int r_height = heightTree(root -> right);height = l_height > r_height? l_height +1 :r_height+1;}return height;
}int main(int argc, char const *argv[])
{ /* code */TreeNode root;cout << "construct the tree " << endl;createTree(&root);cout << "previous order recursion " << endl;preOrder(root);cout << "
previous order no recursion " << endl;preOrderNoRecur(root);cout << "inorder recursion " << endl;inorder(root);cout << "
inorder no recursion " << endl;inorderNoRecur(root);cout << "lastorder recursion " << endl;lastorder(root);cout << "
lastorder no recursion " << endl;lastorderNoRecur(root);cout << "height of the tree is " << heightTree(root) << endl;cout << "num leaves of the tree is " << getLeavesNode(root) << endl;return 0;
}

输出如下:

#输入
construct the tree 
ABD***CE**FG***
#输出
previous order recursion 
ABDCEFG
previous order no recursion 
ABDCEFG
inorder recursion 
DBAECGF
inorder no recursion 
DBAECGF
lastorder recursion 
DBEGFCA
lastorder no recursion 
DBEGFCA
height of the tree is 4
num leaves of the tree is 3

更多相关：

  • 在Ubuntu 12.04 64bit上搭建Crtmpserver视频点播服务

    说明如下： (1)所有操作最好使用root操作，以尽可能避免权限问题 (2)crtmpserver和web服务器apache（Ngnix亦可）被装在同一台服务器上，客户端使用其他PC的桌面浏览器和android手机，下面是测试环境示意图： (3)测试环境位于局域网内，由一台路由器接入联通运营商提供的10M包年网络服务 (...

  • Linux 的内存管理工具和调优参数

    1. free 2. top 3. vmstat 4. slabtop; 5. pmap 6. dmesg 7. /proc/meminfo 8. /proc/sys/vm 目录下的文件 9. sync 10./proc/zoneinfo  11./proc/pagetypeinfo 查看内存工具：1.free free - Dis...

  • ceph-deploy rpm包的制作

    今天需要部署一个ceph L 版本12.2.12的环境，无奈最近公司网络无法访问到ceph官网，只能使用之前下载好的ceph-deploy-1.5.39版本，安装上之后一口老血喷了出来，没有mgr的部署选项。 无奈之下只能自己制作一个1.5.38版本的ceph-deploy包，借用从ceph-deploy-1.5.39-0.src....

  • MySQL 解压版创建用户密码

    root 权限进入MySQL： mysql –uroot 查看当前MySQL用户： select user,host from mysql.user;     此处以User为root，Host为localhost的账户为例，将密码改为password的命令：   SET PASSWORD FOR 'root'@'localhost...

  • 边缘计算架构_Openshift为边缘计算提供三节点架构部署

    当一个IT组织开始走到需要实施网络边缘的旅程时，他们很快意识到面对的挑战与他们在传统数据中心内所经历的挑战不同。 第一个挑战是空间。与更大的核心或区域数据中心同类产品相比，许多边缘站点的物理尺寸更小，因此，需要仔细计划好，尝试在未为其专门设计的空间中安装硬件。  第二个挑战是运行环境。还必须解决的可能面对的冷热温度变化 ，天气，无...

  • node 获取表单数据 为空_数据结构与算法(python)单向循环链表

    单向循环链表单链表的一个变形是单向循环链表, 链表的最后一个节点的next域不再为None, 而是指向链表的头节点.单向循环链表如图所示:单向循环链表同样单向循环链表也是要使用python来对它的基本功能进行一个封装. 总体大致的功能如下:is_empty() 判断链表是否为空length() 返回链表的长度travel() 遍历ad...

  • 剑指offer：面试题36. 二叉搜索树与双向链表

    题目： 二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一...

  • 剑指offer：面试题18. 删除链表的节点

    题目：删除链表的节点 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 注意：此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为...

  • 从零开始的ROS四轴机械臂控制-目录

    【从零开始的ROS四轴机械臂控制】（一）- 实际模型制作、Solidworks文件转urdf与rviz仿真 一、模型制作 1.实际模型制作 2.Solidworks模型制作 二、Solidworks文件转urdf 1.sw_urdf_exporter插件 2.添加坐标系和转轴 3.导出urdf文件 三、rivz仿真...

  • c++关于map的find和count的使用

    使用count，返回的是被查找元素的个数。如果有，返回1；否则，返回0。注意，map中不存在相同元素，所以返回值只能是1或0。 使用find，返回的是被查找元素的位置，没有则返回map.end()。 #include #include #include #include

  • 高精度的除法

    1 //改代码用于精确计算除法的位数，比如求无限循环小数的循环节 2 //求循环节时，需要定义一个数组，用与标记是否有相同的余数，若是遇到时，结束循环，即得到循环节 3 #include 4 using namespace std; 5 6 int main() { 7 int a, b...

  • 机器学习简单代码示例

    机器学习简单代码示例 　　 //在gcc-4.7.2下编译通过。 //命令行：g++ -Wall -ansi -O2 test.cpp -o test #include using namespace std; void input(int &oper,const bool meth) {//meth为true...

©2024 11GX.COM