|
二叉树的操作 #include <stdlibh> #include <stdioh> #define queuesize #define null typedef char datatype; typedef struct node{ datatype data; struct node *lchild*rchild; }bintnode;//定义二叉链表结点结构 typedef bintnode *bintree;//定义二叉链表指针类型 typedef struct{ int frontrear; bintree data[queuesize];//循环队列元素类型为二叉链表结点指针 int count; }cirqueue;//循环队列结构定义 main()//主函数 {//建立二叉树的二叉链表表示并进行先序遍历中序遍历后序遍历和按层次遍历 //求出所有叶子和结点总数 bintree t=null; int n; printf(please input nodes of bintree:\n); createbintree(&t);//建立二叉链表 printf(the preorder is:); preorder(t);//对二叉树t进行先序遍历 printf(\n); printf(the inorder is:); inorder(t);//对二叉树t进行中序遍历 printf(\nthe postorder is:); postorder(t);//对二叉树t进行后序遍历 printf(\nthe leverorder is:); leverorder(t);//对二叉树t进行按层次遍历 n=leave(t);// 求出二叉树的叶子数n printf(\nthe leave of bintree is: %dn);//打印二叉树的叶子总数 if (n){//当叶子数不为 printf(\nthe list of leave is:); leavelist(t);//输出所有的叶子 } else printf(\nno leave!);//输出无叶子（即空树）信息 printf(\nthe nodes of bintree is: %d\nnodes(t));//输出二叉树的总结点数 } createbintree(bintree *t) {//输入二叉树的先序遍历序列创建二叉链表 char ch; if ((ch=getchar())== )//如果读入空格字符创建空树 *t=null; else{ *t=(bintnode*)malloc(sizeof(bintnode));//申请根结点*t空间 (*t)>data=ch;//将结点数据ch放入根结点的数据域 createbintree(&(*t)>lchild);//建左子树 createbintree(&(*t)>rchild);//建右子树 }//end of if }//end of creatbintree preorder(bintree t) {//对二叉树进行先序遍历 if (t){ printf(%ct>data); preorder(t>lchild); preorder(t>rchild); }//end of if }//end of preorder inorder(bintree t) {//对二叉树进行中序遍历 if (t){ inorder(t>lchild); printf(%ct>data); inorder(t>rchild); }//end of if }//end of inorder postorder(bintree t) {//对二叉树进行后序遍历 if (t){ postorder(t>lchild); postorder(t>rchild); printf(%ct>data); }//end of if }//end of postorder error(char *message) {//出错时调用的返回出错信息终止程序运行的函数 fprintf(stderrerror:%s\nmessage); exit(); } leverorder(bintree t) { cirqueue *q; bintree p; q=(cirqueue*)malloc(sizeof(cirqueue));//申请循环队列空间 q>rear=q>front=q>count=;//将循环队列初始化为空 q>data[q>rear]=t;q>count++;q>rear=(q>rear+)%queuesize;//将根结点入队 while (q>count)//若队列不为空做以下操作 if (q>data[q>front]){//当队首元素不为空指针做以下操作 p=q>data[q>front];//取队首元素*p printf(%cp>data);//打印*p结点的数据域信息 q>front=(q>front+)%queuesize;q>count;//队首元素出队 if (q>count==queuesize)//若队列为队满则打印队满信息退出程序的执行 error(the queue full!); else{//若队列不满将*p结点的左孩子指针入队 q>count++;q>data[q>rear]=p>lchild; q>rear=(q>rear+)%queuesize; }//enf of if if (q>count==queuesize)//若队列为队满则打印队满信息退出程序的执行 error(the queue full!); else{//若队列不满将*p结点的右孩子指针入队 q>count++;q>data[q>rear]=p>rchild; q>rear=(q>rear+)%queuesize; }//end of if }//end of if else{//当队首元素为空指针将空指针出队 q>front=(q>front+)%queuesize;q>count;} }//end of leverorder int leave(bintree t) {//求以t为树根的二叉树的叶子总数 if (!t)//若根结点为 return ;//返回叶子数 else//若根结点非空 if ((t>lchild==null)&&(t>rchild==null))//若根结点的左右孩子都为空 return ;//返回叶子数 else //根结点的左右孩子有个不为空 return(leave(t>lchild)+leave(t>rchild)); //叶子数为左子树的叶子数加右子树中的叶子数 } leavelist(bintree t) { if (t){ leavelist(t>lchild);//输出左子树中的所有叶子 if ((t>lchild==null)&&(t>rchild==null)) //若根结点为叶子则输出叶子的数据域信息 printf(%ct>data); leavelist(t>rchild);//输出右子树中的所有叶子 }//end of if }//end of inorder int nodes(bintree t) { if (!t)//若二叉树为空树 return ;//返回结点数 else //若二叉树非空 return nodes(t>lchild)+nodes(t>rchild)+; //二叉树的结点总数为左右子树的结点总数加上（根结点） }//end of node |
