括号表示法字符串构造二叉树

原理如上图，下面的是简述：
当遇到字母的时候，直接入栈，而遇到“）”的时候出栈，其他的字符时做左右子树的标记，代码实现过程如下：

#include<iostream>
using namespace std;
#define MaxSize 100

struct BTnode {  //节点的数据类型
	char data;
	BTnode *lnode, *rnode;
};
void Create(BTnode* &root, char *str) {  //创建二叉树
	BTnode *St[MaxSize], *p = root = NULL;
	int k = 0, j = 0, top = -1;
	char ch = str[j];
	while (ch != '') {
		switch (ch)
		{
		case '(': St[++top] = p; k = 1; break;
		case ')': top--; break;
		case ',': k = 2; break;
		default:
			p = new BTnode;
			p->data = ch;
			p->lnode = p->rnode = NULL;
			if (root == NULL) root = p;
			else k == 1 ? St[top]->lnode = p : St[top]->rnode = p;
		}
		ch = str[++j];
	}
}
BTnode* Findnode(BTnode *root, char ch) {  //查找某个节点
	if (root == NULL) return NULL;
	if (root->data == ch) return root;
	BTnode *p = Findnode(root->lnode, ch);
	return p != NULL ? p : Findnode(root->rnode, ch);
}

void Display(BTnode *root) { //输出整棵二叉树
	if (root != NULL) printf("%c", root->data);
	if (root->lnode != NULL || root->rnode != NULL) {
		printf("(");
		if (root->lnode != NULL) Display(root->lnode);
		if (root->rnode != NULL) {
			printf(",");
			Display(root->rnode);
		}
		printf(")");
	}
}
int main() {

	BTnode *root = NULL;
	char* str = "A(B(D(,G)),C(E,F))";
	Create(root, str);
	Display(root);
	printf("n");

	return 0;
}

最后

以上就是真实大地为你收集整理的括号表示法字符串构造二叉树的全部内容，希望文章能够帮你解决括号表示法字符串构造二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。