用C语言实现了二叉树的初始化，循环队列与顺序栈的建立。
利用递归与非递归方式实现前序遍历、中序遍历、后序遍历。
利用队列实现了层次遍历。
求得了二叉树带权路径长度
#include<stdio.h>#include<stdlib.h>#define Maxsize 20typedef struct BitNode{/* data */int data;struct BitNode *lchild,*rchild;}BitNode;typedef struct Stack{ //栈及相关操作BitNode *data[Maxsize];int top;}Stack;Stack * initStack(){Stack *s = (Stack *)malloc(sizeof(Stack));s->top=0;return s;}int isStackEmpty(Stack *p){if(p->top==0){return 1;}return -1;}int pushStack(Stack *p,BitNode *node){if(p->top+1>Maxsize){printf("full error,please enlarge Maxsize\n");return -1;}p->data[p->top]=node;p->top++;return 1;}BitNode* popStack(Stack *p){if(p->top==0){return NULL;}BitNode * temp = p->data[p->top-1];p->top--;return temp;}BitNode* getTop(Stack *p){if(p->top==0){return NULL;}BitNode * temp = p->data[p->top-1];return temp;}typedef struct Queue//队列及相关操作{BitNode *data[Maxsize];int rear,front;}Queue;Queue* initQueue(){Queue* p = (Queue *)malloc(sizeof(Queue));p->rear=p->front=0;return p;}int isQueueEmpty(Queue *p){if(p->rear==p->front){return 1;}return -1;}int enQueue(Queue *p,BitNode *node){if((p->rear+1)%Maxsize==p->front){printf("full error,please enlarge Maxsize\n");return -1;}p->data[p->rear]=node;p->rear=(p->rear+1)%Maxsize;return 1;}BitNode* deQueue(Queue *p){if(p->rear==p->front){printf("empty error\n");return NULL;}BitNode *temp =p->data[p->front];p->front = (p->front+1)%Maxsize;return temp;}BitNode* creatTree(){ //手动建树BitNode* t = (BitNode*)malloc(sizeof(BitNode));int data;scanf("%d",&data);if(data==-1){return NULL;}t->data=data;printf("Please input %d 's left tree data:\n if input number is -1, would not build tree\n",data);t->lchild = creatTree();printf("Please input %d 's right tree data:\n if input number is -1, would not build tree\n",data);t->rchild = creatTree();return t;}BitNode* creatTree2(int num){ //自动建树if(num<=0){return NULL;}BitNode *t = (BitNode*)malloc(sizeof(BitNode));t->data = num;t->lchild=creatTree2(num-1);t->rchild=creatTree2(num-2);return t;}void preOrder1(BitNode* t){ //前序遍历if(t!=NULL){printf("%d ",t->data);preOrder1(t->lchild);preOrder1(t->rchild);}}void preOrder2(BitNode* t){Stack * stack = initStack();BitNode *p = t;while (p!=NULL||isStackEmpty(stack)!=1){if(p!=NULL){printf("%d ",p->data);pushStack(stack,p);p=p->lchild;}else{p=popStack(stack);p=p->rchild;}}}void inOrder1(BitNode* t){ //中序遍历if(t!=NULL){inOrder1(t->lchild);printf("%d ",t->data);inOrder1(t->rchild);}}void inOrder2(BitNode* t){Stack * stack = initStack();BitNode *p = t;while (p!=NULL||isStackEmpty(stack)!=1){if(p!=NULL){pushStack(stack,p);p=p->lchild;}else{p=popStack(stack);printf("%d ",p->data);p=p->rchild;}}}void postOrder1(BitNode* t){ //后序遍历if(t!=NULL){postOrder1(t->lchild);postOrder1(t->rchild);printf("%d ",t->data);}}void postOrder2(BitNode* t){BitNode *p =t,*temp=NULL;Stack *stack = initStack();while(p!=NULL||isStackEmpty(stack)!=1){if(p!=NULL){pushStack(stack,p);p=p->lchild;}else{p = getTop(stack);if(p->rchild!=NULL&&p->rchild!=temp){p=p->rchild;}else{p =popStack(stack);printf("%d ",p->data);temp = p;p= NULL;}}}}void levelOrder(BitNode* t){ //层次遍历Queue *p= initQueue();BitNode * temp;enQueue(p,t);while(isQueueEmpty(p)!=1){temp = deQueue(p);printf("%d ",temp->data);if(temp->lchild!=NULL){enQueue(p,temp->lchild);}if(temp->rchild!=NULL){enQueue(p,temp->rchild);}}}int WPL(BitNode *t,int deepth){ //求二叉树带权路径长度if(t!=NULL){if(t->lchild==NULL&&t->rchild==NULL){return t->data*deepth;}else{return WPL(t->lchild,deepth+1)+WPL(t->rchild,deepth+1);}}else{return 0;}}int main(){//BitNode* t = creatTree();BitNode * t = creatTree2(5); //根节点的数值大小preOrder1(t); //前序printf("\n");preOrder2(t);printf("\n");inOrder1(t); //中序printf("\n");inOrder2(t);printf("\n");postOrder1(t); //后序printf("\n");postOrder2(t); printf("\n");levelOrder(t); //层次printf("\n%d",WPL(t,0)); //求二叉树带权路径长度}
