文件名称：二叉树的遍历与应用二叉链表
文件大小：7KB
文件格式：TXT
更新时间：2012-07-07 12:18:54
对树的基本应用
// 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" #define 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; } }