您好,欢迎光临本网站![请登录][注册会员]  
文件名称: // BTree.cpp : Defines the entry point for the console application.
  所属分类: Access
  开发工具:
  文件大小: 2kb
  下载次数: 0
  上传时间: 2009-06-17
  提 供 者: sunsh******
 详细说明: // BTree.cpp : Defines the entry point for the console application. /* 作者:成晓旭 时间:2001年7月2日(9:00:00-14:00:00) 内容:完成二叉树的创建、前序遍历、中序遍历、后序遍历 时间:2001年7月2日(14:00:00-16:00:00) 内容:完成二叉树的叶子节点访问,交换左、右孩子 */ #include "stdafx.h" #include "stdlib.h" #defin e MAX_NODE 100 #define NODE_COUNT1 8 #define NODE_COUNT2 15 int TreeValue0[NODE_COUNT1][2] = {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}}; int TreeValue1[NODE_COUNT1][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}}; int TreeValue2[NODE_COUNT2][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}}; struct BTree { int data; int order; BTree *lchild; BTree *rchild; }; void Swap(int *p1,int *p2) { int t; t = *p1; *p1 = *p2; *p2 = t; } /* function CreateBTree()功能:创建一颗二叉树,并返回一个指向其根的指针 */ BTree *CreateBTree(int data[][2],int n) { BTree *Addr[MAX_NODE]; BTree *p, *head; int nodeorder,//节点序号 noderoot, //节点的双亲 i; if(n>MAX_NODE) { printf("参数错误!\n"); return(0); } for(i=1;i<=n;i++) { p = (BTree *)malloc(sizeof(BTree)); if(p==NULL) { printf("内存溢出错误!\n"); return(0); } else { p->data = data[i][0]; p->lchild = NULL; p->rchild = NULL; nodeorder = data[i][1]; p->order = nodeorder; Addr[nodeorder] = p; if(nodeorder>1) { noderoot = nodeorder/2; if(nodeorder %2 == 0) Addr[noderoot]->lchild = p; else Addr[noderoot]->rchild = p; } else head = p; printf("BTree[%d] = %c\t",p->order,p->data); } //free(p); } return(head); } /* function FirstOrderAccess0()功能:实现二叉树的前序遍历 二叉树前序遍历的思想: 从根节点开始,沿左子树一直走到没有左孩子的节点为止, 依次访问所经过的节点,同时所经[节点]的地址进栈; 当找到没有左孩子的节点时,从栈顶退出该节点的双亲的 右孩子,此时,此节点的左子树已访问完毕; 在用上述方法遍历该节点的右子树,如此重复到栈空为止。 */ void FirstOrderAccess0(BTree * header) { BTree * stack[MAX_NODE]; BTree *p; int top; top = 0; p = header; do { while(p!=NULL) { printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P top = top+1; stack[top] = p; p = p->lchild;//继续搜索节点P的左子树 } if(top!=0) { p = stack[top]; top = top-1; p = p->rchild;//继续搜索节点P的右子树 } }while((top!=0)||(p!=NULL)); } /* function FirstOrderAccess1()功能:实现二叉树的前序遍历 二叉树前序遍历的思想: 从根节点开始,沿左子树一直走到没有左孩子的节点为止, 依次访问所经过的节点,同时所经[节点的非空右孩子]进栈; 当找到没有左孩子的节点时,从栈顶退出该节点的双亲的 右孩子,此时,此节点的左子树已访问完毕; 在用上述方法遍历该节点的右子树,如此重复到栈空为止。 */ void FirstOrderAccess1(BTree * header) { BTree * stack[MAX_NODE]; BTree *p; int top; top = 0; p = header; do { while(p!=NULL) { printf("BTree[%d] = %c\t",p->order,p->data); if(p->rchild!=NULL) stack[++top] = p->rchild; p = p->lchild; } if(top!=0) p = stack[top--]; }while((top>0)||(p!=NULL)); } /* function MiddleOrderAccess()功能:实现二叉树的中序遍历 二叉树中序遍历的思想: 从根节点开始,沿左子树一直走到没有左孩子的节点为止, 并将所经[节点]的地址进栈; 当找到没有左孩子的节点时,从栈顶退出该节点并访问它, 此时,此节点的左子树已访问完毕; 在用上述方法遍历该节点的右子树,如此重复到栈空为止。 */ void MiddleOrderAccess(BTree * header) { BTree * stack[MAX_NODE]; BTree *p; int top; top = 0; p = header; do { while(p!=NULL) { stack[++top] = p;//节点P进栈 p = p->lchild; //继续搜索其左子树 } if(top!=0) { p = stack[top--];//节点P出栈 printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P p = p->rchild;//继续搜索其左子树 } }while((top!=0)||(p!=NULL)); } /* function LastOrderAccess()功能:实现二叉树的后序遍历 二叉树后序遍历的思想: 从根节点开始,沿左子树一直走到没有左孩子的节点为止, 并将所经[节点]的地址第一次进栈; 当找到没有左孩子的节点时,此节点的左子树已访问完毕; 从栈顶退出该节点,判断该节点是否为第一次进栈,如是,再 将所经[节点]的地址第二次进栈,并沿该节点的右子树一直走到 没有右孩子的节点为止,如否,则访问该节点;此时,该节点的 左、右子树都已完全遍历,且令指针p = NULL; 如此重复到栈空为止。 */ void LastOrderAccess(BTree * header) { BTree * stack[MAX_NODE];//节点的指针栈 int count[MAX_NODE];//节点进栈次数数组 BTree *p; int top; top = 0; p = header; do { while(p!=NULL) { stack[++top] = p;//节点P首次进栈 count[top] = 0; p = p->lchild; //继续搜索节点P的左子树 } p = stack[top--];//节点P出栈 if(count[top+1]==0) { stack[++top] = p;//节点P首次进栈 count[top] = 1; p = p->rchild; //继续搜索节点P的左子树 } else { printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P p = NULL; } }while((top>0)); } /* function IsLeafNode()功能:判断给定二叉树的节点是否是叶子节点 */ int IsLeafNode(BTree *node) { if((node->lchild==NULL)&&(node->rchild==NULL)) return(1); else return(0); } /* function PrintLeafNode()功能:输出给定二叉树的叶子节点 */ void PrintLeafNode(BTree *header) { BTree * stack[MAX_NODE];//节点的指针栈 BTree *p; int top; p = header; top = 0; do { while(p!=NULL) { stack[++top] = p; p = p->lchild;//继续搜索节点P的左子树 } if(top!=0) { p = stack[top--]; if(IsLeafNode(p)) printf("LNode[%d] = %c\t",p->order,p->data);//访问叶子节点 p = p->rchild;//继续搜索节点P的右子树 } }while(top>0||p!=NULL); } /* function HasTwoChildNode()功能:判断给定二叉树的节点是否存在两个孩子节点 */ int HasTwoChildNode(BTree *node) { if((node->lchild!=NULL)&&(node->rchild!=NULL)) return(1); else return(0); } /* function SwapChildNode()功能:交换给定二叉树的所有节点的左、右孩子 */ void SwapChildNode(BTree *header) { BTree * stack[MAX_NODE];//节点的指针栈 BTree *p; int top; p = header; top = 0; do { while(p!=NULL) { stack[++top] = p; p = p->lchild;//继续搜索节点P的左子树 } if(top!=0) { p = stack[top--]; if(HasTwoChildNode(p)) Swap(&p->lchild->data,&p->rchild->data);//交换节点P的左、右孩子 p = p->rchild;//继续搜索节点P的右子树 } }while(top>0||p!=NULL); } int main(int argc, char* argv[]) { BTree * TreeHeader; printf("二叉树创建数据结果:\n"); TreeHeader = CreateBTree(TreeValue1,NODE_COUNT1-1); //TreeHeader = CreateBTree(TreeValue2,NODE_COUNT2-1); if (TreeHeader==0) { printf("二叉树创建失败!\n"); return(0); } else { printf("\n二叉树前序遍历结果:\n"); FirstOrderAccess1(TreeHeader); printf("\n二叉树中序遍历结果:\n"); MiddleOrderAccess(TreeHeader); printf("\n二叉树后序遍历结果:\n"); LastOrderAccess(TreeHeader); //printf("\n二叉树的所有叶子节点:\n"); //PrintLeafNode(TreeHeader); //SwapChildNode(TreeHeader); //printf("\n二叉树交换孩子的结果:\n"); //MiddleOrderAccess(TreeHeader); printf("\n程序运行完毕!\n"); return 0; } } ...展开收缩
(系统自动生成,下载前可以参看下载内容)

下载文件列表

相关说明

  • 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
  • 本站是交换下载平台,提供交流渠道,下载内容来自于网络,除下载问题外,其它问题请自行百度
  • 本站已设置防盗链,请勿用迅雷、QQ旋风等多线程下载软件下载资源,下载后用WinRAR最新版进行解压.
  • 如果您发现内容无法下载,请稍后再次尝试;或者到消费记录里找到下载记录反馈给我们.
  • 下载后发现下载的内容跟说明不相乎,请到消费记录里找到下载记录反馈给我们,经确认后退回积分.
  • 如下载前有疑问,可以通过点击"提供者"的名字,查看对方的联系方式,联系对方咨询.
 相关搜索: // BTree.cpp : Defines the
 输入关键字,在本站1000多万海量源码库中尽情搜索: