二叉树的相关操作

问题描述

实现以下算法：
1．以二叉链表表示二叉树，建立一棵二叉树；
2．输出二叉树的中序遍历结果；
3．输出二叉树的前序遍历结果；
4．输出二叉树的后序遍历结果；
5. 输出二叉树的层序遍历结果。
6.交换二叉树每个结点的左孩子和右孩子。
7．利用二叉树计算表达式的值。建立表达式树，并计算表达式的值
8. 树的层序zigzag输出，树按层序遍历，奇数层从左至右输出，偶数层从右至左输出。

---

提示：以下是本篇文章正文内容，下面案例可供参考

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;

typedef struct BTNode *Position;
typedef Position BTree;
struct BTNode
{
    
    char data;
    Position lChild, rChild;
};
//建立二叉函数 
BTree CreateBTree(BTree bt)
{
    
    char ch;
    
    printf("节点: ");

    fflush(stdin);         /* 清空缓存区 */
    scanf("%c", &ch);
    fflush(stdin);
    if (ch != '#')//出现#即为该节点没有左（右）孩子 
    {
    
        
        bt = new BTNode;
        bt->data = ch;  
        bt->lChild = NULL;
        bt->rChild = NULL;
        printf("%c的左孩子: ", bt->data);
        bt->lChild = CreateBTree(bt->lChild);
        printf("%c的右孩子: ", bt->data);
        bt->rChild = CreateBTree(bt->rChild);
    }
    return bt;
}
//先序遍历 
void PreOrder(BTree bt)
{
    
    if (bt != NULL)
    {
    
        printf("%c", bt->data);
        PreOrder(bt->lChild);
        PreOrder(bt->rChild);
    }
}
//中序遍历 
void InOrder(BTree bt)
{
    
    if (bt != NULL)
    {
    
        InOrder(bt->lChild);
        printf("%c", bt->data);
        InOrder(bt->rChild);
    }
}
//后序遍历
void PostOrder(BTree bt)
{
    
    if (bt != NULL)
    {
    
        PostOrder(bt->lChild);
        PostOrder(bt->rChild);
        printf("%c", bt->data);
    }
}
//层序遍历 
void CenOrder(BTree bt)
{
    
    BTree temp[100];
    int in=0,out=0;
    temp[in++]=bt;
    while(in>out){
    
    	if(temp[out]){
    
    		printf("%c",temp[out]->data);
    		temp[in++]=temp[out]->lChild;
    		temp[in++]=temp[out]->rChild;
		}
		out++;
	}
}
//zigzag层序遍历 
void ZigZagOrder(BTree bt)
{
    
    BTree temp[100];
    int in=0,out=0,k,i,j;
    temp[in++]=bt;
    while(in>out){
    
    	if(temp[out]){
    
    		temp[in++]=temp[out]->lChild;
    		temp[in++]=temp[out]->rChild;
		}
		out++;
	}
	k=ceil(log(in+1)/log(2));
	printf("%c",temp[0]->data);
	for(i=2;i<=k;i++){
    
		if(i%2==1){
    
			for(j=pow(2,i-1);j<=pow(2,i)-1;j++){
    
				if(temp[j-1]!=NULL)
				printf("%c",temp[j-1]->data);
			}
		}
		else{
    
			for(j=pow(2,i)-1;j>=pow(2,i-1);j--){
    
				if(temp[j-1]!=NULL)
				printf("%c",temp[j-1]->data);
			}
		}
	}
}
//交换每个节点的左孩子和右孩子
BTree Change(BTree bt)
{
    
	BTree t;
	if(bt->data!='#'){
    
		if(bt->lChild != NULL&&bt->rChild != NULL){
    
			Change(bt->lChild);
	    	Change(bt->rChild);
		}
	    t=bt->lChild;
	    bt->lChild=bt->rChild;
	    bt->rChild=t;
	}
	return bt;
}

int main()
{
    
    int choose=-1;
    printf("1、建立二叉树\n");
	printf("2、先序遍历\n");
	printf("3、中序遍历\n");
	printf("4、后序遍历\n");
	printf("5、层序遍历\n");
	printf("6、交换每个节点的左孩子和右孩子\n");
	printf("7、zigzag层序遍历\n");
	printf("0、退出\n\n");
    while(choose!=0){
    
    	printf("请选择：");
    	scanf("%d", &choose);
    	switch (choose){
    
    		case 1:
    			BTree bt;
    			bt = CreateBTree(bt);
    			printf("成功建立二叉树\n");
    			break;
    		case 2:
    			printf("先序遍历：");
    			PreOrder(bt);
    			printf("\n");
    			break;
    		case 3:
    			printf("中序遍历：");
    			InOrder(bt);
    			printf("\n");
    			break;
    		case 4:
    			printf("后序遍历：");
    			PostOrder(bt);
    			printf("\n");
    			break;
			case 5:
				printf("层序遍历：");
				CenOrder(bt);
				printf("\n");
				break;
			case 6:
				Change(bt);
				printf("交换成功！\n");
				break;
			case 7:
				printf("zigzag层序遍历：");
				ZigZagOrder(bt);
				printf("\n");
				break;
		}
	}
	getchar();
    return 0;
}

实验结果

建立二叉树