头歌实践平台-数据结构-二叉树及其应用

第1关：实现二叉树的创建

#include "binary_tree.h"BiTreeNode* CreatBiTree(char* s, int &i, int len)
// 利用先序遍历创建二叉树
// 参数：先序遍历字符串s，字符串初始下标i=0，字符串长度len。
// 返回：二叉树
{// 请在这里补充代码，完成本关任务/********** Begin *********/if(i>=len||s[i]=='#')return NULL;BiTreeNode*root=new BiTreeNode(s[i]);i++;root->left=CreatBiTree(s,i,len); i++;   root->right=CreatBiTree(s,i,len);return root;/********** End **********/
}void InOrder(BiTreeNode* root)
// 二叉树的中序遍历
// 参数：二叉树根节点root
// 输出：中间没有空格，末尾不换行。
{// 请在这里补充代码，完成本关任务/********** Begin *********/if(root==NULL)return;if(root->left!=NULL){InOrder(root->left);}printf("%c",root->data);if(root->right!=NULL){InOrder(root->right);}/********** End **********/}

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

#include "binary_tree.h"int GetTreeDepth(BiTreeNode* root)
// 计算该二叉树的深度
// 参数：二叉树根节点root
// 返回：二叉树的深度
{// 请在这里补充代码，完成本关任务/********** Begin *********/int depthval,n,m;if (root==NULL) depthval=0;else{m=GetTreeDepth(root->left);n=GetTreeDepth(root->right);depthval=1+(m>n?m:n);
}return depthval;/********** End **********/
}int GetNodeNumber(BiTreeNode* root)
// 计算该二叉树的总节点个数
// 参数：二叉树根节点root
// 返回：二叉树的总节点个数
{// 请在这里补充代码，完成本关任务/********** Begin *********/int count,n,m;if(root==NULL) count= 0;else{m=GetNodeNumber(root->left);n=GetNodeNumber(root->right);count=m+n+1;}return count;/********** End **********/
}int GetLeafNodeNumber(BiTreeNode* root)
// 计算该二叉树的叶子节点个数
// 参数：二叉树根节点root
// 返回：二叉树的叶子节点个数
{// 请在这里补充代码，完成本关任务/********** Begin *********/
if (root==NULL) return 0;
else if(root->left==NULL&&root->right==NULL) return 1;
else return GetLeafNodeNumber(root->left)+ GetLeafNodeNumber(root->right);/********** End **********/
}

第3关：递归实现二叉树左右子树交换

#include "binary_tree.h"BiTreeNode* BiTreeChange(BiTreeNode* root)
// 实现二叉树左右子树的交换（递归法）
// 参数：二叉树根节点root
// 返回：二叉树
{// 请在这里补充代码，完成本关任务/********** Begin *********/if (!root) return NULL;else{BiTreeNode* p=new BiTreeNode;p=root->left;root->left=root->right;root->right=p;BiTreeChange(root->left);BiTreeChange(root->right);}return root;/********** End **********/
}void PreOrder(BiTreeNode* root)
// 二叉树的前序遍历
// 参数：二叉树根节点root
// 输出：二叉树的前序遍历，中间没有空格，末尾不换行。
{// 请在这里补充代码，完成本关任务/********** Begin *********/if (!root) {return;}else{printf("%c",root->data);PreOrder(root->left);PreOrder(root->right);}/********** End **********/
}

第4关：非递归实现二叉树左右子树交换

#include "binary_tree.h"BiTreeNode* BiTreeChangeStack(BiTreeNode* root)
// 实现二叉树左右子树的交换（栈实现）
// 参数：二叉树根节点root
// 返回：二叉树
{// 请在这里补充代码，完成本关任务/********** Begin *********/if(!root) return NULL;stack<BiTreeNode*> s; s.push(root);     //最后弹出保证根不变while(root&&!s.empty()) {BiTreeNode*p =new BiTreeNode;p=root->right;root->right=root->left;root->left=p;if(root->right)s.push(root->right);if(root->left){root=root->left;}else{root=s.top();s.pop();}}return root;/********** End **********/
}void PostOrder(BiTreeNode* root)
// 二叉树的后序遍历
// 参数：二叉树根节点root
// 输出：二叉树的后序遍历，中间没有空格，末尾不换行。
{// 请在这里补充代码，完成本关任务/********** Begin *********/if(!root) return;else{PostOrder(root->left);PostOrder(root->right);printf("%c",root->data);}/********** End **********/
}

第5关：层次遍历二叉树

#include "binary_tree.h"void HierarchyOrder(BiTreeNode* root)
// 二叉树的层次遍历（队列实现）
// 参数：二叉树根节点root
// 输出：二叉树的层次遍历，中间没有空格，末尾不换行。
{// 请在这里补充代码，完成本关任务/********** Begin *********/queue<BiTreeNode*> q;  // 创建队列对象  if(root!=NULL)  q.push(root);while(!q.empty()) {printf("%c",q.front()->data);if(q.front()->left)  q.push(q.front()->left);    if (q.front()->right)  q.push(q.front()->right);q.pop();}/********** End **********/}