- 浏览: 2830498 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (1173)
- 名言警句 (5)
- 心情随笔 (50)
- 数据库 (57)
- Java基础 (241)
- J2EE框架 (91)
- 数据结构 (12)
- 程序设计 (21)
- WEB技术 (128)
- 网络日志 (12)
- IT资讯 (247)
- linux (64)
- solaris (2)
- 其它 (143)
- WebService (4)
- 日语学习 (2)
- 机器人 (5)
- Android (5)
- cgywin (3)
- Game (1)
- DWR (1)
- spring (8)
- canvas (1)
- Guava (3)
- Modbus (5)
- 测试 (6)
- mongodb (9)
- Quartz (2)
- Cron (1)
- windows (2)
- 持续集成 (1)
- bootstrap (3)
- 结对编程 (1)
- nodejs (1)
- Netty (1)
- 安全 (3)
- webstorm (2)
- sparkline (1)
- Job (1)
- git (3)
- Maven (3)
- knockout (5)
- jquery (1)
- bower (1)
- docker (1)
- confluence (4)
- wiki (1)
- GoogleMap (1)
- jekyll (10)
- ruby (2)
- npm (3)
- browserify (1)
- gulp (3)
- openwrt (1)
- discuz (3)
- 输入法 (1)
- JPA (1)
- eclipse (2)
- IntelliJ (1)
- css (1)
- 虚拟机 (1)
- 操作系统 (1)
- azkaban (2)
- scrum (1)
最新评论
-
pangxiea_:
你好, 想请问一下 Linux下 这么使用rxtxcomm 在 ...
使用Java进行串口通信 -
abababudei:
请教一下,这个您是怎么解决的:/dev/ttyS2enteri ...
Java应用程序的MODBUS通讯 -
xuniverse:
hannibal005 写道楼主,我问下 request.se ...
用javascript与java进行RSA加密与解密 -
atxkm:
找了一下午,终于找到了
gulp 拷贝文件时如何移除文件目录结构 -
kalogen:
gtczr 写道非常感谢,经过我自己的修改,已经完美实现。发出 ...
用javascript与java进行RSA加密与解密
java 代码
- //二叉树处理头文件
- //包括二叉树的结构定义,二叉树的创建,遍历算法(递归及非递归),
- /*
- 作者:成晓旭
- 时间:2001年10月7日(18:49:38-20:00:00)
- 内容:完成二叉树创建,二叉树的前,中,后序遍历(递归)
- 时间:2001年10月7日(21:09:38-22:09:00)
- 内容:完成二叉树的前,中序遍历(非递归)
- 时间:2001年10月8日(10:09:38-11:29:00)
- 内容:完成查找二叉树的静,动态查找(非递归)
- */
- #include "stdlib.h"
- #define MAXNODE 20
- #define ISIZE 8
- #define NSIZE0 7
- #define NSIZE1 8
- #define NSIZE2 15
- //SHOWCHAR = 1(显示字符) SHOWCHAR = 0(显示数字)
- #define SHOWCHAR 1
- //二叉树结构体
- struct BTNode
- {
- int data;
- BTNode *rchild;
- BTNode *lchild;
- };
- //非递归二叉树遍堆栈
- struct ABTStack
- {
- BTNode *ptree;
- ABTStack *link;
- };
- char TreeNodeS[NSIZE0] = {'A','B','C','D','E','F','G'};
- char PreNode[NSIZE0] = {'A','B','D','E','C','F','G'};
- char MidNode[NSIZE0] = {'D','B','E','A','C','G','F'};
- int TreeNodeN0[NSIZE1][2] = {{0,0},{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7}};
- int TreeNodeN1[NSIZE1][2] = {{0,0},{4,1},{2,2},{6,3},{1,4},{3,5},{5,6},{7,7}};
- int TreeNode0[NSIZE1][2] = {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}};
- int TreeNode1[NSIZE1][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}};
- int TreeNode2[NSIZE2][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7},{'H',8},{'I',9},{'J',10},{'K',11},{'L',12},{'M',13},{'N',14}};
- int InsertNode[ISIZE] = {-10,-8,-5,-1,0,12,14,16};
- //char *prestr = "ABDECFG";
- //char *midstr = "DBEACGF";
- /*
- 二叉树创建函数dCreateBranchTree1()<递归算法>
- 参数描述:
- int array[]: 二叉树节点数据域数组
- int i: 当前节点的序号
- int n: 二叉树节点个数
- 返回值:
- dCreateBranchTree1 = 新建二叉树的根节点指针
- 备注:
- 根节点 = array[(i+j)/2];
- 左子节点 = [array[i],array[(i+j)2-1]]
- 右子节点 = [array[(i+j)/2+1,array[j]]
- */
- BTNode *dCreateBranchTree1(char array[],int i,int n)
- {
- BTNode *p; /*二叉树节点*/
- if(i>=n)
- return(NULL);
- p = (BTNode *)malloc(sizeof(BTNode));
- p->data = array[i];
- p->lchild = dCreateBranchTree1(array,2*i+1,n);
- p->rchild = dCreateBranchTree1(array,2*i+2,n);
- return(p);
- }
- /*
- 二叉树创建函数dCreateBranchTree2()<递归算法>
- 参数描述:
- int array[]: 二叉树节点数据域数组
- int i: 当前节点的序号
- int n: 二叉树节点个数
- 返回值:
- dCreateBranchTree2 = 新建二叉树的根节点指针
- 备注:
- 根节点 = array[(i+j)/2];
- 左子节点 = [array[i],array[(i+j)2-1]]
- 右子节点 = [array[(i+j)/2+1,array[j]]
- */
- BTNode *dCreateBranchTree2(char array[],int i,int j)
- {
- BTNode *p; /*二叉树节点*/
- if(i>j)
- return(NULL);
- p = (BTNode *)malloc(sizeof(BTNode));
- p->data = array[(i+j)/2];
- p->lchild = dCreateBranchTree2(array,i,(i+j)/2-1);
- p->rchild = dCreateBranchTree2(array,(i+j)/2+1,j);
- return(p);
- }
- /*
- 二叉树创建函数dCreateBranchTree3()<非递归算法>
- 已知二叉树的前,中序遍历序列串,构造对应的二叉树
- <编程思想>:
- 首先,在前序遍历序列中的首元素是二叉树的根节点,接着
- ,在中序遍历序列中找到此节点,那么在此节点以前的节点必为
- 其左孩子节点,以后的必为其右孩子节点;
- 然后,在中序遍历序列中,根节点的左子树和右子树再分别
- 对应子树前序遍历序列的首字符确定子树的根节点,再由中序
- 遍历序列中根节点的位置分别确定构成它们的左子树和右子树
- 的节点;
- 依次类推,确定二叉树的全部节点,构造出二叉树.
- 参数描述:
- char *pre: 前序遍历序列
- char *mid: 中序遍历序列
- int n: 遍历序列中节点个数
- 返回值:
- dCreateBranchTree3 = 新建二叉树的根节点指针
- */
- BTNode *dCreateBranchTree3(char *pre,char *mid,int n)
- {
- BTNode *p;
- char *t;
- int left;
- if(n<=0)
- return(NULL);
- p = (BTNode *)malloc(sizeof(BTNode));
- p->data = *pre;
- for(t=mid;t<mid+n;t++)
- if(*t==*pre) break; /*在中序遍历序列中查找根节点*/
- left = t - mid; /*左子树的节点个数*/
- p->lchild = dCreateBranchTree3(pre+1,t,left);
- p->rchild = dCreateBranchTree3(pre+1+left,t+1,n-1-left);
- return(p);
- }
- /*
- 二叉树创建函数CreateBranchTree()<非递归算法>
- 参数描述:
- int array[]: 二叉树节点数据域数组
- int n: 二叉树节点个数
- 返回值:
- CreateBranchTree = 新建二叉树的根节点指针
- */
- BTNode *CreateBranchTree(int array[][2],int n)
- {
- BTNode *head,*p;
- BTNode *NodeAddr[MAXNODE]; //节点地址临时缓冲区
- int i,norder,rorder;
- head = NULL;
- printf("二叉树原始数据<新建顺序>:\t");
- for(i=1;i<=n;i++)
- {
- p = (BTNode *)malloc(sizeof(BTNode));
- if(p==NULL)
- {
- printf("\n新建节点时内存溢出!\n");
- return(NULL);
- }
- else
- {
- p->data = array[i][0];
- p->lchild = p->rchild = NULL;
- norder = array[i][1];
- NodeAddr[norder] = p;
- if(norder>1)
- {
- rorder = norder / 2; /*非根节点:挂接在自己的父节点上*/
- if(norder % 2 == 0)
- NodeAddr[rorder]->lchild = p;
- else
- NodeAddr[rorder]->rchild = p;
- }
- else
- head = p; /*根节点*/
- if(SHOWCHAR)
- printf("%c ",p->data);
- else
- printf("%d ",p->data);
- }
- }
- return(head);
- }
- //------------------------------递归部分------------------------------
- /*
- 二叉树前序遍历函数dpre_Order_Access()<递归算法>
- 参数描述:
- BTNode *head: 二叉树的根节点指针
- */
- void dpre_Order_Access(BTNode *head)
- {
- if(head!=NULL)
- {
- if(SHOWCHAR)
- printf("%c ",head->data);
- else
- printf("%d ",head->data);
- dpre_Order_Access(head->lchild); /*递归遍历左子树*/
- dpre_Order_Access(head->rchild); /*递归遍历右子树*/
- }
- }
- /*
- 二叉树中序遍历函数dmid_Order_Access()<递归算法>
- 参数描述:
- BTNode *head: 二叉树的根节点指针
- */
- void dmid_Order_Access(BTNode *head)
- {
- if(head!=NULL)
- {
- dmid_Order_Access(head->lchild); /*递归遍历左子树*/
- if(SHOWCHAR)
- printf("%c ",head->data);
- else
- printf("%d ",head->data);
- dmid_Order_Access(head->rchild); /*递归遍历右子树*/
- }
- }
- /*
- 二叉树后序遍历函数dlast_Order_Access()<递归算法>
- 参数描述:
- BTNode *head: 二叉树的根节点指针
- */
- void dlast_Order_Access(BTNode *head)
- {
- if(head!=NULL)
- {
- dlast_Order_Access(head->lchild); /*递归遍历左子树*/
- dlast_Order_Access(head->rchild); /*递归遍历右子树*/
- if(SHOWCHAR)
- printf("%c ",head->data);
- else
- printf("%d ",head->data);
- }
- }
- //------------------------------递归部分------------------------------
- //------------------------------非递归部分------------------------------
- /*
- 二叉树前序遍历函数pre_Order_Access()<非递归算法>
- 参数描述:
- BTNode *head: 二叉树的根节点指针
- */
- void pre_Order_Access(BTNode *head)
- {
- BTNode *pt;
- ABTStack *ps,*top;
- pt = head;
- top = NULL;
- printf("\n二叉树的前序遍历结果<非递归>:\t");
- while(pt!=NULL ||top!=NULL) /*二叉树未遍历完,或堆栈非空*/
- {
- while(pt!=NULL)
- {
- if(SHOWCHAR)
- printf("%c ",pt->data); /*访问根节点*/
- else
- printf("%d ",pt->data); /*访问根节点*/
- ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
- ps->ptree = pt;
- ps->link = top;
- top = ps;
- pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
- }
- if(top!=NULL)
- {
- pt = top->ptree; /*栈顶节点出栈*/
- ps = top;
- top = top->link;
- free(ps); /*释放栈顶节点空间*/
- pt = pt->rchild; /*遍历节点右子树*/
- }
- }
- }
- /*
- 二叉树中序遍历函数mid_Order_Access()<非递归算法>
- 参数描述:
- BTNode *head: 二叉树的根节点指针
- */
- void mid_Order_Access(BTNode *head)
- {
- BTNode *pt;
- ABTStack *ps,*top;
- int counter =1;
- pt = head;
- top = NULL;
- printf("\n二叉树的中序遍历结果<非递归>:\t");
- while(pt!=NULL ||top!=NULL) /*二叉树未遍历完,或堆栈非空*/
- {
- while(pt!=NULL)
- {
- ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
- ps->ptree = pt;
- ps->link = top;
- top = ps;
- pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
- }
- if(top!=NULL)
- {
- pt = top->ptree; /*栈顶节点出栈*/
- ps = top;
- top = top->link;
- free(ps); /*释放栈顶节点空间*/
- if(SHOWCHAR)
- printf("%c ",pt->data); /*访问根节点*/
- else
- printf("%d ",pt->data); /*访问根节点*/
- pt = pt->rchild; /*遍历节点右子树*/
- }
- }
- }
- /*
- 二叉树后序遍历函数last_Order_Access()<非递归算法>
- 参数描述:
- BTNode *head: 二叉树的根节点指针
- */
- void last_Order_Access(BTNode *head)
- {
- BTNode *pt;
- ABTStack *ps,*top;
- int counter =1;
- pt = head;
- top = NULL;
- printf("\n二叉树的后序遍历结果<非递归>:\t");
- while(pt!=NULL ||top!=NULL) /*二叉树未遍历完,或堆栈非空*/
- {
- while(pt!=NULL)
- {
- ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
- ps->ptree = pt;
- ps->link = top;
- top = ps;
- pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
- }
- if(top!=NULL)
- {
- pt = top->ptree; /*栈顶节点出栈*/
- ps = top;
- top = top->link;
- free(ps); /*释放栈顶节点空间*/
- printf("%c ",pt->data); /*访问根节点*/
- pt = pt->rchild; /*遍历节点右子树*/
- }
- }
- }
- /*
- 二叉查找树静态查找函数static_Search_STree()<非递归算法>
- 参数描述:
- BTNode *head: 二叉查找树的根节点指针
- int key: 查找关键码
- 返回值:
- static_Search_STree = 键值为key的节点指针(找到)
- static_Search_STree = NULL(没有找到)
- */
- BTNode *static_Search_STree(BTNode *head,int key)
- {
- while(head!=NULL)
- {
- if(head->data == key)
- {
- printf("\n数据域=%d\t地址=%d\t\n",head->data,head);
- return(head); /*找到*/
- }
- if(head->data > key)
- head = head->lchild; /*继续沿左子树搜索*/
- else
- head = head->rchild; /*继续沿右子树搜索*/
- }
- return(NULL); /*没有查找*/
- }
- /*
- 二叉查找树动态查找函数dynamic_Search_STree()<非递归算法>
- 参数描述:
- BTNode *head: 二叉查找树的根节点指针
- BTNode **parent: 键值为key的节点的父节点指针的指针
- BTNode **head: 键值为key的节点指针的指针(找到)或NULL(没有找到)
- int key: 查找关键码
- 注意:
- *parent == NULL 且 *p == NULL 没有找到(二叉树为空)
- *parent == NULL 且 *p != NULL 找到(找到根节点)
- *parent != NULL 且 *p == NULL 没有找到(叶节点)<可在parent后插入节点>
- *parent != NULL 且 *p != NULL 找到(中间层节点)
- */
- void dynamic_Search_STree(BTNode *head,BTNode **parent,BTNode **p,int key)
- {
- *parent = NULL;
- *p = head;
- while(*p!=NULL)
- {
- if((*p)->data == key)
- return; /*找到*/
- *parent = *p; /*以当前节点为父,继续查找*/
- if((*p)->data > key)
- *p = (*p)->lchild; /*继续沿左子树搜索*/
- else
- *p = (*p)->rchild; /*继续沿右子树搜索*/
- }
- }
- /*
- 二叉查找树插入节点函数Insert_Node_STree()<非递归算法>
- 参数描述:
- BTNode *head: 二叉查找树的根节点指针
- int key: 查找关键码
- 返回值:
- Insert_Node_STree = 1 插入成功
- Insert_Node_STree = 0 插入失败(节点已经存在)
- */
- int Insert_Node_STree(BTNode *head,int key)
- {
- BTNode *p,*q,*nnode;
- dynamic_Search_STree(head,&p,&q,key);
- if(q!=NULL)
- return(0); /*节点在树中已经存在*/
- nnode = (BTNode *)malloc(sizeof(BTNode)); /*新建节点*/
- nnode->data = key;
- nnode->lchild = nnode->rchild = NULL;
- if(p==NULL)
- head = p; /*原树为空,新建节点为查找树*/
- else
- {
- if(p->data > key)
- p->lchild = nnode; /*作为左孩子节点*/
- else
- p->rchild = nnode; /*作为右孩子节点*/
- }
- return(1); /*插入成功*/
- }
- /*
- 二叉查找树插入一批节点函数Insert_Batch_Node_STree()<非递归算法>
- 参数描述:
- BTNode *head: 二叉查找树的根节点指针
- int array[]: 被插入的数据域数组
- int n: 被插入的节点数目
- */
- void Insert_Batch_Node_STree(BTNode *head,int array[],int n)
- {
- int i;
- for(i=0;i<n;i++)
- {
- if(!Insert_Node_STree(head,array[i]))
- printf("\n插入失败<键值为%d的节点已经存在>!\n",array[i]);
- }
- }
- //------------------------------非递归部分------------------------------
发表评论
-
Oracle中的临时表用法汇总(转)
2008-02-29 10:34 20721.语法在Oracle中,可以创建以下两种临时表:1)会话特有 ... -
全方位介绍Oracle数据库中的回滚段
2008-01-08 11:27 4351本文分为以下几个部分: * 回滚段的作用 * 回滚段的类型 ... -
PLSQL单行函数和组函数详解(转)
2007-12-07 14:48 1812PL/SQL单行函数和组函数详解 函数是一种有零个 ... -
查找算法集:顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)(转)
2007-10-13 17:34 11688java 代码 // search.cpp : ... -
使用数据结构实现计算器功能-java
2007-10-12 13:09 2834java 代码 package cacu; ... -
链表之堆栈的实现
2007-10-12 12:59 2047java 代码 /** * ... -
链表之队列的实现
2007-10-12 12:52 2675java 代码 /** * ... -
链表的实现
2007-10-12 12:45 1597java 代码 /** * ... -
线性表之队列的实现
2007-10-12 12:42 1930java 代码 /** * Que ... -
线性排序的实现
2007-10-12 12:38 1640java 代码 /** * 线性表 ... -
线性表之堆栈的实现
2007-10-12 08:02 1875java 代码 /** ...
相关推荐
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版).
建立二叉树,实现二叉树的先序、中序、后序的递归遍历算法,输出遍历结果。 实现二叉树的先序、中序、后序和层次遍历的非递归算法,输出遍历结果。
经典的数据结构问题:二叉树非递归遍历算法实现 二叉树递归遍历算法实现
使用C++模板、类的技术实现了二叉树的中序遍历,在BC3.1已经测试成功
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
C语言实现二叉树的前序遍历(非递归),下载下来看看哦!
二叉树的非递归遍历,使用C++实现二叉树的非递归遍历,对正在学习算法的同学应该挺有帮助的
自己编写的实验二叉树的后序遍历非递归算法 包括以递归中序遍历建立二叉树 前序,中序,后序递归以及非递归实现二叉树的遍历 经vc6.0编译通过 自己实验,不足之处应该很多,望指出
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
利用栈的基本操作实现二叉树的中序遍历非递归算法。
C语言二叉树遍历前序非递归算法,简单易懂,正确无误
二叉树的中序、前序、后序的递归、非递归遍历算法
由先根次序和中跟次序建立二叉树,以及各种遍历的递归、非递归算法
非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度: 交换二叉树的左右子树: 二叉树已左右交换。 递归先序遍历二叉树: 递归...
按先序遍历的扩展序列建立二叉树的二叉链表存储结构,实现二叉树先序、中序、后序遍历的递归算法,实现二叉树中序遍历的非递归算法,实现二叉树层次遍历的非递归算法(要求使用顺序队列,调用顺序队列基本操作...
二叉树的后序遍历非递归算法.doc
//二叉树的二叉链表存储表示 typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; //左右孩子指针 } BiTNode, *BiTree; typedef struct { BiTree *base; BiTree *top; int stacksize; //当前...
⒈ 二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现; ⒉ 树与二叉树的转换的实现。