Educoder头歌数据结构-树和二叉树及其应用

头歌实践平台答案educoder

数据结构-树和二叉树及其应用

第1关二叉树的创建

/*************************************************************date: March 2019二叉树的创建  实现文件    
**************************************************************/
BiTree CreateBiTree()
// 利用先序遍历创建二叉树，返回根指针。
{// 请在这里补充代码，完成本关任务/********** Begin *********//*typedef char ElemType;typedef struct BiTNode{ ElemType data;struct BiTNode *lchild,*rchild;}BiTNode, *BiTree;*/BiTree root;char ch;scanf("%c",&ch);if(ch=='#')root = NULL;else{root = (BiTree)malloc(sizeof(BiTNode));if(root!=NULL){root-> data = ch;root->lchild = CreateBiTree();root->rchild = CreateBiTree();}}return root;/********** End **********/
}void InOrder(BiTree T)
// 二叉树的中序遍历
// 参数：二叉树根指针T
// 输出：中间没有空格，末尾不换行。
{// 请在这里补充代码，完成本关任务/********** Begin *********/if(T)//T!=NULL{InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}/********** End **********/
}

第2关计算二叉树的深度和结点个数

/*************************************************************date: March 2019计算二叉树的深度和结点个数  实现文件    
**************************************************************/
#include 
#include 
#include 
#include "binary_tree.h"int GetTreeDepth(BiTree T)
// 计算二叉树的深度
// 参数：二叉树根指针T
// 返回：二叉树的深度
{// 请在这里补充代码，完成本关任务/********** Begin *********/int lsd=0,rsd=0,max=0;if(T!=NULL){lsd = GetTreeDepth(T->lchild);rsd = GetTreeDepth(T->rchild);(lsd>rsd)?max=(lsd+1):max=(rsd+1);}return max;/********** End **********/
}int GetNodeNumber(BiTree T)
// 计算二叉树的总结点个数
// 参数：二叉树根指针T
// 返回：二叉树的总结点个数
{// 请在这里补充代码，完成本关任务/********** Begin *********/int count=0;if(T!=NULL)count = GetNodeNumber(T->lchild) + GetNodeNumber(T->rchild) + 1;//根节点return count;/********** End **********/
}int GetLeafNodeNumber(BiTree T)
// 计算二叉树的叶子结点个数
// 参数：二叉树根指针T
// 返回：二叉树的叶子结点个数
{// 请在这里补充代码，完成本关任务/********** Begin *********/int count=0;if(T!=NULL){if(T->lchild==NULL&&T->rchild==NULL)count = 1;elsecount = GetLeafNodeNumber(T->lchild) + GetLeafNodeNumber(T->rchild) ;}return count;/********** End **********/
}

实现二叉树左右子树交换

/*************************************************************date: March 2019实现二叉树左右子树交换  实现文件    
**************************************************************/
#include 
#include 
#include 
#include "binary_tree.h"BiTree BiTreeChange(BiTree T)
// 实现二叉树左右子树的交换
// 参数：二叉树根指针T
// 返回：二叉树根指针
{// 请在这里补充代码，完成本关任务/********** Begin *********//*typedef struct BiTNode
{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree; //¶þ²æÁ´±íµÄÀàÐͶ¨Òå*/int max=10000;BiTNode* str[max];int k=0;str[k]=0;if(T){k++;str[k]=T->lchild;T->lchild=T->rchild;T->rchild=str[k];T->lchild=BiTreeChange(T->lchild);T->rchild=BiTreeChange(T->rchild);k++;}return T;/********** End **********/
}void PreOrder(BiTree T)
// 二叉树的先序遍历
// 参数：二叉树根指针T
// 输出：二叉树的先序遍历，中间没有空格，末尾不换行。
{// 请在这里补充代码，完成本关任务/********** Begin *********/if(T!=NULL){printf("%c",T->data);PreOrder(T->lchild);PreOrder(T->rchild);}/********** End **********/
}

层次遍历二叉树

/*************************************************************层次遍历二叉树  实现文件 更新于2020年6月8日
**************************************************************/void HierarchyOrder(BiTree T)
// 二叉树的层次遍历（借助队列实现）
// 参数：二叉树根指针T
// 输出：二叉树的层次遍历，中间没有空格，末尾不换行。
{/*typedef char ElemType; //二叉链表中结点元素类型typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;}BiTNode, *BiTree; //二叉链表的类型定义#define  MAXSIZE 100     //最大长度typedef BiTNode* QElemType; //队列中数据元素类型typedef  struct {QElemType  *elem;     //数组空间的起始地址int front; // 存放队头元素的下标int rear;  // 存放队尾元素的下一个位置的下标                                                      }SqQueue;*/// 请在这里补充代码，完成本关任务/********** Begin *********/
//	int e;SqQueue Q;//定义队列SQ_Initiate(Q);//初始化队列if(T!=NULL){SQ_In(Q,T);//入根}while(!SQ_IsEmpty(Q)){SQ_Out(Q,T);printf("%c",T->data);if(T->lchild!=NULL)SQ_In(Q,T->lchild);//入根if(T->rchild!=NULL)SQ_In(Q,T->rchild);//入根}/********** End **********/
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！