赞
踩
本关任务:利用先序遍历创建二叉树,并给出相应二叉树的中序遍历结果。
-
- BiTreeNode* CreatBiTree(char* s, int &i, int len)
-
- // 利用先序遍历创建二叉树
-
- // 参数:先序遍历字符串s,字符串初始下标i=0,字符串长度len。
-
- // 返回:二叉树
-
- {
-
- // 请在这里补充代码,完成本关任务
-
- /********** Begin *********/
-
- BiTreeNode* root;
-
- char c = s[i ++];
-
- if(c == '#' || i >= len) { // 遍历到空节点的时候将指针指向NULL
-
- root = NULL;
-
- } else{
-
- root = new BiTreeNode(c); //开辟新的内存空间
-
- root->left = CreatBiTree(s, i, len); //递归建立左子树
-
- root->right = CreatBiTree(s, i, len); // 递归建立右子树
-
- }
-
- return root;
-
- /********** End **********/
-
- }
-
- void InOrder(BiTreeNode* root)
-
- {
-
- // 请在这里补充代码,完成本关任务
-
- /********** Begin *********/
-
- if(root == NULL) return; // 遇到空结点时返回
-
- InOrder(root->left); //中序遍历,左->根->右
-
- printf("%c", root->data);
-
- InOrder(root->right);
-
- /********** End **********/
-
- }
本关任务:给定一棵二叉树,计算该二叉树的深度、总节点个数和叶子节点个数。
-
- int GetTreeDepth(BiTreeNode* root)
- // 计算该二叉树的深度
- // 参数:二叉树根节点root
- // 返回:二叉树的深度
- {
- // 请在这里补充代码,完成本关任务
- /********** Begin *********/
- if(root == NULL) return 0; //遇到空结点,说明该以当前root为根的子树深度为零
- int n = GetTreeDepth(root->left); // 左子树深度
- int m = GetTreeDepth(root->right); //右子树深度
- if(m > n) return m + 1; // 根节点深度为1,故返回 n + 1
- else return n + 1;
-
- /********** End **********/
- }
-
- int GetNodeNumber(BiTreeNode* root)
- // 计算该二叉树的总节点个数
- // 参数:二叉树根节点root
- // 返回:二叉树的总节点个数
- {
- // 请在这里补充代码,完成本关任务
- /********** Begin *********/
- if(root == NULL) return 0;
- return GetNodeNumber(root->left) + GetNodeNumber(root->right) + 1;
- //用递归求左子树节点个数, 右子树节点个数,加上根节点(为1)
- /********** End **********/
- }
-
- int GetLeafNodeNumber(BiTreeNode* root)
- // 计算该二叉树的叶子节点个数
- // 参数:二叉树根节点root
- // 返回:二叉树的叶子节点个数
- {
- // 请在这里补充代码,完成本关任务
- /********** Begin *********/
- if(root == NULL) return 0;
- if(root->left == NULL && root->right == NULL) return 1;
- //左右均为空,当前根节点即为上一层的叶子节点,返回值为1
- return GetLeafNodeNumber(root->left) + GetLeafNodeNumber(root->right);
- //根节点不算叶子节点,不用 + 1(和求节点个数区分开!)
- /********** End **********/
- }
本关任务:给定一棵二叉树,使用递归的方法实现二叉树的左右子树交换,并输出交换后的二叉树的先(前)序遍历结果。
- BiTreeNode* BiTreeChange(BiTreeNode* root)
- // 实现二叉树左右子树的交换(递归法)
- // 参数:二叉树根节点root
- // 返回:二叉树
- {
- // 请在这里补充代码,完成本关任务
- /********** Begin *********/
- BiTreeNode* ch; //创建一个临时变量来储存,用于交换左右子树
- if(root){
- ch = root->left;
- root->left = root->right;
- root->right = ch;
- // 对于每一个根节点,先交换其左右叶子节点,然后再分别左右子树递归,进行下一轮交换
- root->left = BiTreeChange(root->left);
- root->right = BiTreeChange(root->right);
- }
- return root; // 返回二叉树的根节点root
- /********** End **********/
- }
-
-
- void PreOrder(BiTreeNode* root)
- // 二叉树的前序遍历
- // 参数:二叉树根节点root
- // 输出:二叉树的前序遍历,中间没有空格,末尾不换行。
- {
- // 请在这里补充代码,完成本关任务
- /********** Begin *********/
- if(root == NULL) return; //前序遍历 :遇到空结点返回;根->左->右
- printf("%c", root->data);
- PreOrder(root->left);
- PreOrder(root->right);
-
- /********** End **********/
- }
本关任务:给定一棵二叉树,使用非递归的方式实现二叉树左右子树交换,并输出后序遍历结果。
栈存储的是未交换过左右节点的节点,每次循环弹出栈顶元素,交换其左右子树。
如果左右节点不为空,则入栈,等后续处理
- BiTreeNode* BiTreeChangeStack(BiTreeNode* root)
- // 实现二叉树左右子树的交换(栈实现)
- // 参数:二叉树根节点root
- // 返回:二叉树
- {
- // 请在这里补充代码,完成本关任务
- /********** Begin *********/
- stack <BiTreeNode*> s;
-
- if(root == NULL) return NULL;
- s.push(root);
- while(!s.empty()){
- BiTreeNode* t = s.top(); s.pop(); //取出栈顶元素
- //交换
- BiTreeNode* p = t->left;
- t->left = t->right;
- t->right = p;
-
- if(t->left)
- s.push(t->left);
- if (t->right)
- s.push(t->right);
-
- }
- return root;
- /********** End **********/
- }
用队列也可以^ ^ 贴一份队列的代码
道理是一样的,队列里存储的是未进行交换过的节点
- BiTreeNode* BiTreeChangeStack(BiTreeNode* root)
- // 实现二叉树左右子树的交换(栈实现)
- // 参数:二叉树根节点root
- // 返回:二叉树
- {
- // 请在这里补充代码,完成本关任务
- /********** Begin *********/
- queue <BiTreeNode*> q;
-
- if(root == NULL) return NULL;
- q.push(root);
- while(!q.empty()){
- BiTreeNode* t = q.front(); q.pop(); //取出队首元素
- //交换
- BiTreeNode* p = t->left;
- t->left = t->right;
- t->right = p;
-
- if(t->left)
- q.push(t->left);
- if (t->right)
- q.push(t->right);
-
- }
- return root;
- /********** End **********/
- }
本关任务:在HierarchyOrder
中实现二叉树的层次遍历并输出结果,中间没有空格,末尾不换行。
- void HierarchyOrder(BiTreeNode* root)
- // 二叉树的层次遍历(队列实现)
- // 参数:二叉树根节点root
- // 输出:二叉树的层次遍历,中间没有空格,末尾不换行。
- {
- // 请在这里补充代码,完成本关任务
- /********** Begin *********/
- if(root == NULL) return;
- queue <BiTreeNode*> q;
- q.push(root);
- while(!q.empty()){
- BiTreeNode* t = q.front(); q.pop();
- printf("%c",t->data);
- if(t->left) //相当于t->left != NULL
- q.push(t->left);
- if(t->right)
- q.push(t->right);
- }
- /********** End **********/
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。