[数据结构与算法]c语言对数的遍历以及使用

初始化一棵树

struct TreeNode* Create(){
	int val;
	scanf("%d", &val);
	
	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
	if (val <= 0) {
		return NULL;
	}
	
	if (!root) {
		printf("创建失败\n");
	}
 
	if (val > 0) {
		root->val = val;
		root->left = Create();
		root->right = Create();
	}
	 
	return root;
}

//先序
void PreOrderTree(struct TreeNode* root) {
	if (root == NULL) {
		return;
	}
	printf("%d ", root->val);
	PreOrderTree(root->left);
	PreOrderTree(root->right);
}




//中序
void InOrderTree(struct TreeNode* root) {
	if (root == NULL) {
		return;
	}
	InOrderTree(root->left);
	printf("%d ", root->val);
	InOrderTree(root->right);
}



//后序
void PostOrderTree(struct TreeNode* root) {
	if (root == NULL) {
		return;
	}
	PostOrderTree(root->left);
	PostOrderTree(root->right);
	printf("%d ", root->val);
}


//使用
int main()
{
	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
 
    //第二种构建方式：
    //root = Create();
	
	CreateTree(&(root));
	printf("先序排列为：");
	PreOrderTree(root);
	printf("\n中序排列为：");
	InOrderTree(root);
	printf("\n后序排列为：");
	PostOrderTree(root);
	return 0;
}

还有一些基本应用

//深度
int maxDepth(struct TreeNode* root) {
	if (root == NULL) {
		return 0;
	}
	else {
		int maxLeft = maxDepth(root->left), maxRight = maxDepth(root->right);
		if (maxLeft > maxRight) {
			return 1 + maxLeft;
		}
		else {
			return 1 + maxRight;
		}
	}
}


//层序：
//借助队列，根左右顺序入队


//叶子节点数
int LeafNodeNum(struct TreeNode* root) {
	if (root == NULL) {
		return 0;
	}
 
	if (root->left == NULL&&root->right == NULL) {
		return 1;
	}
	else {
		return LeafNodeNum(root->left) + LeafNodeNum(root->right);
	}
}