二叉树的非递归层次遍历

举报
IM_STONE 发表于 2020/12/29 00:15:52 2020/12/29
【摘要】 #include<iostream> #include<stack> #include<queue> using namespace std; typedef struct Node { char data; Node*lchild; Node*rchild; }Node; //创建一个节点 Node*BuyNode() { No...
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

typedef struct Node
{ char data; Node*lchild; Node*rchild;
}Node;

//创建一个节点
Node*BuyNode()
{ Node* p = new(nothrow)Node; if(p==NULL) { exit(-1); } memset(p,0,sizeof(Node)); return p;
}
//创建一棵二叉树
Node* CreateTree(char *&s)
{ if(s==NULL) { return NULL; } Node*p=NULL; if((*s) != '$') { p = BuyNode(); p->data = *s; p->lchild = CreateTree(++s); p->rchild = CreateTree(++s); } return p;
}
//先序递归遍历
void Frond(Node*p)
{ if(p) { cout<<p->data<<' '; Frond(p->lchild); Frond(p->rchild); }
}
//先序非递归遍历
void _Frond(Node*p)
{ stack<Node*>s; while(p!=NULL || !s.empty()) { while(p!=NULL) { s.push(p); cout<<p->data<<" "; p=p->lchild; } if(!s.empty()) { p= s.top(); s.pop(); p=p->rchild; } }
}
//层次遍历
void CenCi(Node*p)
{ if(p==NULL) { return; } int m = 0; queue<Node*>s; int qsize; s.push(p); while(!s.empty()) { m++; qsize = s.size();//记录当前层次的节点数 int i=0; while(i<qsize) { p=s.front(); if(p->lchild) { s.push(p->lchild); } if(p->rchild) { s.push(p->rchild); } cout<<p->data<<" "; s.pop(); i++; } cout<<m<<endl;//显示每一层次的结点 }
}

int main()
{ char *s="fdba$$c$$e$$g$ih$$jp$$$$"; Node*root=CreateTree(s); Frond(root); cout<<endl; _Frond(root); cout<<endl; CenCi(root); cout<<endl; return 0;
}
  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118

文章来源: blog.csdn.net,作者:IM-STONE,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/doubleintfloat/article/details/52622152

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。