我的题目是根据输入的二叉树后序序列(以单个字符作为一个结点的信息)和中序序列,来构
造一棵二叉树,然后输出该树的前序序列,以及该树中所有度为 1 的结点。
#include<stdio.h>
#include<stdlib.h>
#define max 50
typedef char Elemtype;
Elemtype pre[max], in[max], post[max];
typedef struct BTNode{
Elemtype data;
struct BTNode *lchild, *rchild;
}BTree;
/* according to the postorder and inorder travelsal
sequences to create a binary tree */
BTree* create(Elemtype postL, Elemtype postR, Elemtype inL, Elemtype inR){
if(postL > postR)
return NULL;
BTree *root;
root = (BTree*)malloc(sizeof(BTree));
root->data = post[postR]; //后序遍历序列的最后一个结点就是当前树的根结点
int k;
for(k = inL; k <= inR; k++){
if(in[k] == post[postR]) //寻找当前树的根节点在中序遍历序列中的位置
break;
}
int numLeft = k - inL; //root的左子树的结点总数
root->lchild = create(postL, postL + numLeft - 1, inL, k - 1); //root的左孩子所在的区间:中序 in[inL, k-1]
//后序post[postL, postL + numLeft - 1]
root->rchild = create(postL + numLeft, postR - 1, k + 1, inR);
return root; //递归返回根结点地址
}
/* preorder traversal bases on user-defined stack*/
void preorderstack(BTree *root){
BTree *stack[max]; //自定义顺序栈
int top = -1; //栈顶指针
stack[++top] = root; //根结点进栈
BTree *p;
while(top != -1){
p = stack[top--]; //出栈,访问根
printf("%c", p->data);
if(p->rchild != NULL) //若右孩子存在,让它进栈
stack[++top] = p->rchild; //注意,先让右孩子入栈
if(p->lchild != NULL) //若左孩子存在,让它进栈
stack[++top] = p->lchild;
}
}
/* level-order traversal bases on user-defined stack*/
void levelorder(BTree *root){
BTree *queue[max]; //自定义顺序循环队列
int front =0, rear = 0; //队头/尾
rear = (rear +1) % max;
queue[rear] = root; //根结点进队
BTree *p;
while(front != rear){
front = (front + 1)%max;
p = queue[front];
printf("%c", p->data);
if(p->lchild != NULL){
rear = (rear + 1) % max;
queue[rear] = p->lchild;
}
if(p->rchild != NULL){
rear = (rear + 1) % max;
queue[rear] = p->rchild;
}
}
}
int main(){
int n; //树的结点个数
printf("Total number of nodes: ");
scanf("%d", &n);
getchar();
printf("Postorder: ");
for(int i = 0; i < n; i++){
scanf("%c", &post[i]);
}
getchar();
printf("Inorder: ");
for(int i = 0; i < n; i++){
scanf("%c", &in[i]);
}
BTree *root = create(0, n - 1, 0, n - 1);
printf("Preorder: ");
preorderstack(root);
printf("\nLevelorder: ");
levelorder(root);
return 0;
}
这个里面他说的是输入后序中序输出前序和该树中所有度为 1 的结点。您这个是输入节点数和后序中序输出前序和层序啊
仅供参考:
#include <iostream>
#include <stack>
#include <queue>
#include <locale.h>
using namespace std;
typedef struct BiTNode {//二叉树结点
char data; //数据
struct BiTNode *lchild,*rchild; //左右孩子指针
} BiTNode,*BiTree;
int CreateBiTree(BiTree &T) {//按先序序列创建二叉树
char data;
scanf("%c",&data);//按先序次序输入二叉树中结点的值(一个字符),‘#’表示空树
if (data == '#') {
T = NULL;
} else {
T = (BiTree)malloc(sizeof(BiTNode));
T->data = data; //生成根结点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return 0;
}
void Visit(BiTree T) {//输出
if (T->data != '#') {
printf("%c ",T->data);
}
}
void PreOrder(BiTree T) {//先序遍历
if (T != NULL) {
Visit(T); //访问根节点
PreOrder(T->lchild); //访问左子结点
PreOrder(T->rchild); //访问右子结点
}
}
void InOrder(BiTree T) {//中序遍历
if (T != NULL) {
InOrder(T->lchild); //访问左子结点
Visit(T); //访问根节点
InOrder(T->rchild); //访问右子结点
}
}
void PostOrder(BiTree T) {//后序遍历
if (T != NULL) {
PostOrder(T->lchild); //访问左子结点
PostOrder(T->rchild); //访问右子结点
Visit(T); //访问根节点
}
}
void PreOrder2(BiTree T) {//先序遍历(非递归)
//访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,再先序遍历T的右子树。
stack<BiTree> stack;
BiTree p = T;//p是遍历指针
while (p || !stack.empty()) { //栈不空或者p不空时循环
if (p != NULL) {
stack.push(p); //存入栈中
printf("%c ",p->data); //访问根节点
p = p->lchild; //遍历左子树
} else {
p = stack.top(); //退栈
stack.pop();
p = p->rchild; //访问右子树
}
}
}
void InOrder2(BiTree T) {//中序遍历(非递归)
//T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。
//先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。
stack<BiTree> stack;
BiTree p = T;//p是遍历指针
while (p || !stack.empty()) { //栈不空或者p不空时循环
if (p != NULL) {
stack.push(p); //存入栈中
p = p->lchild; //遍历左子树
} else {
p = stack.top(); //退栈,访问根节点
printf("%c ",p->data);
stack.pop();
p = p->rchild; //访问右子树
}
}
}
typedef struct BiTNodePost{
BiTree biTree;
char tag;
} BiTNodePost,*BiTreePost;
void PostOrder2(BiTree T) {//后序遍历(非递归)
stack<BiTreePost> stack;
BiTree p = T;//p是遍历指针
BiTreePost BT;
while (p != NULL || !stack.empty()) {//栈不空或者p不空时循环
while (p != NULL) {//遍历左子树
BT = (BiTreePost)malloc(sizeof(BiTNodePost));
BT->biTree = p;
BT->tag = 'L';//访问过左子树
stack.push(BT);
p = p->lchild;
}
while (!stack.empty() && (stack.top())->tag == 'R') {//左右子树访问完毕访问根节点
BT = stack.top();
stack.pop();//退栈
printf("%c ",BT->biTree->data);
}
if (!stack.empty()) {//遍历右子树
BT = stack.top();
BT->tag = 'R';//访问过右子树
p = BT->biTree;
p = p->rchild;
}
}
}
void LevelOrder(BiTree T) {//层次遍历
if (T == NULL) return;
BiTree p = T;
queue<BiTree> queue;//队列
queue.push(p);//根节点入队
while (!queue.empty()) { //队列不空循环
p = queue.front(); //对头元素出队
printf("%c ",p->data); //访问p指向的结点
queue.pop(); //退出队列
if (p->lchild != NULL) {//左子树不空,将左子树入队
queue.push(p->lchild);
}
if (p->rchild != NULL) {//右子树不空,将右子树入队
queue.push(p->rchild);
}
}
}
int main() {
BiTree T;
setlocale(LC_ALL,"chs");
CreateBiTree(T);
printf("先序遍历 :");PreOrder (T);printf("\n");
printf("先序遍历(非递归):");PreOrder2 (T);printf("\n");
printf("\n");
printf("中序遍历 :");InOrder (T);printf("\n");
printf("中序遍历(非递归):");InOrder2 (T);printf("\n");
printf("\n");
printf("后序遍历 :");PostOrder (T);printf("\n");
printf("后序遍历(非递归):");PostOrder2(T);printf("\n");
printf("\n");
printf("层次遍历 :");LevelOrder(T);printf("\n");
return 0;
}
//ABC##DE#G##F###
//先序遍历 :A B C D E G F
//先序遍历(非递归):A B C D E G F
//
//中序遍历 :C B E G D F A
//中序遍历(非递归):C B E G D F A
//
//后序遍历 :C G E F D B A
//后序遍历(非递归):C G E F D B A
//
//层次遍历 :A B C D E F G
//
/// A
/// /
/// B
/// / \
/// C D
/// / \
/// E F
/// \
/// G