/******************************************************************** created: 2005/12/30 created: 30:12:2005 10:39 filename: bintree.h author: Liu Qi purpose: 二叉树的3种遍历方式(包括非递归实现),前序,后序和中序,先访问根节点就是 前序(部分书籍称为先根遍历,个人觉得该说法更好^_^),类似的,最后访问根节点就是后序 *********************************************************************/ #ifndef TREE_H #define TREE_H #include <stdio.h> #include <malloc.h> #include <stack> #include <queue> #include <assert.h> using namespace std; typedef int ElemType; typedef struct treeT { ElemType key; struct treeT* left; struct treeT* right; }treeT, *pTreeT; /**//*=========================================================================== * Function name: visit * Parameter: root:树根节点指针 * Precondition: * Description: * Return value: * Author: Liu Qi, //- ===========================================================================*/ static void visit(pTreeT root) { if (NULL != root) { printf(" %d\n", root->key); } } /**//*=========================================================================== * Function name: BT_MakeNode * Parameter: target:元素值 * Precondition: None * Postcondition: NULL != pTreeT * Description: 构造一个tree节点,置左右指针为空,并且返回指向新节点的指针 * Return value: 指向新节点的指针 * Author: Liu Qi, [12/30/2005] ===========================================================================*/ static pTreeT BT_MakeNode(ElemType target) { pTreeT pNode = (pTreeT) malloc(sizeof(treeT)); assert( NULL != pNode ); pNode->key = target; pNode->left = NULL; pNode->right = NULL; return pNode; } /**//*=========================================================================== * Function name: BT_Insert * Parameter: target:要插入的元素值, pNode:指向某一个节点的指针 * Precondition: NULL != ppTree * Description: 插入target到pNode的后面 * Return value: 指向新节点的指针 * Author: Liu Qi, [12/29/2005] ===========================================================================*/ pTreeT BT_Insert(ElemType target, pTreeT* ppTree) { pTreeT Node; assert( NULL != ppTree ); Node = *ppTree; if (NULL == Node) { return *ppTree = BT_MakeNode(target); } if (Node->key == target) //不允许出现相同的元素 { return NULL; } else if (Node->key > target) //向左 { return BT_Insert(target, &Node->left); } else { return BT_Insert(target, &Node->right); } } /**//*=========================================================================== * Function name: BT_PreOrder * Parameter: root:树根节点指针 * Precondition: None * Description: 前序遍历 * Return value: void * Author: Liu Qi, [12/29/2005] ===========================================================================*/ void BT_PreOrder(pTreeT root) { if (NULL != root) { visit(root); BT_PreOrder(root->left); BT_PreOrder(root->right); } } /**//*=========================================================================== * Function name: BT_PreOrderNoRec * Parameter: root:树根节点指针 * Precondition: Node * Description: 前序(先根)遍历非递归算法 * Return value: void * Author: Liu Qi, [1/1/2006] ===========================================================================*/ void BT_PreOrderNoRec(pTreeT root) { stack<treeT *> s; while ((NULL != root) || !s.empty()) { if (NULL != root) { visit(root); s.push(root); root = root->left; } else { root = s.top(); s.pop(); root = root->right; } } } /**//*=========================================================================== * Function name: BT_InOrder * Parameter: root:树根节点指针 * Precondition: None * Description: 中序遍历 * Return value: void * Author: Liu Qi, [12/30/2005] ===========================================================================*/ void BT_InOrder(pTreeT root) { if (NULL != root) { BT_InOrder(root->left); visit(root); BT_InOrder(root->right); } } /**//*=========================================================================== * Function name: BT_InOrderNoRec * Parameter: root:树根节点指针 * Precondition: None * Description: 中序遍历,非递归算法 * Return value: void * Author: Liu Qi, [1/1/2006] ===========================================================================*/ void BT_InOrderNoRec(pTreeT root) { stack<treeT *> s; while ((NULL != root) || !s.empty()) { if (NULL != root) { s.push(root); root = root->left; } else { root = s.top(); visit(root); s.pop(); root = root->right; } } } /**//*=========================================================================== * Function name: BT_PostOrder * Parameter: root:树根节点指针 * Precondition: None * Description: 后序遍历 * Return value: void * Author: Liu Qi, [12/30/2005] ===========================================================================*/ void BT_PostOrder(pTreeT root) { if (NULL != root) { BT_PostOrder(root->left); BT_PostOrder(root->right); visit(root); } } /**//*=========================================================================== * Function name: BT_PostOrderNoRec * Parameter: root:树根节点指针 * Precondition: None * Description: 后序遍历,非递归算法 * Return value: void * Author: Liu Qi, // [1/1/2006] ===========================================================================*/ void BT_PostOrderNoRec(pTreeT root) { //学习中,尚未明白 } /**//*=========================================================================== * Function name: BT_LevelOrder * Parameter: root:树根节点指针 * Precondition: NULL != root * Description: 层序遍历 * Return value: void * Author: Liu Qi, [1/1/2006] ===========================================================================*/ void BT_LevelOrder(pTreeT root) { queue<treeT *> q; treeT *treePtr; assert( NULL != root ); q.push(root); while (!q.empty()) { treePtr = q.front(); q.pop(); visit(treePtr); if (NULL != treePtr->left) { q.push(treePtr->left); } if (NULL != treePtr->right) { q.push(treePtr->right); } } } #endif
测试代码
#include <stdio.h> #include <stdlib.h> #include <time.h> #include "tree.h" #define MAX_CNT 5 #define BASE 100 int main(int argc, char *argv[]) { int i; pTreeT root = NULL; srand( (unsigned)time( NULL ) ); for (i=0; i<MAX_CNT; i++) { BT_Insert(rand() % BASE, &root); } //前序 printf("PreOrder:\n"); BT_PreOrder(root); printf("\n"); printf("PreOrder no recursion:\n"); BT_PreOrderNoRec(root); printf("\n"); //中序 printf("InOrder:\n"); BT_InOrder(root); printf("\n"); printf("InOrder no recursion:\n"); BT_InOrderNoRec(root); printf("\n"); //后序 printf("PostOrder:\n"); BT_PostOrder(root); printf("\n"); //层序 printf("LevelOrder:\n"); BT_LevelOrder(root); printf("\n"); return 0; }
发表评论
-
析构函数为虚函数的原因
2012-09-09 11:42 786我们知道,用C++开发的时候,用来做基类的类的析构函数 ... -
hash的应用
2012-08-31 23:02 925第一部分为一道百度面试题Top K算法的详解;第二部分为关 ... -
微软智力题
2012-08-29 19:59 539第一组1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
C++不能被继承的类
2012-08-27 20:16 997一个类不能被继承, ... -
括号对齐问题
2012-08-27 10:47 1352解法一:左右括号成一对则抵消 可以 ... -
堆排序
2012-08-16 14:24 844堆:(二叉)堆数据结构是一种数组对象。它可以被视为一棵完全 ... -
多态赋值
2012-08-14 16:16 778#include <iostream> usi ... -
static变量与static函数(转)
2012-08-13 10:15 702一、 static 变量 static变量大致分为三种用法 ... -
不用sizeof判断16位32位
2012-08-10 15:21 1663用C++写个程序,如何判断一个操作系统是16位还是3 ... -
找出连续最长的数字串(百度面试)
2012-08-09 15:15 1111int maxContinuNum(const char*in ... -
顺序栈和链栈
2012-08-06 10:01 767顺序栈:话不多说直接上代码 #include ... -
队列的数组实现和链表实现
2012-08-05 16:20 995话不多少,数组实现上代码: #include<i ... -
KMP算法详解
2012-08-02 21:40 850KMP算法: 是在一个“主文本字符串” ... -
字符串的最长连续重复子串
2012-08-01 15:05 9700两种方法: 循环两次寻找最长的子串: <方法一> ... -
寻找一个字符串连续出现最多的子串的方法(转)
2012-07-31 21:19 918算法描述首先获得后缀数组,然后1.第一行第一个字符a,与第二行 ... -
字符串的循环移位
2012-07-31 16:52 935假设字符串:abcdefg 左循环两位:cdefgab 右 ... -
一次谷歌面试趣事(转)
2012-07-31 15:26 726很多年前我进入硅谷 ... -
约瑟夫环问题(循环链表)
2012-07-30 21:31 1242题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1, ... -
面试之单链表
2012-07-30 20:18 6911、编程实现一个单链表的建立/测长/打印。 ... -
多重继承内存地址问题
2012-07-30 15:55 696[cpp] view plaincopy ...
相关推荐
三叉树多叉树遍历 c# 2.0
遍历目录树 遍历目录树 遍历目录树 遍历目录树
基于Python的多叉树遍历算法
实现文件树遍历程序myfind,参照UNIX环境高级编程中的例子
建立一棵二叉链表树,分别输出此先根、中根和后根遍历序列 将上题编程,实现哈夫曼树的构建和哈夫曼编码的设计
CTreeCtrl目录树遍历,提供了两种遍历目录树的方式,循环,递归。
VFP中TREE树遍历 无限制目录树
无线Mesh网络的网络结构导致了无线Mesh网络具有更多的安全隐患。其中数据完整性校验是...在研究的基础上,提出了一种改进的Merkle可信树遍历算法,并将改进后的Merkle可信树应用于无线Mesh网络的数据完整性校验机制。
树遍历.cpp
多叉树的遍历,可以打印出树形结构,也可以只打印叶节点,或打印指定层的节点(一位德国教授写的文章)可以按照文章中给的网址下载源代码,
C++用递归算法实现二叉树的前序、中序、后序遍历,用队列实现层次遍历
以Underscore / Lodash方式编写的树遍历库。 独立或作为Lodash mixin扩展 安装 在浏览器中 在Lodash之后加载,然后将lodash实例传递给deepdash函数: < script src =" ...
java多叉树的实现:节点集合生成多叉树,单个节点添加到多叉树,深度遍历,广度遍历
排序、二分法查找、树遍历等常见算法实现python语言实现 常见数据结构 顺序表 Python中的list和tuple两种类型采用了顺序表的实现技术 链表 单向链表 双向链表 单向循环链表 栈 队列 FIFO队列 LIFO队列 优先队列...
jquery遍历节点树jquery遍历节点树jquery遍历节点树
C++用非递归算法(用栈实现前序、中序、后序遍历;用队列实现层次遍历)实现二叉树的遍历。
一个MFC的程序,他能够实现将指定目录下的目录树绘制起来。
尝试设计翻译方法。假定对程序片段已得到语法树,如 if (a > b) b = a; 已得到语法树 编写程序,遍历语法树,执行代码,得到正确结果。
非递归前序,中序,后序遍历二叉树(优化算法)