按广义表表示二叉树结构生成二叉树链表的算法

用广义表表示二叉树结构如下：

(A (B (,D (E,E),C))

  

 

  
1
 

算法如下：

#include <stdio.h>
#include <stdlib.h>


// 定义节点
typedef struct Node{
	char data; struct Node* lChild;
	struct Node* rChild;
} BinTNode;	

// 根据广义表表示二叉树结构来创建二叉树链表
BinTNode* createTree(char *str){
	// 用指针数组st存放双亲节点
	BinTNode *st[100];
	// 用来一生成节点时用的
	BinTNode *p = NULL;
	// 二叉树链表的头节点
	BinTNode *b = NULL;
	// top用来记录st的栈顶，key用来记录下一个节点是当前节点的左子树（用１表示）还是右子树（用２表示），j是用来遍历str字符串用的
	int top = -1,key,j=0;
	// 取得第一个字符
	char ch = str[j];
	// 当字符串没有结束，就继续循环，'\0'是字符串的结束标记
	while(ch != '\0'){ // 在遍历广义表表示二叉树结构过程中，会遇到'(',',',')'和字母
		switch(ch){ // 遇到'('，就是左子树，将key标记为１，以作记录，将当前节点记录到栈st中 case '(': top++; st[top] = p; key = 1; break; // 遇到',',就是右子树，将key标记为１，以作记录 case ',': key = 2; break; // 遇到')'，说明此子树已遍历完成，要返回到上一个双亲节点，准备遍历双亲节点的另一棵子树 case ')': top--; break; // 遇到节点，为节点申请内存，并初始化节点 default: p = (BinTNode*)malloc(sizeof(BinTNode)); p->data = ch; p->lChild = p->rChild = NULL; // 记录头结点 if(b == NULL){ b = p; }else{ // 如果是非头结点，那么就根据key的值，将节点添加到双亲节点的子树上去 switch(key){ case 1: st[top]->lChild = p; break; case 2: st[top]->rChild = p; break; } } }
		// 遍历下一个字符
		j++;
		ch = str[j];
	}
	// 返回头结点
	return b;
}

  

 

  
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
  
65
  
66
  
67
  
68
 

测试：

int main(){
	char *str = "(A(B(,D(E,F)),C))";

	BinTNode* tree = createTree(str);

	printf("%c",tree->data); return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

我们来看看上述程序执行过程中，st与top的变化：

本算法正是借助它们来创建二叉树链表的。

谢谢阅读。

文章来源: blog.csdn.net，作者：WongKyunban，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_40763897/article/details/104968496