使用C语言构建基本的二叉树数据结构
二叉树结构常用的一些初始化代码
#include #include typedefstructNode{ intdata; Node*leftchild; Node*rightchild; }Node; /* 初始化一棵二叉树排序树。 */ voidInitBinaryTree(Node**root,intelem) { *root=(Node*)malloc(sizeof(Node)); if(!(*root)) { printf("Memoryallocationforrootfailed.\n"); return; } (*root)->data=elem; (*root)->leftchild=NULL; (*root)->rightchild=NULL; } /* 向二叉树排序树中插入节点。 */ voidInsertNode(Node*root,intelem) { Node*newnode=NULL; Node*p=root,*last_p=NULL; newnode=(Node*)malloc(sizeof(Node)); if(!newnode) { printf("Memoryallocationfornewnodefailed.\n"); return; } newnode->data=elem; newnode->leftchild=NULL; newnode->rightchild=NULL; while(NULL!=p) { last_p=p; if(newnode->datadata) { p=p->leftchild; } elseif(newnode->data>p->data) { p=p->rightchild; } else { printf("Nodetobeinsertedhasexisted.\n"); free(newnode); return; } } p=last_p; if(newnode->datadata) { p->leftchild=newnode; } else { p->rightchild=newnode; } } /* 创建一棵二叉树排序树。 */ voidCreatBinarySearchTree(Node**root,intdata[],intnum) { inti; for(i=0;i { if(NULL==*root) { InitBinaryTree(root,data[i]); } else { InsertNode(*root,data[i]); } } }
根据前序序列、中序序列构建二叉树
函数定义
btrebuildTree(char*pre,char*in,intlen);
参数:
*pre:前序遍历结果的字符串数组
*in:中序遍历结果的字符串数组
len:树的长度
例如:
前序遍历结果:abcdefgh
中序遍历结果:cbedfagh
算法思想
- 递归思想,递归的终止条件是树的长度len==0
- 在中序遍历的数组中找到前序数组的第一个字符,记录在中序数组中的位置index.如果找不到,说明前序遍历数组和中序遍历数组有问题,提示错误信息,退出程序即可;找到index后,新建一个二叉树节点t,t->item=*pre,然后递归的求t的左孩子和有孩子
- 递归的左孩子:voidrebuildTree(pre+1,in,index)
- 递归的右孩子:voidrebuildTree(pre+(index+1),in+(index+1),len-(index+1))
实现代码(c语言版)
/** *Description:根据前序和中序构建二叉树 */ btrebuildTree(char*pre,char*in,intlen) { btt; if(len<=0) { //递归终止 t=NULL; }else { //递归主体 intindex=0; while(index<len&&*(pre)!=*(in+index)) { index++; } if(index>=len) { printf("前序遍历或者中序遍历数组有问题!\n"); exit(-1); } t=(structbintree*)malloc(sizeof(structbintree)); t->item=*pre; t->lchild=rebuildTree(pre+1,in,index); t->rchild=rebuildTree(pre+(index+1),in+(index+1),len-(index+1)); } returnt; }
根据中序序列、后序序列构建二叉树
函数定义
/** *中序、后序序列构建二叉树 */ btree*rebuildTree(char*order,char*post,intlen);
算法思想
中序序列:C、B、E、D、F、A、H、G、J、I
后序序列:C、E、F、D、B、H、J、I、G、A
递归思路:
- 根据后序遍历的特点,知道后序遍历最后一个节点为根节点,即为A
- 观察中序遍历,A左侧CBEDF为A左子树节点,A后侧HGJI为A右子树节点
- 然后递归的构建A的左子树和后子树
实现代码(c代码)
/** *根据中序和后序序列构建二叉树 *(ps:昨晚参加阿里笔试,等到最后说可以免笔试直接面试,今天估计还是要根据学校筛选,哈哈,为了这点 *也得参加阿里笔试,不能让自己的学校受到鄙视) */ #include<stdio.h> #include<stdlib.h> #include<string.h> intn; typedefstructbtree{ structbtree*lchild; structbtree*rchild; chardata; }btree; /** *中序、后序序列构建二叉树 */ btree*rebuildTree(char*order,char*post,intlen) { btree*t; if(len<=0){ returnNULL; }else{ intindex=0; while(index<len&&*(post+len-1)!=*(order+index)){ index++; } t=(btree*)malloc(sizeof(btree)); t->data=*(order+index); t->lchild=rebuildTree(order,post,index); t->rchild=rebuildTree(order+index+1,post+index,len-(index+1)); } returnt; } /** *前序遍历二叉树 */ voidpreTraverse(btree*t) { if(t){ printf("%c",t->data); preTraverse(t->lchild); preTraverse(t->rchild); } } intmain(void) { inti; char*post,*order; btree*t; while(scanf("%d",&n)!=EOF){ post=(char*)malloc(n); order=(char*)malloc(n); getchar(); for(i=0;i<n;i++) scanf("%c",order+i); getchar(); for(i=0;i<n;i++) scanf("%c",post+i); t=rebuildTree(order,post,n); preTraverse(t); printf("\n"); free(post); free(order); } return0; }