[数据结构] 一般二叉树

一 顺序二叉树转链式二叉树

内容描述

一个限长的字符数组,按顺序结构保存着二叉树,我们要将其顺序结构转化成为二叉链表结构的二叉树

实现思想

数组是从零开始的,所以根节点的位置为 0 处;
当前结点位置为currentPos,那么其左节点的位置为[( currentPos + 1 ) * 2 - 1],其右结点的位置为 [( currentPos + 1 ) * 2] , 
每次都为当前的结点创建两个新的结点,将其作为子结点,但是我们规定了'#'字符表示为空的结点,
所以在‘#’存在的时候我们跳过,其实就是从下标上面做手脚;
当然,因为我们是对下标做的手脚,所以说在开始的时候就要对下标是否越界进行判断;

实现代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>

#define MAXPos 15

typedef struct BiTreeNode
{
   struct BiTreeNode *lchild;
   struct BiTreeNode *rchild;
   char value;
} BiTreeN, *BiTN;

char nodeArray[12];

void InputTreeList(char *TreeNode);
void preorder(BiTreeN *node);
void BiTree_Recursion(BiTreeN *parentNode, int postionChar);
void inorder(BiTreeN *node);
void postorder(BiTreeN *node);

int main()
{
   InputTreeList(nodeArray);
   BiTreeN *node = (BiTreeN *)malloc(sizeof(BiTreeN));
   node->lchild = NULL;
   node->rchild = NULL;
   node->value = nodeArray[0];
   BiTree_Recursion(node,0);
   postorder(node);
   return 0;
}

void InputTreeList(char *TreeNode)
{
   for (int i = 0; i < MAXPos; ++i)
  {
       TreeNode[i] = getchar();
  }
}

//递归构建二叉树
void BiTree_Recursion(BiTreeN *parentNode, int postionChar)
{
//开始限定条件
   if (parentNode == NULL || (postionChar + 1) * 2 >= MAXPos)
  {
       return;
  }
   else
  {
       if (nodeArray[(postionChar + 1) * 2 - 1] != '#')
      {
           BiTreeN *lnode = (BiTreeN *)malloc(sizeof(BiTreeN));
           lnode->lchild = NULL;
           lnode->rchild = NULL;
           lnode->value = nodeArray[(postionChar + 1) * 2 - 1];
           parentNode->lchild = lnode;
           BiTree_Recursion(lnode, (postionChar + 1) * 2 - 1);
      }
       if (nodeArray[(postionChar + 1) * 2] != '#')
      {
           BiTreeN *rnode = (BiTreeN *)malloc(sizeof(BiTreeN));
           rnode->lchild = NULL;
           rnode->rchild = NULL;
           rnode->value = nodeArray[(postionChar + 1) * 2];
           parentNode->rchild = rnode;
           BiTree_Recursion(rnode, (postionChar + 1) * 2);
      }
  }
}

void preorder(BiTreeN *node){
   if(node){
       printf("~   %c ", node->value);
       preorder(node->lchild);
       preorder(node->rchild);
  }
}

void inorder(BiTreeN *node)
{
   if (node)
  {
       inorder(node->lchild);
       printf("*   %c ", node->value);
       inorder(node->rchild);
  }
}

void postorder(BiTreeN *node)
{
   if (node)
  {
       postorder(node->lchild);
       postorder(node->rchild);
       printf("&   %c ", node->value);
  }
}

必须输入15个,不然会出错,明天修改为任意输入构建二叉树;


内容描述

一个限长的字符数组,按顺序结构保存着二叉树,我们要将其顺序结构转化成为二叉链表结构的二叉树

思想介绍

先创建一个字符数组,存储二叉树的顺序结构;
然后通过这个字符数组创建二叉链表表示的二叉树; 

