实现二叉树的先序遍历、中序遍历、后序遍历
2018-06-27 10:04:19来源:未知 阅读 ()
一、二叉树定义
1.树的术语:
树的结点:包含一个数据元素及若干指向子树的分支;
孩子结点:结点的子树的根称为该结点的孩子;
双亲结点:B 结点是A 结点的孩子,则A结点是B 结点的双亲;
兄弟结点:同一双亲的孩子结点; 堂兄结点:同一层上结点;
祖先结点: 从根到该结点的所经分支上的所有结点子孙结点:以某结点为根的子树中任一结点都称为该结点的子孙
结点层:根结点的层定义为1;根的孩子为第二层结点,依此类推;
树的深度:树中最大的结点层
结点的度:结点子树的个数
树的度: 树中最大的结点度。
叶子结点:也叫终端结点,是度为 0 的结点;
分枝结点:度不为0的结点;
有序树:子树有序的树
无序树:不考虑子树的顺序
2.由树引出二叉树
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^(i-1)个结点;深度为k的二叉树至多有2^k-1个结点。
二叉树有五种基本形态:
(1)空二叉树;
(2)只有一个根结点的二叉树;
(3)只有左子树;
(4)只有右子树;
(5)完全二叉树
尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。(当有序树只有一个节点时没有左右之分,而二叉树不是)
3.二叉树的遍历
附上代码:
#include<stdio.h> #include<stdlib.h> typedef char TElemType; #define OK 1 #define ERROR 0 typedef int Status; typedef struct BiTNode{ TElemType data; struct BiTNode* LChild,*RChild; }BiTNode,*BiTree; Status Visit(TElemType e){ if(e!=' ') printf("%c ",e); return OK; } Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ if(T){ if(Visit(T->data)){ if(PreOrderTraverse(T->LChild,Visit)){ if(PreOrderTraverse(T->RChild,Visit)){ return OK; } } } return ERROR; }else{ return OK; } } Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ if(T){ if(InOrderTraverse(T->LChild,Visit)){ if(Visit(T->data)){ if(InOrderTraverse(T->RChild,Visit)){ return OK; } } } return ERROR; }else{ return OK; } } Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ if(T){ if(PostOrderTraverse(T->LChild,Visit)){ if(PostOrderTraverse(T->RChild,Visit)){ if(Visit(T->data)){ return OK; } } } return ERROR; }else{ return OK; } } Status CreatTree(BiTree& T){ TElemType ch; T=(BiTree)malloc(sizeof(BiTNode)); scanf("%c",&ch);getchar(); T->data=ch; if(ch==' '){ T->LChild=NULL; T->RChild=NULL; return OK; } printf("输入%c的左孩子:",ch); CreatTree(T->LChild); printf("输入%c的右孩子:",ch); CreatTree(T->RChild); } int main(){ BiTree T=NULL; printf("输入root:"); CreatTree(T); printf("\nPreOrderTraverse:"); PreOrderTraverse(T,Visit); printf("\nInOrderTraverse:"); InOrderTraverse(T,Visit); printf("\nPostOrderTraverse:"); PostOrderTraverse(T,Visit); }
遍历的树:
运行截图:
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:动态绑定与静态绑定
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 二叉搜索树_BST 2020-05-30
- opencv-12-高斯滤波-双边滤波(附C++代码实现) 2020-05-10
- 二叉树 2020-05-02
- 二叉排序树 2020-05-02
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