二叉树的定义与简单应用

#include <stdio.h> #include<stdlib.h> #define null 0 #define maxsize 100 typedef struct tree { /*声明树的结构*/ struct tree *left; /*存放左子树的指针*/ struct tree *right; /*存放又子树的指针*/ int data; /*存放节点的内容*/ } treenode, * btree; /*声明二叉树的链表*/ btree q[maxsize]; int count; /* 在二叉排序树中插入结点*/ btree insertnode(btree root,int node) { btree newnode; /*声明新结点指针*/ btree currentnode; /*声明当前结点指针*/ btree parentnode; /*声明父结点指针*/ newnode=(btree)malloc(sizeof(treenode));/*建立新结点的内存空间*/ newnode->data =node; /*结点的内容*/ newnode->left =null; /*设置右指针初值*/ newnode->right =null; /*设置左指针初值*/ if(root==null) return newnode; else { currentnode=root; while(currentnode!=null) {/*寻找要插入的位置*/ parentnode =currentnode; if(currentnode->data >node ) currentnode=currentnode->left ; else currentnode=currentnode->right ; } if(parentnode->data >node) parentnode->left =newnode; else parentnode->right =newnode; return root; } } /*建立二叉树 */ btree createbtree(int *data,int len) { btree root=null; /*根结点*/ int i; for(i=0;i<len;i++)/*建立二叉排序树*/ root=insertnode(root,data[i]); return root; } /* 中序遍历打印二叉排序树*/ void inorderbtree(btree root) { btree p=root; if(p!=null){ inorderbtree(p->left ); printf("%3d",p->data ); inorderbtree(p->right ); } } typedef btree ElemType ; /*typedef char ElemType ; */ /*定义队列结点类型*/ typedef struct QueueNode { ElemType data; struct QueueNode *next; } QueueNode; /*定义队列*/ typedef struct linkQueue { QueueNode * front; QueueNode * rear; }linkQueue; /*初始化队列*/ void initQueue(linkQueue * q) { q->front=q->rear =null; } /*判断队列是否为空*/ int QueueEmpty(linkQueue * Q) { return (Q->front==null)&&(Q->rear==null); /*实际上只须判断队头指针是否为空即可*/ } /*入队操作*/ void EnQueue(linkQueue *Q,ElemType x) { /*将元素x插入链队列尾部*/ QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode)); /*申请新结点*/ p->data=x; p->next=null; if(QueueEmpty(Q)) /*将x插入空队列*/ Q->front=Q->rear=p; else { /*x插入非空队列的尾*/ Q->rear->next=p; /*p链到原队尾结点后*/ Q->rear=p; /*队尾指针指向新的尾*/ } } /*出队操作*/ ElemType DeQueue (linkQueue *Q) { ElemType x; QueueNode *p; if(QueueEmpty(Q)) { printf("Queue underflow");/*下溢*/ exit(1) ; } p=Q->front; /*指向对头结点*/ x=p->data; /*保存对头结点的数据*/ Q->front=p->next; /*将对头结点从链上摘下*/ if(Q->rear==p)/*原队中只有一个结点，删去后队列变空，此时队头指针已为空*/ Q->rear=NULL; free(p); /*释放被删队头结点*/ return x; /*返回原队头数据*/ } void visit(btree p) { if(p->data!=1) printf("%3d",p->data); else printf("%3c",p->data); } //将原二叉树补全使其成为完全二叉树后按层次遍历序列输出 void breadthFirst2(btree root) { btree p,tmp; linkQueue * q; tmp=(treenode *)malloc(sizeof(treenode)); q=(linkQueue *)malloc(sizeof(linkQueue)); tmp->data=1; initQueue(q); p=root; if(p!=null) { EnQueue(q,p); while(!QueueEmpty(q)) { p=DeQueue(q); visit(p); if(p->data!=1) { if(p->left!=null) EnQueue(q,p->left); else EnQueue(q,tmp); if(p->right!=null) EnQueue(q,p->right); else EnQueue(q,tmp); } } } } //层次遍历输出 void breadthFirst(btree root) { btree p; linkQueue * q; q=(linkQueue *)malloc(sizeof(linkQueue)); initQueue(q); p=root; if(p!=null) { EnQueue(q,p); while(!QueueEmpty(q)) { p=DeQueue(q); visit(p); if(p->left!=null) EnQueue(q,p->left); if(p->right!=null) EnQueue(q,p->right); } } } //用递归算法输出二叉树的叶子结点 void leafprint(btree bt) { if(bt) { if(bt->left==NULL&&bt->right==NULL) printf(" %d ",bt->data); leafprint(bt->left); leafprint(bt->right); } } //用递归算法求二叉树的叶子节点个数 int leafcount(btree bt) { if(bt) { leafcount(bt->left); leafcount(bt->right); if(bt->left==NULL&&bt->right==NULL) count++; } return count; } //用递归算法求二叉树的深度 int deeptree(btree bt) { int hl,hr,max; if(bt) { hl=deeptree(bt->left); hr=deeptree(bt->right); max=hl>hr?hl:hr; return max+1; } else return 0; } //用非递归算法实现二叉树的先序遍历输出 void xianxu(btree bt) { btree p; int top=-1; if(bt) { top++; //根结点入栈 q[top]=bt; while(top>-1) //栈不为空时循环 { p=q[top]; //出栈并访问该结点 top--; printf(" %d ",p->data); if(p->right) //右孩子结点入栈 { top++; q[top]=p->right; } if(p->left) //左孩子结点入栈 { top++; q[top]=p->left; } } } } //用非递归算法实现二叉树的中线序遍历输出 void zhongxu(btree bt) { btree p; int top=-1; if(bt) { p=bt; while(top>-1||p) { while(p) //扫描*p的所有左结点并入栈 { top++; q[top]=p; p=p->left; } if(top>-1) { p=q[top]; //出栈*p结点 top--; printf(" %d ",p->data); //访问之 p=p->right; //扫描*p的右孩子结点 } } } } //用非递归算法实现二叉树的后序遍历输出 void houxu(btree bt) { btree p; int top=-1,flag; //栈顶指针初始化 if(bt) { do { while(bt) //将bt的所有左结点入栈 { top++; q[top]=bt; bt=bt->left; } p=NULL; //p指向栈顶结点的前一个已访问的结点 flag=1; //设置bt的访问标记为已访问过 while(top>-1&&flag) { bt=q[top]; //栈顶元素出栈 if(bt->right==p) //右孩子不存在或右孩子已被访问过 { printf(" %d ",bt->data); //访问bt结点 top--; p=bt; //p指向被访问的结点 } else { bt=bt->right; //bt指向右孩子结点 flag=0; //设置未被访问的标记 } } }while(top>-1); } } //用递归算法实现二叉树的先序遍历输出 void preorder(btree bt) { if(bt) { printf(" %d ",bt->data); preorder(bt->left); preorder(bt->right); } } //用递归算法实现二叉树的中序遍历输出 void inorder(btree bt) { if(bt) { inorder(bt->left); printf(" %d ",bt->data); inorder(bt->right); } } //用递归算法实现二叉树的后续遍历输出 void postorder(btree bt) { if(bt) { postorder(bt->left); postorder(bt->right); printf(" %d ",bt->data); } } void main() { int nodelist[maxsize],i,n; btree root; int k; printf("--------------------------------------------------------\n"); printf("\n* * * * 您好!欢迎您使用二叉树的操作实现系统! * * * *\n"); printf("\n--------------------------------------------------------\n"); printf("*******请选择您要进行的操作*********\n"); do{ printf(" 1.......创建二叉树\n"); printf(" 2.......分别用递归和非递归先序遍历二叉树\n"); printf(" 3.......分别用递归和非递归中序遍历二叉树\n"); printf(" 4.......分别用递归和非递归后序遍历二叉树\n"); printf(" 5.......求二叉树的高度\n"); printf(" 6.......层次遍历二叉树\n");