<meta http-equiv="Content-Type" content="text/html;charset=gb2312">
/***************************************************************** * 文件名:Rstree.c * * 文件描述:树相关操作的递归算法实现 * * 创建人:颜清国 2006年4月15日 * * * 修改记录: * **************************************************************/ #include "stdio.h"#include"stdlib.h"#include"conio.h"#define LEFT 1#define RIGHT 2#define MAX 20/************************************** 定义树的结构体***************************************/typedef struct tagtree{ char data; /*数据域*/ int flag; /*非递归操作时用来做标志*/ struct tagtree*lchild; /*指向左孩子的指针域*/ struct tagtree*rchild; /*指向右孩子的指针域*/}tree;/**************************************** 创建一棵树,要求这棵树用括号表示法输入*****************************************/void CreateTree(tree **root,char *str){ char ch; tree *stack[MAX],*lp=NULL,*temp; /*定义一个指向树的一个栈, 用来创建其结点的父子关系*/ int top=-1,flag; /*指向树栈的栈顶,flag用来标记左右孩子*/ (*root)=NULL; /*特别注意这里一定要先将指向根结点的指针附空,否则 在XP系统下就会出大错*/while((*str)!='\0'){ ch=(*str); switch(ch) { case '(': /*下去的DATA值将作为栈顶结点的左右孩子*/ top++; stack[top] = lp; /*将双亲结点入栈*/ flag = LEFT; /*标记其下一个结点将作为此栈顶结点的 左孩子*/ break; case ',': flag = RIGHT; /*标记为下去结点将作为此栈顶结点的 右孩子*/ break; case ')': top--; /*将栈顶结点退栈,这样才能保证双亲及 其对应孩子的正确配对*/ break; default: /*此时CH为DATA域*/ lp = (tree*)malloc(sizeof(tree)); /*创建一个结点*/ lp->data = ch; lp->lchild = NULL; lp->rchild = NULL; if((*root) == NULL) /*是树的根结点*/ (*root) = lp; else { /*注意此处不能用这种表达方式*/ /* temp = (flag == LEFT) ? stack[top]->lchild : stack[top]->rchild; temp = lp; */ switch(flag) { case RIGHT: /*插到右结点*/ stack[top]->rchild = lp; break; case LEFT: /*插到左结点*/ stack[top]->lchild = lp; break; } } break; } str++;}}/******************************************** 用括号表示法输出树**********************************************/void OutTree(tree *root){ if(root != NULL) { printf("%c",root->data); /*先输出根结点*/ if(root->lchild != NULL || root->rchild != NULL) { printf("("); OutTree(root->lchild); /*处理左子树*/ if(root->rchild != NULL) { printf(","); } OutTree(root->rchild); /*处理右子树*/ printf(")");}}}/************************************************ 递归先序遍历二叉树************************************************/void RsPrePath(tree *root){ if(root!=NULL) { printf("%c ",root->data); /*遇到根结点先输出*/ RsPrePath(root->lchild); /*遇到根结点左子数先输出, 直到空,返回是输出左子数 根结点右子数*/ RsPrePath(root->rchild); /*同样处理右子数*/ }}/************************************************ 递归中序遍历二叉树************************************************/void RsMidPath(tree *root){ if(root!=NULL) { RsMidPath(root->lchild); printf("%c ",root->data); RsMidPath(root->rchild); }}/************************************************ 递归后序遍历二叉树************************************************/void RsLastPath(tree *root){ if(root!=NULL) { RsLastPath(root->lchild); RsLastPath(root->rchild); printf("%c ",root->data); }}/*********************************************** 递归遍历二叉树演示************************************************/void RsTreeDemo(tree*root){ printf("\nthe PrePath is:"); RsPrePath(root); printf("\nthe MidPath is:"); RsMidPath(root); printf("\nthe LastPath is:"); RsLastPath(root);}/************************************************ 用树形表示法输出树*************************************************/void DispTree(tree *root,int x,int y,int n) /*n用来控制第一层树的高度*/{ int i=0; if(root !=NULL) { gotoxy(x,y); /*到相应结点输出*/ printf("%c",root->data); if(root->lchild != NULL) /*处理左子树,这里只有第一次N为可变的,*/ { i=1; /*为的是能够输出整棵树,而不会被覆盖,*/ while(ilchild,x-n,y+n,2); /*递归处理左子树*/ } if(root->rchild != NULL) { i=1; while(irchild,x+n,y+n,2); /*递归处理右子树*/ } }}/***************************************************** 根据DATA域,查找第一个遇到的结点,并返回该结点 *****************************************************/tree* IndexNode(tree *root,char data,int *high,int temp){ if(root == NULL) { (*high)=0; return NULL; } else if(root->data == data) /*找到所要找的结点*/ { (*high) = temp; return root; } else { if(IndexNode(root->lchild,data,high,temp+1)==NULL) { IndexNode(root->rchild,data,high,temp+1);/*如果在左子树中没有找到*/ } }}/**************************************************** 找某一结点的左子树 ****************************************************/tree* FindLchild(tree * node){ if(node !=NULL) { return node->lchild; } else return NULL;}/**************************************************** 找某一结点的右子树 ****************************************************/tree* FindRchild(tree * node){if(node !=NULL) { return node->rchild; } else return NULL;}/**************************************************** 先序遍历查找所有叶子结点 ****************************************************/void FindLeaft(tree *root){ if(root == NULL) return; if(root->lchild == NULL && root->rchild == NULL) { printf("%c ",root->data); } FindLeaft(root->lchild); FindLeaft(root->rchild);}void main(){ tree *root; int high; char str[100]; clrscr(); printf("Please input the Tree string:"); gets(str); CreateTree(&root,str); printf("\nthe Tree is:"); DispTree(root,10,4,5); gotoxy(2,15); FindLeaft(root); /*printf("\n%c",IndexNode(root,'t',&high,1)->data); printf("\n%d",high);*/ /*RsTreeDemo(root);*/ getch();}
分享到:
相关推荐
本文实例讲述了JavaScript实现多叉树的递归遍历和非递归遍历算法操作。分享给大家供大家参考,具体如下: 演示之前的准备工作 演示项目的文件结构: index.html jsonData.js recurrenceTree.js noRecurrenceTree.js ...
掌握二叉树的二叉链表存储结构;掌握二叉树的遍历规则;利用二叉树的二叉链表存储结构实现二叉树的建树操作;利用二叉树的二叉链表存储结构实现二叉树层次...设计并实现如下算法:后序递归建树,先序非递归遍历该树。
本文实例讲述了js 递归json树实现根据子id查父id的方法。分享给大家供大家参考,具体如下: 最近做了一个类似用js实现思维导图的功能,作为思维导图,一定会有树状结构的数据产生,在操作里面的节点时会经常需要查找...
本文实例讲述了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作。分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,...
1、二叉树三种遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4.层次遍历算法 19 2、线性表 20 4、串 23 5、多维数组和广义表 24 6、树与二叉树 24 7、图 26 8、查找...
3) 分析递归算法的⼯具是递归树,从递归树上可以得到递归函数的各种相关信息。例如:递归树的深度即为递归函数的递归深度;递归树上的结点数 ⽬恰为函数中的主要操作重复进⾏的次数;若递归树蜕化为单⽀树或者递归树...
07-008习题课:广义表的存储、递归算法、汉诺塔问题、二叉树的基本操作 07-009习题课:图的简单路径、深度优先遍历图的非递归算法等 09-001顺序表的查找、有序表的查找、二分查找 09-002顺序表的查找与有序表的查找...
这个算法也有被称为FP-growth算法,这个算法克服了Apriori算法的产生过多侯选集的缺点,通过递归的产生频度模式树,然后对树进行挖掘,后面的过程与Apriori算法一致。详细介绍链接 PageRank 网页重要性/排名算法。...
实现二叉树的先序,中序与后序遍历的递归算法与非递归算法。求二叉树的结点个数,叶子结点个数,二叉树的高度,度为2的结点个数等,自己设计一段报文,设计哈夫曼编码与译码系统。
范例1-71 树的二叉链表存储的基本操作 193 ∷相关函数:LevelOrderTraverse函数 1.4.18 二叉树的三叉链表存储的基本操作 201 范例1-72 二叉树的三叉链表存储表示 201 ∷相关函数:CreateBiTree函数 1.4.19 二叉树的...
5.1 递归算法 5.2 分治法 5.3 动态规划 5.4 树 5.5 树的数学性质 5.6 树的遍历 5.7 递归二叉树算法 5.8 图的遍历 5.9 综述 第三部分 排序 第6章 基本排序方法 6.1 游戏规则 6.2...
通过研究数和二叉树,深刻理解链式存储结构用于表达非线性结构的作用,掌握采用递归算法实现递归数据结构基本操作的设计方法。 二、实验题目 public void printGenList() 输出树的广义表表示字符串 三、实验方法与...
1. 熟悉二叉树结点的...3. 学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4. 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。 5. 掌握构造哈夫曼树以及哈夫曼编码的方法
数据结构算法实现(严蔚敏版配套实现程序) 1.1 数组和字符串 2 1.1.1 一维数组的倒置 2 范例1-1 一维数组的倒置 2 ∷相关函数:fun函数 1.1.2 一维数组应用 3 范例1-2 一维数组应用 3 1.1.3 一维数组的高级应用 5 ...
good)——图 15. 利用深度或广度优先搜索求...20. 递归算法与非递归算法的比较与复杂度分析(实例说明,具体数据) 21. 一种查找算法的改进及性能分析(实例说明,具体数据) 22.哈希表在字符串操作中的应用(字符串
/*选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等) 【实验内容】 必做内容 程序的菜单功能项如下: 1----...
④二叉树先序遍历的非递归算法实现; ⑤利用二叉树的遍历算法求二叉树的结点数、二叉树的叶结点数、二叉树的高度; ⑥二叉树的撤销删除 三、实验步骤: 1、需求分析: 本演示程序用JAVA编写,完成树的生成,任意位置...
一、以动态二叉链表为存储结构,实现如下操作: 1. 二叉树的建立, 2. 先序遍历的非递归算法, 3. 按层次遍历的算法, 4. 将二叉树的深度作为递归参数,实现计算树的深度的递归算法
/* 迷宫问题的非递归算法(栈实现)*/ /* 队列的顺序表示:类型和函数声明 */ /* 队列的顺序表示:函数定义 */ /*队列链接表示:类型和界面函数声明*/ /*队列链接表示:函数定义*/ /* 用队列解决农夫过河问题的算法*/ ...