网站首页
网站导航
Ctrl+D收藏
首 页
代码段
源码包
文档库
工具箱
代码语言
.
CSharp
.
JS
Java
Asp.Net
C
MSSQL
PHP
Css
PLSQL
Python
Shell
EBS
ASP
Perl
ObjC
VB.Net
VBS
MYSQL
GO
Delphi
AS
DB2
Domino
Rails
ActionScript
Scala
代码分类
文件
系统
字符串
数据库
网络相关
图形/GUI
多媒体
算法
游戏
Jquery
Extjs
Android
HTML5
菜单
网页交互
WinForm
控件
企业应用
安全与加密
脚本/批处理
开放平台
其它
【
C
】
二叉树递归,非递归遍历
作者:
Gooogle
/ 发布于
2012/3/6
/
799
#include <stdio.h></div> #include <stdlib.h></div> #include <assert.h></div> <div>/* struct of tree */</div> <div>typedef struct tree {</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>int data;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>struct tree *left;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>struct tree *right;</div> <div>} tree_item, *tree_pitem, *tree_list;</div> <div></div> <div>/* alloc_item alloc a struct of tree_item, and return it */</div> <div>tree_pitem alloc_item(int data){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tree_pitem tmp = (tree_pitem)malloc(sizeof(tree_item));</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp->data = data;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp->left = NULL;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp->right = NULL;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>return tmp;</div> <div>} <div></div> <div>/* print root of the tree */</div> <div>void put_root(tree_item *l){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>printf("[%d]", l->data);</div> <div>} <div></div> <div>/* insert item into tree */</div> <div>void insert_to_tree(int data, tree_list *l){//需要修改l的left和right 所以用**</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL == *l){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>*l = alloc_item(data);//这里是根节点初始化</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(data < (*l)->data){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL == (*l)->left){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>(*l)->left = alloc_item(data);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>insert_to_tree(data, &(*l)->left);//小的往左边塞</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else if(data > (*l)->data){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL == (*l)->right){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>(*l)->right = alloc_item(data);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>insert_to_tree(data, &(*l)->right);//大的往右边塞</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>return;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div>} <div></div> <div>void first_put(tree_list l){//先序递归</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL != l){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>put_root(l);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>first_put(l->left);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>first_put(l->right);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div>} <div></div> <div>void middle_put(tree_list l){//中序递归</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL != l){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>middle_put(l->left);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>put_root(l);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>middle_put(l->right);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div>} <div></div> <div>void last_put(tree_list l){//后续递归</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL != l){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>last_put(l->left);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>last_put(l->right);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>put_root(l);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div>} <div></div> <div>/* 栈没有定义, 也没有验证正确与否, 算是个伪代码 */</div> <div>void iteration_first(tree_list l){非递归先序</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tree_list tmp = l;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL != l){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>while(!is_empty(tmp)){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>visit(tmp);//先访问根</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(tmp->left != NULL){//如果有左子节点</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>push(tmp);//保存根</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = tmp->left;//开始访问左子树</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(tmp->right != NULL){//如果没有左子节点, 但有右子节点</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>push(tmp);//保存根</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = tmp->right;//开始访问右子树</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = pop();//既没有左也没有右, 回到父节点</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div>} <div></div> <div>void iteration_middle(tree_list l){//非递归中序</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tree_list tmp = l;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL != l){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>while(!is_empty(tmp)){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(tmp->left != NULL){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>push(tmp);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = tmp->left;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>visit(tmp);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(tmp->right != NULL){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>push(tmp);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = tmp->right;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = pop();</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div> } <div> } <div>} <div></div> <div>void iteration_last(tree_list l){//非递归后序</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tree_list tmp = l;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(NULL != l){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>while(!is_empty(tmp)){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(tmp->left != NULL){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>push(tmp);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = tmp->left;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>if(tmp->right != NULL){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>push(tmp);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = tmp->right;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>}else{</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>visit(tmp);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tmp = pop();</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div>} <div></div> <div>int main(int argc, char **argv){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>tree_list tree = (tree_list)0;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>int i;</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>for(i = 1; i <= 10; i++){</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>insert_to_tree(i, &tree);//insert_to_tree(rand() % 100, &tree)</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>} <div><span class="Apple-tab-span" style="white-space:pre"> </span>first_put(tree);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>puts("\n");</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>middle_put(tree);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>puts("\n");</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>last_put(tree);</div> <div><span class="Apple-tab-span" style="white-space:pre"> </span>puts("\n");</div> <div>} <div></div>
评论列表
本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。
试试其它关键字
二叉树
同语言下
.
获取手机通讯录 iOS去除数字以外的所有字符
.
异步加载音乐等资源
.
交通罚单管理系统
.
freemark实现，简单的替换
.
计算斐波那契数列
.
base64解码 包括解码长度
.
图像显示
.
冒泡排序
.
输入十进制数，输出指定进制
.
链式栈
可能有用的
.
SQL查询 多列合并成一行用逗号隔开
.
一行一行读取txt的内容
.
C#动态修改文件夹名称(FSO实现，不移动文件)
.
c# 移动文件或文件夹
.
c#图片添加水印
.
Java PDF转换成图片并输出给前台展示
.
网站后台修改图片尺寸代码
.
处理大图片在缩略图时的展示
.
实现对图片上传的接收
.
判断用户输入的是否为IP地址
Gooogle
贡献的其它代码
(
3
)
.
将人民币数字转换成大写形式
.
二叉树递归,非递归遍历
.
文件读写操作工具类
地图
本站
我们
服务
版权
联系
回馈
博客