⼆叉树的建⽴⽅法总结
之前已经介绍了⼆叉树的四种遍历(如果不熟悉)，下⾯介绍⼀些⼆叉树的建⽴⽅式。⾸先需要明确的是，由于⼆叉树的定义是递归的，所以⽤递归的思想建⽴⼆叉树是很⾃然的想法。
1. 交互式问答⽅式
这种⽅式是最直接的⽅式，就是先询问⽤户根节点是谁，然后每次都询问⽤户某个节点的左孩⼦是谁，右孩⼦是谁。代码如下(其中字符'#'代表空节点)：
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef struct BTNode *Position;
typedef Position BTree;
struct BTNode
{
char data;
Position lChild, rChild;
};
BTree CreateBTree(BTree bt, bool isRoot)
{
char ch;
if (isRoot)
printf("Root: ");
fflush(stdin);        /* 清空缓存区 */
scanf("%c", &ch);
fflush(stdin);
if (ch != '#')
{
isRoot = false;
bt = new BTNode;
先序中序后序遍历二叉树bt->data = ch;
bt->lChild = NULL;
bt->rChild = NULL;
printf("%c's left child is: ", bt->data);
bt->lChild = CreateBTree(bt->lChild, isRoot);
printf("%c's right child is: ", bt->data);
bt->rChild = CreateBTree(bt->rChild, isRoot);
}
return bt;
}
int main()
{
BTree bt;
bt = CreateBTree(bt, true);
LevelOrderTraversal(bt);        /* 层序遍历 */
return0;
}
2. 根据先序序列
例如输⼊序列ABDH##I##E##CF#J##G##（#表⽰空），则会建⽴如下图所⽰的⼆叉树
思路和第⼀种⽅式很相似，只是代码实现细节有⼀点区别，这⾥给出创建函数
BTree CreateBTree()
{
BTree bt = NULL;
char ch;
scanf("%c", &ch);
if (ch != '#')
{
bt = new BTNode;
bt->data = ch;
bt->lChild = CreateBTree();
bt->rChild = CreateBTree();
}
return bt;
}
3. 根据中序序列和后序序列
和⽅式⼆不同的是，这⾥的序列不会给出空节点的表⽰，所以如果只给出先序序列，中序序列，后序序列中的⼀种，不能唯⼀确定⼀棵⼆叉树。但是如果给出中序序列和后序序列或者先序序列和中序序列就可以唯⼀确定⼀棵树。根据三种遍历⽅式的特点，我们可以利⽤先序序列或后序序列确定根节点，可以利⽤中序序列确定左右孩⼦。
由后序序列“左⼦树->右⼦树->根节点”性质可知后序序列的最后⼀个⼀定为这棵树的根节点，⽽⼜根据中序序列“左⼦树->根节点->右⼦树”的性质，由后序序列得到的根节点可以将中序序列分为左⼦树中序序列和右⼦树中序序列。然后根据序列的个数相同，可以将后序序列分为左⼦树后序序列和右⼦树后序序列。依次递归的进⾏，直到序列长度为空递归返回。同理，根据先序序列的“根节点->左⼦树->右⼦树”性质可得先序序列的第⼀个⼀定为这棵树的根节点，之后与上述类似。
例如：⼀棵⼆叉树的中序序列为：ABCEFGHD，后序序列为: ABFHGEDC。建⽴的⼆叉树如下图：
代码如下：
/*
通过中序序列和后序序列建树，然后先序遍历输出
输⼊（第⼀⾏为中序，第⼆⾏为后序）：
ABCEFGHD
ABFHGEDC
输出：
CBADEGFH
*/
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N = 1010;
typedef struct BTNode *Position;
typedef Position BTree;
struct BTNode
{
char data;
Position lChild, rChild;
};
BTree CreateBTree(char inOd[], char postOd[], int n);
void PreOrder(BTree bt);
int main()
{
char inOd[N], postOd[N];  /* 中序序列与后序序列 */
int n = 0;
char ch;
while ((ch = getchar()) && ch != '\n')
inOd[n++] = ch;
n = 0;
while ((ch = getchar()) && ch != '\n')
postOd[n++] = ch;
BTree bt = CreateBTree(inOd, postOd, n);
PreOrder(bt);
printf("\n");
return0;
}
BTree CreateBTree(char inOd[], char postOd[], int n)
{
if (n == 0)
return NULL;
BTree btRoot = new BTNode;
btRoot->data = postOd[n-1];    //后序序列最后⼀个元素⼀定是根节点
char lInOd[N], rInOd[N];
char lPostOd[N], rPostOd[N];
int n1, n2;
n1 = n2 = 0;
//根据根节点将中序序列分为左⼦树和右⼦树
for (int i = 0; i < n; i++)
{
if (i <= n1 && inOd[i] != btRoot->data)
lInOd[n1++] = inOd[i];
else if (inOd[i] != postOd[n-1])
rInOd[n2++] = inOd[i];
}
//根据⼀个树的后序序列的长度等于中序序列且后序遍历是先左⼦树再右⼦树    //将后序序列分为左⼦树和右⼦树
int m1, m2;
m1 = m2 = 0;
for (int i = 0; i < n-1; i++)
{
if (i < n1)
lPostOd[m1++] = postOd[i];
else
rPostOd[m2++] = postOd[i];
}
btRoot->lChild = CreateBTree(lInOd, lPostOd, n1);
btRoot->rChild = CreateBTree(rInOd, rPostOd, n2);
return btRoot;
}
void PreOrder(BTree bt)
{
if (bt != NULL)
{
printf("%c", bt->data);
PreOrder(bt->lChild);
PreOrder(bt->rChild);
}
}
4. 根据不完整的先序，中序，后序序列
如果同时给出先序，中序，后序三种序列，但都是不完整的，能否建⽴⼀课⼆叉树呢？考虑下⾯⼀个例⼦：⼀棵⼆叉树的先序、中序和后序序列分别如下，其中⼀部分未显⽰出来，试编程求出空格处的内容。
先序：_B_F_ICEH_G
中序：D_KFIA_EJC_
后序：_K_FBHJ_G_A
事实上，上述例⼦的核⼼思想还是⽅式三中先到根节点，再分为左右⼦树，然后递归进⾏。区别是这⾥不能唯⼀的根据先序或后序来确定根节点，故需要判断当前是先序序列还是后序序列可以得到根节点，所以函数实现需要传递先序中序后序3种序列。⽽此题还有⼀个隐含的条件，就是当先序和后序都不能得到根节点时，中序序列存在且只存在⼀个'_'，⽽且'_'就是根节点所在位置。这样分析之后代码就⽐较好实现了。代码如下：
/*
⼀棵⼆叉树的先序、中序和后序序列分别如下，其中⼀部分未显⽰出来，
试根据三个不完整的序列建树，然后依次输出先，中，后序的完整序列。
输⼊：
_B_F_ICEH_G
D_KFIA_EJC_
_K_FBHJ_G_A
输出：
ABDFKICEHJG
DBKFIAHEJCG
DKIFBHJEGCA
*/
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N = 1010;
typedef struct BTNode *Position;
typedef Position BTree;
struct BTNode
{
char data;
Position lChild, rChild;
};
BTree CreateBTree(char preOd[], char inOd[], char postOd[], int n);
void PreOrder(BTree bt);
void InOrder(BTree bt);
void PostOrder(BTree bt);
int main()
{
char preOd[N], inOd[N], postOd[N];
int n = 0;
char ch;
while ((ch = getchar()) && ch != '\n')
preOd[n++] = ch;
n = 0;
while ((ch = getchar()) && ch != '\n')
inOd[n++] = ch;
n = 0;
while ((ch = getchar()) && ch != '\n')
postOd[n++] = ch;
BTree bt = CreateBTree(preOd, inOd, postOd, n);
PreOrder(bt);
printf("\n");
InOrder(bt);
printf("\n");
PostOrder(bt);
printf("\n");
return0;
}
BTree CreateBTree(char preOd[], char inOd[], char postOd[], int n)
{
if (n == 0)
return NULL;
BTree btRoot = new BTNode;
if (n == 1)
{
if (preOd[0] != '_')
btRoot->data = preOd[0];
else if (inOd[0] != '_')
btRoot->data = inOd[0];
else if (postOd[0] != '_')
btRoot->data = postOd[0];
else
{
printf("Input error!\n");
exit(0);
}
btRoot->lChild = NULL;
btRoot->rChild = NULL;
return btRoot;
}
if (postOd[n-1] != '_')
btRoot->data = postOd[n-1];    //后序序列最后⼀个元素⼀定是根节点else if (preOd[0] != '_')
btRoot->data = preOd[0];
else
{
printf("Input Error!\n");
exit(0);
}
char lPreOd[N], rPreOd[N];
char lInOd[N], rInOd[N];

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。