数据结构中二叉树的一些操作

2.5 Project 4: 二叉树遍历实验

（1）问题描述

对任意输入的表示某二叉树的字符序列，创建该二叉树，并完成二叉树的先序递归、中序递归、后序递归、中序非递归和层次等遍历算法，以及求二叉树的叶子数、高度等应用算法。注：所需栈和队列的各函数由自已实现不能用STL，二叉树的存储结构可以使用二叉链表表示。例如，如下图所示二叉树，其输入字符序列为： ABD#G###CE##FH###，该字符串类似于二叉树的先序遍历结果，若二叉树中某结点无左或右孩子时则用字符“#”代替。 

图1 二叉树

（2）实验步骤

Step 1.  输入带“#”号的先序序列，写一创建二叉树的二叉链表存储结构的函数Create，对图1的二叉树，其输入为： ABD#G###CE##FH###。函数原型：treePointer Create (  );

Step 2.  输入给定二叉树的中序和后序序列，写一创建二叉树的二叉链表存储结构的函数CreatePreIn，对图1的二叉树，其输入为：DGBAECHF和GDBEHFCA。函数原型：treePointer CreateInPost(char Inorder[], char Postorder[], int n);

Step 3.   写出二叉树的先序、中序、后序等递归遍历算法，其函数名分别为inorder, preorder 和 postorder。

Step 4.  完成有关栈的基本操作，实现栈ADT。(Project31中已经完成。)

Step 5.  完成有关队列的基本操作，实现队列ADT。(Project32中已经完成。)

Step 6.  写出二叉树的中序非递归遍历算法iterInorder。

Step 7. 写出二叉树的层次遍历算法levelOrder。

Step 8. 写出求二叉树叶结点数的函数leaf，类似也请写出求二叉树的度为1结点数nodesOne、度为2结点数nodesTwo、结点数nodes等函数。

Step9. 写出求二叉树高度的函数height。

Step 10. 计算给定的任一表达式树的值的算法eval。如右图的表达式树，其值为10。输入：+1## #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; #define MAX_SIZE 100 //Chapter 1 #define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t)) //Chapter 1 #define MAX_TERMS 101 //Chapter 2 #define MAX_POLYS 15 //Chapter 2 #define MAX_STACK_SIZE 100 //Chapter 3 #define MAX_QUEUE_SIZE 100 //Chapter 3 #define MEMORY_SIZE 100 //Chapter 3 #define MAX_STACKS 10 //Chapter 3 #define MAX_QUEUES 10 //Chapter 3 #define IS_EMPTY(first) (!(first)) //Chapter 4 #define IS_FULL(temp) (!(temp)) //Chapter 4 #define MAX_ELEMENTS 200 //Chapter 5 #define HEAP_FULL(n) (n == MAX_ELEMENTS - 1) //Chapter 5 #define HEAP_EMPTY(n) (!n) //Chapter 5 #define MAX_VERTICES 50 //Chapter 6 #define MALLOC(p,s,type) if (!((p) = (type)malloc(s))) { fprintf(stderr,"Insufficient memory"); exit(EXIT_FAILURE); } #define REALLOC(p,s) if (!(realloc((void*)p,s))) { fprintf(stderr,"Insufficient memory"); exit(EXIT_FAILURE); } #define CALLOC(p,n,s,type) if (!((p) = (type)calloc(n,s))) { fprintf(stderr,"Insufficient memory"); exit(EXIT_FAILURE); } #define FREE(p) if (!(p)) { free(p);p = NULL; } #endif ​ 2.BiTree.h

#ifndef BITREE_H
#define BITREE_H
struck node;
typedef struct node{
    char data;
    treePointer leftChild,rightChild;
};
treePointer Create();
void inorder(treePointer ptr);
void preOrder(treePointer ptr);
void postorder(treePointer ptr);
void interInorder(treePointer node);
void levelOrder(treePointer ptr);
int Leaf(treePointer bt);
int nodesOne(treePointer bt);
int nodesTwo(treePointer bt);
int nodes(treePointer bt );
int Depth (treePointer bt);
int eval(treePointer bt );
#endif

