二叉树详解（C语言版）.rar

//二叉树 #include"BinTree.h" #include"Queue.h" #include"Stack.h" //二叉树初始化 void InitBinTree(BinTree *bt, ElemType ref) { bt->root = NULL;//根设置为空 bt->refvalue = ref; //设置停止标记 } ///////////// 二叉树的创建 /////////////////////// //方式一：使用二级指针 //供外部调用 void CreateBinTree_1(BinTree *bt) { CreateBinTree_1(bt,&(bt->root)); } //内部实现 void CreateBinTree_1(BinTree *bt, BinTreeNode **t) { ElemType Item; //接收数据 scanf("%c",&Item); if(Item == bt->refvalue) //判断输入是否为一个结束标记 (*t) = NULL;//是 说明这棵二叉树是空树 else {//否 //创建树（子树）根结点 (*t) = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert((*t) != NULL); (*t)->data = Item;//为结点赋值 CreateBinTree_1(bt,&((*t)->leftChild)); //创建左子树 CreateBinTree_1(bt,&((*t)->rightChild)); //创建右子树 } } //方式二：使用指针引用方式 //对外调用 void CreateBinTree_2(BinTree *bt) { CreateBinTree_2(bt,bt->root); } //内部实现 void CreateBinTree_2(BinTree *bt, BinTreeNode *&t) { ElemType Item;//接收数据 scanf("%c",&Item); if(Item == bt->refvalue)//判断输入是否为一个结束标记 t = NULL;//是 说明这棵二叉树是空树 else {//否 //创建树（子树）根结点 t = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert(t != NULL); t->data = Item;//为结点赋值 CreateBinTree_2(bt,t->leftChild); //创建左子树 CreateBinTree_2(bt,t->rightChild); //创建右子树 } } //方式三：通过返回值返回二叉树 void CreateBinTree_3(BinTree *bt) { bt->root = CreateBinTree_3_(bt); } BinTreeNode* CreateBinTree_3_(BinTree *bt) { ElemType Item; //接收数据 scanf("%c",&Item); if(Item == bt->refvalue) //判断输入是否为一个结束标记 return NULL;//是 说明这棵二叉树是空树 else {//否 //创建树（子树）根结点 BinTreeNode *t = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert(t != NULL); t->data = Item;//为结点赋值 t->leftChild = CreateBinTree_3_(bt);//创建左子树 t->rightChild = CreateBinTree_3_(bt);//创建右子树 return t;//返回所创建的树 } } //方式4：传入要创建的二叉树的串进行创建 void CreateBinTree_4(BinTree *bt, char *str) { CreateBinTree_4(bt,bt->root,str); } void CreateBinTree_4(BinTree *bt, BinTreeNode *&t, char *&str) { if(*str == bt->refvalue) //判断输入是否为一个结束标记 t = NULL; //是 说明这棵二叉树是空树 else { //创建树（子树）根结点 t = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert(t != NULL); t->data = *str;//为结点赋值 CreateBinTree_4(bt,t->leftChild,++str);//创建左子树 CreateBinTree_4(bt,t->rightChild,++str);//创建右子树 } } ///////////// 二叉树的遍历 /////////////////////// //2 //先序遍历 void PreOrder(BinTree *bt) { PreOrder(bt->root); } void PreOrder(BinTreeNode *t) { if(t != NULL)//树不为空 { printf("%c ",t->data);//访问（子树）根结点 PreOrder(t->leftChild);//访问左子树 PreOrder(t->rightChild);//访问右子树 } } //中序遍历 void InOrder(BinTree *bt) { InOrder(bt->root); } void InOrder(BinTreeNode *t) { if(t != NULL) { InOrder(t->leftChild);//访问左子树 printf("%c ",t->data);//访问（子树）根 InOrder(t->rightChild);//访问右子树 } } //后序遍历 void PostOrder(BinTree *bt) { PostOrder(bt->root); } void PostOrder(BinTreeNode *t) { if(t != NULL) { PostOrder(t->leftChild);//访问左子树 PostOrder(t->rightChild);//访问右子树 printf("%c ",t->data);//访问（子树）根 } } //层次遍历 void LevelOrder(BinTree *bt) { LevelOrder(bt->root); } void LevelOrder(BinTreeNode *t) { if(t != NULL) { BinTreeNode *v; LinkQueue Q; //创建队列 InitQueue(&Q); //对队列初始化 EnQueue(&Q,t);//将二叉树根结点（地址）入队 while(!QueueIsEmpty(&Q)) //判断队列是否为空 {//不空 GetHead(&Q,&v);//取（子树）根结点（地址） DeQueue(&Q);//将（子树）根结点（地址）出队 printf("%c ",v->data);//打印出（子树）根结点的数据 if(v->leftChild != NULL) //判断该结点的左树是否为空 EnQueue(&Q,v->leftChild); //否 将左子树（地址）入队 if(v->rightChild != NULL) //判断该结点右子树是否为空 EnQueue(&Q,v->rightChild);//否 将右子树（地址）入队 } } } ////////////////////// 二叉树的其他操作 //////////////////// //3 //求以bt为根结点的二叉树结点个数 int Size(BinTree *bt) { return Size(bt->root); } int Size(BinTreeNode *t) { if(t == NULL) //判断二叉树是否为空 return 0;//是 记录个数为0 else//否 该二叉树的结点个数=左子树结点个数+右子树结点个数+根结点个数（1） return Size(t->leftChild)+Size(t->rightChild)+1; } //求取二叉树的高度 int Height(BinTree *bt) { return Height(bt->root); } int Height(BinTreeNode *t) { if(t == NULL) //判断二叉树是否为空 return 0;//是 记录高度为0 else {//否 //求取左子树高度 int left_height = Height(t->leftChild); //求取右子树高度 int right_height = Height(t->rightChild); //返回：该二叉树高度=左子树与右子树的最大高度+1 return (left_height>right_height ? left_height:right_height)+1; } } //查找key值所在的结点 BinTreeNode* Search(BinTree *bt, ElemType key) { return Search(bt->root,key); } BinTreeNode* Search(BinTreeNode *t, ElemType key) { if(t == NULL) //判断二叉树是否为空 return NULL; //是 说明不存在，返回空 if(t->data == key) //否 判断结点值是否等于key值 return t; //是 返回结点地址 //没找到 BinTreeNode *p = Search(t->leftChild,key); //查找左子树 if(p != NULL)//判断是否找到 return p;//找到 返回结点地址 // 没找到 return Search(t->rightChild,key); // 查找右子树，返回查找结果 } //在bt二叉树中查找p结点的父结点 BinTreeNode* Parent(BinTree *bt, BinTreeNode *p) { return Parent(bt->root,p); } BinTreeNode* Parent(BinTreeNode *t, BinTreeNode *p) { if(t==NULL || p==NULL) //判断二叉树和结点是否为空 return NULL;//是 返回空 //否 if(t->leftChild==p || t->rightChild==p)//判断t的左右孩子是否为p return t;// 是 返回其父结点 //否 BinTreeNode *q = Parent(t->leftChild,p);//查找t的左子树 if(q != NULL)//判断左子树中是否找到满足条件的结点 return q;// 是 返回 //否 return Parent(t->rightChild,p);//查找右子树 } //获取二叉树的左子树 BinTreeNode* LeftChild(BinTreeNode *p) { if(p != NULL) return p->leftChild; return NULL; } //获取二叉树的右子树 BinTreeNode* RightChild(BinTreeNode *p) { if(p != NULL) return p->rightChild; return NULL; } //判断二叉树是否为空 bool BinTreeEmpty(BinTree *bt) { return bt->root==NULL;//判断根结点是否为空 } //拷贝二叉树:bt2拷贝到bt1 void Copy(BinTree *bt1, BinTree *bt2) { Copy(bt1->root,bt2->root); } void Copy(BinTreeNode *&t1, BinTreeNode *t2) { if(t2 == NULL) //判断t2是否为空 t1 = NULL;//是 则无需拷贝，直接将t1置空 else {//否 //为t2（子树）根结点拷贝到t1（子树）根结点 t1 = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert(t1 != NULL); t1->data = t2->data; Copy(t1->leftChild,t2->leftChild);//拷贝t2左子树到t1左子树 Copy(t1->rightChild,t2->rightChild);//拷贝t2右子树到t1右子树 } } //清空操作 void BinTreeClear(BinTree *bt) { BinTreeClear(bt->root); } void BinTreeClear(BinTreeNode *&t) { if(t != NULL) //判断二叉树是否为空 {//否 BinTreeClear(t->leftChild);//清空左子树 BinTreeClear(t->rightChild);//清空右子树 free(t);//清空（子树）根 t = NULL; } } ////////////////////////////////////////////////////////////// //4 //先序遍历的非递归实现 void PreOrder_1(BinTree *bt) { PreOrder_1(bt->root); } void PreOrder_1(BinTreeNode *t) { if(t != NULL) //判断二叉树是否为空 { SeqStack st; //申请一个栈 InitStack(&st); //初始化栈 BinTreeNode *p; Push(&st,t); //将二叉树的根结点入栈 while(!IsEmpty(&st)) //判断栈顶是否为空 {//否 GetTop(&st,&p);//获取栈顶结点 Pop(&st);//出栈 printf("%c ",p->data);//打印数据 /*这里需要注意的是栈结构是先进后出的，所以后访问的结点先入栈*/ if(p->rightChild != NULL) //判断右子树是否为空 Push(&st,p->rightChild); //否 入栈 if(p->leftChild != NULL) //判断左子树是否为空 Push(&st,p->leftChild); //否 入栈 } } } //中序遍历