資料結構（算法）-樹

#include <iostream>
#include <malloc.h>

using namespace std;


#define MaxSize 100
typedef char ElemType;

typedef struct node{
	ElemType data;
	struct node *left ,*right;
} BTree;

//先序
void preorder(BTree * bt){
	if(bt != NULL){
		printf("%c",bt->data);
		preorder(bt->left);
		preorder(bt->right);

	}
}

//中序
void inoder(BTree * bt){
	if(bt != NULL){
		inoder(bt->left);
		printf("%c",bt->data);
		inoder(bt->right);
	}
}

//後序

void postorder(BTree *bt){
	if(bt != NULL){
		postorder(bt->left);
		postorder(bt->right);
		printf("%c",bt->data);
	}
}


void createTree(BTree **bt, char * str){
	BTree * stack[MaxSize] ,*p;
	int top=-1 , k, j=0;

	char ch;
	*bt =NULL;
	ch=str[j];
	while(ch !='\0'){
		switch(ch){
			case '(' :
				top++;
				stack[top]=p;
				k=1;
				break;
			case ')' :
				top--;
				break;
			case ',' :
				k=2;
				break;
			default:
				p=(BTree *)malloc(sizeof(BTree));
				p->data=ch;
				p->left=p->right=NULL;
				if(*bt ==NULL){
					*bt =p;
				}else{
					switch(k){
						case 1:
							stack[top]->left=p;
							break;
						case 2:
							stack[top]->right=p;
							break;
					}
				}
		}
		j++;
		ch=str[j];
	}
} 

//樹的高度
int BTreeDepth(BTree * bt){
	int leftdep ,rightdep;
	if(bt ==NULL){
		return 0;
	}else {
		leftdep=BTreeDepth(bt->left);
		rightdep=BTreeDepth(bt->right);
		if(leftdep > rightdep){
			return leftdep +1;
		}else {
			return rightdep +1;
		}
	}
}

//樹的葉子結點

int leafCout(BTree * bt){
	if(bt == NULL){
		return 0;
	}else if (bt ->left == NULL && bt ->right ==NULL){
		return 1;
	}else{
		return leafCout(bt->left) + leafCout(bt ->right) +1 ;
	}
}

void main(){
	BTree *b;
	char *s ="A(B(D,E(H,I)),C(G))";
	createTree(&b,s);
	printf("\n 先序周遊：");
	preorder(b);

	printf("\n 中序周遊：");
	inoder(b);
	
	printf("\n 後序周遊：");
	postorder(b);

	printf("\n樹的高度：%d\n",BTreeDepth(b));

	printf("樹的葉子結點：%d\n",leafCout(b));
	
}



           

測試結果

先序周遊：ABDEHICG
中序周遊：DBHEIAGC
後序周遊：DHIEBGCA
樹的高度：4
樹的葉子結點：8
           

版權聲明：本文為CSDN部落客「weixin_34080571」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。

原文連結：https://blog.csdn.net/weixin_34080571/article/details/91701606