#include
#include
#includedata = ch;
        bt->left = create();
        bt->right = create();

    }
    
}
void inorder(treePointer ptr){
    inorder(ptr->left);
    print("%c",ptr->data);
    inorder(ptr->right);

}
void preOrder(treePointer ptr){
    print("%c",ptr->data);
    preOrder(ptr->left);
    preOrder(ptr->right);
void postorder(treePointer ptr){
    postorder(ptr->left);
    postorder(ptr->right);
    print("%c",ptr->data);
}
void interInorder(treePointer node) {//中序非递归遍历
	int  top = -1; 
	element stack[MAX_STACK_SIZE];
	for (; ; ) {
		for (; node; node = node->leftChild)
			Push_Sq(node, stack, top);
		int Flag = Pop(stack, top, node);
		if (!Flag)  break;
		printf("%c", node->data);
		node = node->rightChild;
	}
}

void  levelOrder(treePointer ptr) {//层次遍历
	int  front = 0, rear = 0;
	element queue[MAX_QUEUE_SIZE]; 
	if (!ptr)  return;   
	AddQ_Sq(ptr, queue, front, rear);  
	for (; ; ) {
		int Flag = DeleteQ_Sq(queue, front, rear, ptr);  
		if (Flag) {
			printf("%d", ptr->data);
			if (ptr->leftChild)  
				AddQ_Sq(ptr->leftChild, queue, front, rear); 
			if (ptr->rightChild) 
				AddQ_Sq(ptr->rightChild, queue, front, rear);
		} 
		else  break;  
	} 
}


int Leaf(treePointer bt) {//叶结点数
	if (bt == NULL) return 0;
	else if ((bt->leftChild == NULL) && (bt->rightChild == NULL)) return 1;
	else return (Leaf(bt->leftChild) + Leaf(bt->rightChild));
}

int nodesOne(treePointer bt) {//度为1结点数
	if (bt == NULL) return 0;
	else if ((bt->leftChild != NULL) && (bt->rightChild == NULL)) return (nodesOne(bt->leftChild) + 1);
	else if ((bt->leftChild == NULL) && (bt->rightChild != NULL)) 
        return (nodesOne(bt->rightChild) + 1);
	else 
        return (nodesOne(bt->leftChild) + nodesOne(bt->rightChild));
}

int nodesTwo(treePointer bt) {//度为2结点数
	if (bt == NULL) return 0;
	else if ((bt->leftChild != NULL) && (bt->rightChild != NULL))
         return (nodesTwo(bt->leftChild) + nodesTwo(bt->rightChild)+1);
	else 
         return (nodesTwo(bt->leftChild) + nodesTwo(bt->rightChild));
}

int nodes(treePointer bt) {//结点数
	if (bt == NULL) return 0;
	else return (nodes(bt->leftChild) + nodes(bt->rightChild)+1);
}

int Depth(treePointer bt) {//二叉树深度
	int LeftDepth, RightDepth;
	if (bt == NULL) return 0;
	else {
		LeftDepth = Depth(bt->leftChild);
		RightDepth = Depth(bt->rightChild);
		return (LeftDepth > RightDepth) ?
			(LeftDepth + 1) : (RightDepth + 1);
	}
}

int eval(treePointer bt) {//表达式树计算
	if (bt->data >= '0' && bt->data <= '9')return bt->data - '0';
	else if (bt->data == '+')return (eval(bt->leftChild) + eval(bt->rightChild));
	else if (bt->data == '-')return (eval(bt->leftChild) - eval(bt->rightChild));
	else if (bt->data == '*')return (eval(bt->leftChild) * eval(bt->rightChild));
	else if (bt->data == '/')return (eval(bt->leftChild) / eval(bt->rightChild));
}

#include
#include
#include"Public.h"
#include"BiTree.h"


void main() {
	treePointer bt;
	bt = Create();
	interInorder(bt);
	system("pause");
}