dw网站制作的源代码,网站建设智能优化,平台推广网站排名,万户网络网站顾问第1关#xff1a;实现二叉树的创建
#include binary_tree.hBiTreeNode* CreatBiTree(char* s, int i, int len)
// 利用先序遍历创建二叉树
// 参数#xff1a;先序遍历字符串s#xff0c;字符串初始下标i0#xff0c;字符串长度len。
// 返回#xff1…
第1关实现二叉树的创建
#include binary_tree.hBiTreeNode* CreatBiTree(char* s, int i, int len)
// 利用先序遍历创建二叉树
// 参数先序遍历字符串s字符串初始下标i0字符串长度len。
// 返回二叉树
{// 请在这里补充代码完成本关任务/********** Begin *********/if(ilen||s[i]#)return NULL;BiTreeNode*rootnew BiTreeNode(s[i]);i;root-leftCreatBiTree(s,i,len); i; root-rightCreatBiTree(s,i,len);return root;/********** End **********/
}void InOrder(BiTreeNode* root)
// 二叉树的中序遍历
// 参数二叉树根节点root
// 输出中间没有空格末尾不换行。
{// 请在这里补充代码完成本关任务/********** Begin *********/if(rootNULL)return;if(root-left!NULL){InOrder(root-left);}printf(%c,root-data);if(root-right!NULL){InOrder(root-right);}/********** End **********/}第2关计算二叉树的深度和节点个数
#include binary_tree.hint GetTreeDepth(BiTreeNode* root)
// 计算该二叉树的深度
// 参数二叉树根节点root
// 返回二叉树的深度
{// 请在这里补充代码完成本关任务/********** Begin *********/int depthval,n,m;if (rootNULL) depthval0;else{mGetTreeDepth(root-left);nGetTreeDepth(root-right);depthval1(mn?m:n);
}return depthval;/********** End **********/
}int GetNodeNumber(BiTreeNode* root)
// 计算该二叉树的总节点个数
// 参数二叉树根节点root
// 返回二叉树的总节点个数
{// 请在这里补充代码完成本关任务/********** Begin *********/int count,n,m;if(rootNULL) count 0;else{mGetNodeNumber(root-left);nGetNodeNumber(root-right);countmn1;}return count;/********** End **********/
}int GetLeafNodeNumber(BiTreeNode* root)
// 计算该二叉树的叶子节点个数
// 参数二叉树根节点root
// 返回二叉树的叶子节点个数
{// 请在这里补充代码完成本关任务/********** Begin *********/
if (rootNULL) return 0;
else if(root-leftNULLroot-rightNULL) return 1;
else return GetLeafNodeNumber(root-left) GetLeafNodeNumber(root-right);/********** End **********/
}
第3关递归实现二叉树左右子树交换
#include binary_tree.hBiTreeNode* BiTreeChange(BiTreeNode* root)
// 实现二叉树左右子树的交换递归法
// 参数二叉树根节点root
// 返回二叉树
{// 请在这里补充代码完成本关任务/********** Begin *********/if (!root) return NULL;else{BiTreeNode* pnew BiTreeNode;proot-left;root-leftroot-right;root-rightp;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.hBiTreeNode* BiTreeChangeStack(BiTreeNode* root)
// 实现二叉树左右子树的交换栈实现
// 参数二叉树根节点root
// 返回二叉树
{// 请在这里补充代码完成本关任务/********** Begin *********/if(!root) return NULL;stackBiTreeNode* s; s.push(root); //最后弹出保证根不变while(root!s.empty()) {BiTreeNode*p new BiTreeNode;proot-right;root-rightroot-left;root-leftp;if(root-right)s.push(root-right);if(root-left){rootroot-left;}else{roots.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.hvoid HierarchyOrder(BiTreeNode* root)
// 二叉树的层次遍历队列实现
// 参数二叉树根节点root
// 输出二叉树的层次遍历中间没有空格末尾不换行。
{// 请在这里补充代码完成本关任务/********** Begin *********/queueBiTreeNode* 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 **********/}
