#include <iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef int TelemType;
typedef struct BinaryTreeNode
{
TelemType data;
struct BinaryTreeNode *Left;
struct BinaryTreeNode *Right;
}Node;
//创建二叉树,顺序依次为中间节点->左子树->右子树
Node* createBinaryTree()
{
Node *p;
TelemType ch;
cin>>ch;
if(ch == 0) //如果到了叶子节点,接下来的左、右子树分别赋值为0
{
p = NULL;
}
else
{
p = (Node*)malloc(sizeof(Node));
p->data = ch;
p->Left = createBinaryTree(); //递归创建左子树
p->Right = createBinaryTree(); //递归创建右子树
}
return p;
}
//先序遍历
void preOrderTraverse(Node* root)
{
if( root )
{
cout<<root->data<< "→"; //访问根节点
preOrderTraverse(root->Left); //先序遍历左子树
preOrderTraverse(root->Right); //先序遍历后子树
}
}
//中序遍历
void inOrderTraverse(Node* root)
{
if( root )
{
inOrderTraverse(root->Left); //左->中(根)->右
cout<<root->data<< "→";
inOrderTraverse(root->Right);
}
}
//后序遍历
void lastOrderTraverse(Node* root)
{
if( root )
{
lastOrderTraverse(root->Left); //左->右->中(根)
lastOrderTraverse(root->Right);
cout<<root->data<< "→";
}
}
//二叉树节点总数目
int Nodenum(Node* root)
{
if(root == NULL)
{
return 0;
}
else
{
return 1+Nodenum(root->Left)+Nodenum(root->Right);
//一个根节点加上左右子树上的节点为节点的总数
}
}
//二叉树叶子节点数
int Leafnum(Node* root)
{
if(!root)
{
return 0;
}
else if( (root->Left == NULL) && (root->Right == NULL) )
{
return 1;
}
else
{
return (Leafnum(root->Left) + Leafnum(root->Right)) ;
}
}
int main()
{
printf("请输入二叉树(输入0表示空域的值)(每个值之间要空格隔开):");
Node *root = NULL;
root = createBinaryTree();
printf("biu~二叉树建立成功");
cout<<endl;
cout<<"二叉树总节点数为:"<<Nodenum(root)<<endl;
cout<<"二叉树叶子节点数为:"<<Leafnum(root)<<endl;
cout<<"前序遍历结果:"<<endl;
preOrderTraverse(root);
cout<<endl;
cout<<"中序遍历结果:"<<endl;
inOrderTraverse(root);
cout<<endl;
cout<<"后序遍历结果:"<<endl;
lastOrderTraverse(root);
cout<<endl;
return 0;
}
二叉树的基本操作,想三种遍历的基础上想加一个层序遍历
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- threenewbee 2019-06-30 16:39关注
你的输入的顺序本身就是层序了,也就是说直接用数组记录下来再输出(去掉0)就可以了。
假设你希望在构造完树以后,再输出层序(而不是直接从输入的序列输出)
我给你写了一个参考代码,也就是根据你的树反推回去你输入的序列。
// Q767712.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include<cstdio> #include<cstdlib> using namespace std; typedef int TelemType; typedef struct BinaryTreeNode { TelemType data; struct BinaryTreeNode *Left; struct BinaryTreeNode *Right; }Node; //创建二叉树,顺序依次为中间节点->左子树->右子树 Node* createBinaryTree() { Node *p; TelemType ch; cin>>ch; if(ch == 0) //如果到了叶子节点,接下来的左、右子树分别赋值为0 { p = NULL; } else { p = (Node*)malloc(sizeof(Node)); p->data = ch; p->Left = createBinaryTree(); //递归创建左子树 p->Right = createBinaryTree(); //递归创建右子树 } return p; } //先序遍历 void preOrderTraverse(Node* root) { if( root ) { cout<<root->data<< "→"; //访问根节点 preOrderTraverse(root->Left); //先序遍历左子树 preOrderTraverse(root->Right); //先序遍历后子树 } } //中序遍历 void inOrderTraverse(Node* root) { if( root ) { inOrderTraverse(root->Left); //左->中(根)->右 cout<<root->data<< "→"; inOrderTraverse(root->Right); } } //后序遍历 void lastOrderTraverse(Node* root) { if( root ) { lastOrderTraverse(root->Left); //左->右->中(根) lastOrderTraverse(root->Right); cout<<root->data<< "→"; } } //二叉树节点总数目 int Nodenum(Node* root) { if(root == NULL) { return 0; } else { return 1+Nodenum(root->Left)+Nodenum(root->Right); //一个根节点加上左右子树上的节点为节点的总数 } } //二叉树叶子节点数 int Leafnum(Node* root) { if(!root) { return 0; } else if( (root->Left == NULL) && (root->Right == NULL) ) { return 1; } else { return (Leafnum(root->Left) + Leafnum(root->Right)) ; } } void ConvTree(Node * root, int id, TelemType ** data) { if( root ) { data[id] = &(root->data); ConvTree(root->Left, id * 2 + 1, data); ConvTree(root->Right, id * 2 + 2, data); } else { data[id] = NULL; } } void levelTraverse(Node * root) { TelemType* data[511]; int i; for (i = 0; i < 511; i++) data[i] = NULL; ConvTree(root, 0, data); for (i = 0; i < 511; i++) { if (data[i] != NULL) cout<<*(data[i])<< "→"; } } int main() { printf("请输入二叉树(输入0表示空域的值)(每个值之间要空格隔开):"); Node *root = NULL; root = createBinaryTree(); printf("biu~二叉树建立成功"); cout<<endl; cout<<"二叉树总节点数为:"<<Nodenum(root)<<endl; cout<<"二叉树叶子节点数为:"<<Leafnum(root)<<endl; cout<<"前序遍历结果:"<<endl; preOrderTraverse(root); cout<<endl; cout<<"中序遍历结果:"<<endl; inOrderTraverse(root); cout<<endl; cout<<"后序遍历结果:"<<endl; lastOrderTraverse(root); cout<<endl; cout<<"层序遍历结果:"<<endl; levelTraverse(root); cout<<endl; return 0; }
(有待改进:TelemType* data[511];最好不要用数组,而是链表来稀疏存储,这样效率更高)
运行截图
解决 无用评论 打赏 举报
悬赏问题
- ¥88 找成都本地经验丰富懂小程序开发的技术大咖
- ¥15 如何处理复杂数据表格的除法运算
- ¥15 如何用stc8h1k08的片子做485数据透传的功能?(关键词-串口)
- ¥15 有兄弟姐妹会用word插图功能制作类似citespace的图片吗?
- ¥200 uniapp长期运行卡死问题解决
- ¥15 请教:如何用postman调用本地虚拟机区块链接上的合约?
- ¥15 为什么使用javacv转封装rtsp为rtmp时出现如下问题:[h264 @ 000000004faf7500]no frame?
- ¥15 乘性高斯噪声在深度学习网络中的应用
- ¥15 关于docker部署flink集成hadoop的yarn,请教个问题 flink启动yarn-session.sh连不上hadoop,这个整了好几天一直不行,求帮忙看一下怎么解决
- ¥15 深度学习根据CNN网络模型,搭建BP模型并训练MNIST数据集