代码实现

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100 /* 存储空间初始分配量 */
char Nil = ' '; /* 字符型以空格符为空 */
/*用于构造二叉树*/
int index = 1;
typedef char String[24]; /* 0 号单元存放串的长度 */
String str;
int StrAssign(String T, char chars[])
{
int i;
if (strlen(chars) > MAXSIZE)
{
return -1;
}
else
{
T[0] = strlen(chars);
for (i = 1; i <= T[0]; i++)
{
T[i] = *(chars + i - 1);
}
return 1;
}
}

typedef struct BiTNode /* 结点结构 */
{
char data; /* 结点数据 */
struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;

int InitBiTree(BiTree *T) /* 构造空二叉树 T */
{
*T = NULL;
return 1;
}

/* 初始条件: 二叉树 T 存在。操作结果: 销毁二叉树 T */
void DestroyBiTree(BiTree *T)
{
if (*T)
{
if ((*T)->lchild) /* 有左孩子 */
DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
if ((*T)->rchild) /* 有右孩子 */
DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
free(*T); /* 释放根结点 */
*T = NULL; /* 空指针赋 0 */
}
}

/* 按前序输入二叉树中结点的值(一个字符) */
/* #表示空树,构造二叉链表表示二叉树 T。 */

void CreateBiTree(BiTree *T)
{
char ch;
/* scanf("%c",&ch); */
ch = str[index++];
if (ch == '#')
*T = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
if (!*T)
exit(0);
(*T)->data = ch; /* 生成根结点 */
CreateBiTree(&(*T)->lchild); /* 构造左子树 */
CreateBiTree(&(*T)->rchild); /* 构造右子树*/
}
}

/* 初始条件: 二叉树 T 存在 */ /* 操作结果: 若 T 为空二叉树,则返回 TRUE,否则 FALSE */

int BiTreeEmpty(BiTree T)
{
if (T)
return 0;
else
return 1;
}

/* 初始条件: 二叉树T 存在。操作结果: 返回T 的深度 */
int BiTreeDepth(BiTree T)
{
int i, j;
if (!T)
{
return 0;
}
if (T->lchild)
{
i = BiTreeDepth(T->lchild);
}
else
{
i = 0;
}
if (T->rchild)
{
j = BiTreeDepth(T->rchild);
}
else
{
j = 0;
}
return i > j ? i + 1 : j + 1;
}

/* 初始条件: 二叉树 T 存在。操作结果: 返回 T 的根 */
char Root(BiTree T)
{
if (BiTreeEmpty(T))
{
return Nil;
}
else
{
return T->data;
}
}

/* 初始条件: 二叉树 T 存在 */ /* 操作结果: 前序递归遍历 T */
void PreOrderTraverse(BiTree T)
{
if (T == NULL)
return;
printf("%c->", T->data); /* 显示结点数据,可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树*/
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}

/* 初始条件: 二叉树 T 存在 */

/* 操作结果: 中序递归遍历 T */
void InOrderTraverse(BiTree T)
{
if (T == NULL)
return;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c->", T->data); /* 显示结点数据,可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树*/
}

/* 初始条件: 二叉树 T 存在 */

/* 操作结果: 后序递归遍历 T */
void PostOrderTraverse(BiTree T)
{
if (T == NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树*/
PostOrderTraverse(T->rchild); /* 再后序遍历右子树*/
printf("%c->", T->data); /* 显示结点数据,可以更改为其它对结点操作 */
}
void Test()
{
int i;
BiTree T;
char e1;
InitBiTree(&T);
StrAssign(str, "ABDH#K###E##CFI###G#J##");
CreateBiTree(&T);
printf("构造空二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
e1 = Root(T);
printf("二叉树的根为: %c\n", e1);
printf("\n 前序遍历二叉树:");
PreOrderTraverse(T);
printf("\n 中序遍历二叉树:");
InOrderTraverse(T);
printf("\n 后序遍历二叉树:");
PostOrderTraverse(T);
DestroyBiTree(&T);
printf("\n 清除二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
i = Root(T);
if (!i)
printf("树空,无根\n");
}

int main()
{
Test();
return 0;
}