数据结构括号表示法创建二叉树_给出一棵二叉树的括号表示法,本题要求实现2个函数,根据给出的括号表示法创建该二

2022.11.18有一阵没写了，主要原因：中期和生日。

---

任务描述

本关任务：给出一棵二叉树的括号表示法，本题要求实现3个函数，根据给出的括号表示法创建该二叉树并输出。输出时，也按二叉树的括号表示法输出。然后再求出二叉树高度并输出。

相关知识

编程要求

测试说明

平台会对你编写的代码进行测试：

开始你的任务吧，祝你成功！

C/C++代码

#include "binary_tree.h"

//根据嵌套括号表示法的字符串生成链式存储的二叉树
void CreateTree(BTNode* &root, char str[]) {
	/*请在BEGIN和END之间实现你的代码*/
	/*****BEGIN*****/
	BTNode* St[60], * p; root = NULL;
	int top = -1, k, i = 0;	//栈顶指针
	char ch = str[i];
	while (ch != '\0'){
		switch (ch){
		case '(':top++; St[top] = p; k = 1; break;		
		case ')':top--;  break;							
		case ',': k = 2; break;							
		default:
			p = (BTNode*)malloc(sizeof(BTNode));		
			p->data = ch;								
			p->lchild = p->rchild = NULL;				
			if (root == NULL)				
				root = p;			
			else{
                k == 1 ? St[top]->lchild = p : St[top]->rchild = p;
			}
		}
		ch = str[++i];
	}
	/******END******/
}

//以嵌套括号表示法输出一棵二叉树
void DispTree(BTNode* root) {
	/*请在BEGIN和END之间实现你的代码*/
	/*****BEGIN*****/

	if (root != NULL){
		printf("%c", root->data);
		if (root->lchild != NULL || root->rchild != NULL){
			printf("(");
			DispTree(root->lchild);
			if (root->rchild != NULL)
				printf(",");
			DispTree(root->rchild);
			printf(")");
		}
	}
	/******END******/
}

// 求二叉树的高度
// 参数：二叉树根节点root
int getHeight(BTNode* root)
{
	/*请在BEGIN和END之间实现你的代码*/
	/*****BEGIN*****/
    int lchildh, rchildh;
	if (root == NULL) return 0;
	else{
		lchildh = getHeight(root->lchild);
		rchildh = getHeight(root->rchild);
		return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
	}
	/******END******/
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64