第1关 实现二叉树的创建
#include "binary_tree.h"
BiTreeNode* CreatBiTree(char* s, int &i, int len)
// 利用先序遍历创建二叉树
// 参数:先序遍历字符串s,字符串初始下标i=0,字符串长度len。
// 返回:二叉树
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
BiTreeNode *root;
char chk;
chk=s[i++];
if(chk=='#')
root=NULL;
else
{
root=(BiTreeNode*)malloc(sizeof(BiTreeNode));
root->data=chk;
if(root!=NULL)
{
root->left=CreatBiTree(s,i,len);
root->right=CreatBiTree(s,i,len);
}
}
return root;
/********** End **********/
}
void InOrder(BiTreeNode* root)
// 二叉树的中序遍历
// 参数:二叉树根节点root
// 输出:中间没有空格,末尾不换行。
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(root)
{
InOrder(root->left);
printf("%c",root->data);
InOrder(root->right);
}
/********** End **********/
}
第2关 计算二叉树的深度和节点个数
#include "binary_tree.h"
int sum=0;
int leaf=0;
int GetTreeDepth(BiTreeNode* root)
// 计算该二叉树的深度
// 参数:二叉树根节点root
// 返回:二叉树的深度
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
int m=0,n=0,max=0;
if(root)
{
m=GetTreeDepth(root->left);
n=GetTreeDepth(root->right);
(m>n)?max=(m+1):max=(n+1);
}
return max;
/********** End **********/
}
int GetNodeNumber(BiTreeNode* root)
// 计算该二叉树的总节点个数
// 参数:二叉树根节点root
// 返回:二叉树的总节点个数
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(root)
{
sum++;
GetNodeNumber(root->left);
GetNodeNumber(root->right);
}
return sum;
/********** End **********/
}
int GetLeafNodeNumber(BiTreeNode* root)
// 计算该二叉树的叶子节点个数
// 参数:二叉树根节点root
// 返回:二叉树的叶子节点个数
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(root)
{
if(root->left==root->right)
leaf++;
GetLeafNodeNumber(root->left);
GetLeafNodeNumber(root->right);
}
return leaf;
/********** End **********/
}
第3关 递归实现二叉树左右子树交换
#include "binary_tree.h"
BiTreeNode* BiTreeChange(BiTreeNode* root)
// 实现二叉树左右子树的交换(递归法)
// 参数:二叉树根节点root
// 返回:二叉树
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(root==NULL)return NULL;
BiTreeNode* temp=root->left;
root->left=root->right;
root->right=temp;
if(root->left!=NULL)
BiTreeChange(root->left);
if(root->right!=NULL)
BiTreeChange(root->right);
return root;
/********** End **********/
}
void PreOrder(BiTreeNode* root)
// 二叉树的前序遍历
// 参数:二叉树根节点root
// 输出:二叉树的前序遍历,中间没有空格,末尾不换行。
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(root)
{
printf("%c",root->data);
PreOrder(root->left);
PreOrder(root->right);
}
/********** End **********/
}
第4关 非递归实现二叉树左右子树交换文章来源:https://www.toymoban.com/news/detail-754482.html
#include "binary_tree.h"
BiTreeNode* BiTreeChangeStack(BiTreeNode* root)
// 实现二叉树左右子树的交换(栈实现)
// 参数:二叉树根节点root
// 返回:二叉树
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(root==NULL)return NULL;
stack<BiTreeNode*> swap;
swap.push(root->left);
swap.push(root->right);
root->left=swap.top();
swap.pop();
root->right=swap.top();
if(root->left!=NULL)
BiTreeChangeStack(root->left);
if(root->right!=NULL)
BiTreeChangeStack(root->right);
return root;
/********** End **********/
}
void PostOrder(BiTreeNode* root)
// 二叉树的后序遍历
// 参数:二叉树根节点root
// 输出:二叉树的后序遍历,中间没有空格,末尾不换行。
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(root)
{
PostOrder(root->left);
PostOrder(root->right);
printf("%c",root->data);
}
/********** End **********/
}
第5关 层次遍历二叉树文章来源地址https://www.toymoban.com/news/detail-754482.html
#include "binary_tree.h"
void HierarchyOrder(BiTreeNode* root)
// 二叉树的层次遍历(队列实现)
// 参数:二叉树根节点root
// 输出:二叉树的层次遍历,中间没有空格,末尾不换行。
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
queue<BiTreeNode*> t;
if(root)
t.push(root);
while(!t.empty())
{
BiTreeNode* T=t.front();
t.pop();
printf("%c",T->data);
if(T->left)
t.push(T->left);
if(T->right)
t.push(T->right);
}
/********** End **********/
}
到了这里,关于头歌数据结构实训参考---二叉树及其应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!