单选题
单选题题解
3、由中序判断左右子树,中序遍历顺序左子树，根节点，右子树，先序遍历的左子树元素在右子树元素之前，后序遍历顺序是的左子树，右子树，根节点
6、“二叉树中的度“是指树中最大的结点度，叶子结点是终端结点，是度为0 的结点。
二叉树的度是指树中所以结点的度数的最大值。二叉树的度小于等于2，因为二叉树的定义要求二叉树中任意结点的度数（结点的分支数）小于等于2 ，并且两个子树有左右之分，顺序不可颠倒。
叶子结点就是度为0的结点，也就是没有子结点的结点叶子。如n0表示度为0的结点数，n1表示度为1的结点，n2表示度为2的结点数。在二叉树中：n0=n2+1；N=n0+n1+n2（N是总结点）。
8 、二叉树定义：二叉树是每个节点最多有两个子树的有序树，通常子树的根被称作“左子树”和“右子树”。”
具有3个结点的二叉树，有2层和3层两种情况
若有2层，则只有一种情况
若有3层，则每层只有1个结点，一共有2*2种情况
函数题
6-1 先序输出叶结点 (30分)
本题要求按照先序遍历的顺序输出给定二叉树的叶结点。
函数接口定义：
void PreorderPrintLeaves( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };
函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。
输出样例（对于图中给出的树）：
Leaf nodes are: D E H I
代码
#include <stdio.h> #include <stdlib.h> typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; BinTree CreatBinTree(); void PreorderPrintLeaves( BinTree BT ); int main() { BinTree BT = CreatBinTree(); printf("Leaf nodes are:"); PreorderPrintLeaves(BT); printf("\n"); return 0; } BinTree CreatBinTree() { BinTree Bt = NULL; int n; ElementType ch; scanf("%d",&n); for(int i = 0;i < n;i ++) { getchar(); scanf("%c",&ch); Bt = Insert(Bt,ch); } return Bt; } /* 你的代码将被嵌在这里 */ if(BT) { if(BT->Left==NULL&&BT->Right==NULL) printf(" %c",BT->Data); //格式为一个空格跟着一个字符。 PreorderPrintLeaves(BT->Left); PreorderPrintLeaves(BT->Right); }
编程题
7-1 列出叶结点 (20分)
对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。
输入格式：
首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 “-”。编号间以 1 个空格分隔。
输出格式：
在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
8 1 - - - 0 - 2 7 - - - - 5 - 4 6
输出样例：
4 1 5
代码（未完，不大会）
#include<iostream> #include<stdio.h> #include<queue> #include<vector> #include<algorithm> using namespace std; struct Node { int l, r; }q[10]; int v[10]; queue <int> Q; vector <int> ans; // 层序输出 void bfs() { int len = Q.size(); for (int i = 0; i < len; i++) { int num = Q.front(); Q.pop(); if (q[num].l == -1 && q[num].r == -1) // 左右子树都为空，直接写进去 ans.push_back(num); if (q[num].l != -1) Q.push(q[num].l); if (q[num].r != -1) Q.push(q[num].r); } if (Q.size()) bfs(); } int main() { memset(q, 0, sizeof(q)); memset(v, 0, sizeof(v)); int n; scanf("%d", &n); char a, b; for (int i = 0; i < n; i++) { scanf(" %c %c", &a, &b); if (a == '-') q[i].l = -1; else { q[i].l = a - '0'; v[a - '0'] = 1; } if (b == '-') q[i].r = -1; else { q[i].r = b - '0'; v[b - '0'] = 1; } } int root; for (int i = 0; i < n; i++) { if (v[i] == 0) { root = i; break; } } Q.push(root); bfs(); vector <int>::iterator it; for (it = ans.begin(); it != ans.end(); it++) { if (it != ans.begin()) printf(" "); printf("%d", *it); } cout << endl; }
