赞
踩
第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关 非递归实现二叉树左右子树交换
-
- #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关 层次遍历二叉树
-
-
- #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 **********/
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。