二叉树的查找(前序、中序、后序、层序遍历)--bia…
2019-10-29 16:01:26来源:博客园 阅读 ()
二叉树的查找(前序、中序、后序、层序遍历)--biaobiao88
建立一棵含有n个结点的二叉树,采用二叉链表存储;
输出前序、中序、后序、、层序遍历该二叉树的遍历结果。
定义二叉树的数据类型——二叉树结点结构体BiNode。建立二叉链表可以采用扩展二叉树的一个遍历序列,例如前序序列,将扩展二叉树的前序序列由键盘输入,建立该二叉树的二叉链表存储。
简单起见,本实验假定二叉树的数据元素为char型
用模板类改写
#include<iostream> #include<cstdio> #include<cstdlib> #include<malloc.h> int MaxSize = 100; using namespace std; typedef char DataType; typedef struct BiNode { DataType data; struct BiNode *lchile,*rchild; }BiNode; BiNode *root; //创建拓展二叉树,#代虚结点 BiNode *Creat(BiNode *root)// cishu ///// { char ch; cin >> ch; if(ch == '#') root = NULL; else { root = (BiNode *)malloc(sizeof(BiNode)); root->data = ch; root->lchile = Creat(root->lchile); root->rchild = Creat(root->rchild); } return root; } //前序遍历 void PreOrder(BiNode *root) { if(root == NULL) return; else { cout << root->data << " "; PreOrder(root->lchile); PreOrder(root->rchild); } } //中序遍历 void InOrder(BiNode *root) { if(root == NULL) return; else { InOrder(root->lchile); cout << root->data << " "; InOrder(root->rchild); } } //后序遍历 void PostOrder(BiNode *root) { if(root == NULL) return; else { InOrder(root->lchile); InOrder(root->rchild); cout << root->data << " "; } } //层序遍历 void LevelOrder(BiNode *root) { BiNode *q = NULL,*Q[MaxSize]; int front = -1; int rear = -1; if(root == NULL) return; Q[++rear] = root; while(front != rear) { q = Q[++front]; cout << q->data << " "; if(q->lchile != NULL) Q[++rear] = q->lchile; if(q->rchild != NULL) Q[++rear] = q->rchild; } } int main() { BiNode *root = NULL; root = Creat(root); cout << "该二叉树的根节点是:" << root->data << endl; cout << endl; cout << "该二叉树的前序遍历是:"; PreOrder(root); cout << endl; // cout << "该二叉树的根节点是:" << root->data << endl; cout << endl; cout << "该二叉树的中序遍历是:"; InOrder(root); cout << endl; // cout << "该二叉树的根节点是:" << root->data << endl; cout << endl; cout << "该二叉树的后序遍历是:"; PostOrder(root); cout << endl; // cout << "该二叉树的根节点是:" << root->data << endl; cout << endl; cout << "该二叉树的层序遍历是:"; LevelOrder(root); cout << endl; return 0; } /* abd##e##c#f## 该二叉树的根节点是:a 该二叉树的前序遍历是:a b d e c f 该二叉树的中序遍历是:d b e a c f 该二叉树的后序遍历是:d b e c f a 该二叉树的层序遍历是:a b c d e f */
原文链接:https://www.cnblogs.com/biaobiao88/p/11761685.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 二叉搜索树_BST 2020-05-30
- 二叉树 2020-05-02
- 二叉排序树 2020-05-02
- C++ 实现带监视哨的顺序查找 2020-03-26
- C语言:字符串拷贝(截取)、查找 2020-02-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash