根据顺序和遍历顺序构建二叉树

【前言】

该主题源自课堂练习. 本主题提供了二叉树的预遍历遍历和中阶遍历，并且需要整个二叉树. 当我第一次提出这个问题时，我有点困惑. 但是，由于答案是肯定的中序遍历创建二叉树，因此必须有找到该二叉树的算法. 经过一番探索，终于确定了求解算法.

【分析】

二叉树遍历有四种方法，即前顺序遍历，中阶遍历，后继遍历和序列遍历. 每种方法都有其自身的特征，但最好使用中阶遍历的特征.

顺序遍历是先遍历左子树，然后依次遍历根节点和右子树. 在形成的序列中，节点的左子树节点全部分布在其左侧，而右子树节点全部分布在其右侧. 这样，通过比较子节点和根节点的相对位置，可以确定该节点是左子节点还是右子节点.

从上到下以及从左到右执行预定遍历. 遍历根节点和子节点之间的节点后，将不会遍历它们. 这意味着我们不必考虑插入节点.

我的想法是按顺序扫描预遍历的顺序，第一个是直接创建的根节点. 后续元素应使用中阶遍历的结果与生成的节点进行比较，以确定该节点位于左侧还是右侧子树中. 重复此过程，直到找到最终位置，然后在该位置继续成为叶子. 当然，此过程是递归过程. 预遍历扫描结束后，生成二叉树并解决了问题.

[算法实现]

该程序使用两个字符数组存储预遍历和中间遍历的结果. 字符数组作为参数在模块之间传递，以供每个模块使用，并且还减少了模块之间的耦合. 设计一个函数来生成一个二叉树. 还有一个创建新节点的功能. 此函数需要递归本身. 它还需要设计一个函数来扫描字符串，以确定它应该在左还是右子树中.

值得注意的是，创建新节点的功能需要为该节点分配内存，因此有必要使用地址传输，它实际上是一个传递给指针的指针. 另外，还应考虑二叉树的输出. 在此，使用文本模式输出. 这只是一个示例，因此节点数据被设计为字符类型以便于理解，并且程序不会检查输入的有效性和可行性.

[源代码]

#include

#include

#include

#include

#define MAXCOUNT 32

#define LEFT 0

#define RIGHT 1

typedef char Elemtype;

typedef struct BtreeNode

{

元素类型数据；

struct BtreeNode * LChild中序遍历创建二叉树，* RChild;

} BTREENODE，* BTREENODEPTR，* BTREE；

typedef struct Pos

{

int x，y;

} BTREENODEPOS;

BTREENODEPOS BtnPos [MAXCOUNT];

void InitBtreeNodePos（无效）

{

int i;

for（i = 0; i <16; i ++）

{

BtnPos [16 + i] .x = 25 + i * 2;

BtnPos [16 + i] .y = 16;

}

对于（i = 15; i> = 1; i-）

{

BtnPos [i] .x =（BtnPos [2 * i] .x + BtnPos [2 * i + 1] .x）/ 2;

BtnPos [i] .y = BtnPos [2 * i] .y-2;

}

}

void DestroyBtree（BTREE根）

{

如果（Root == NULL）返回;

DestroyBtree（Root-> LChild）;

DestroyBtree（Root-> RChild）;

Root-> LChild = NULL;

Root-> RChild = NULL;

免费（root）；

}

void ShowBtree（BTREE根，整数索引）

{

int i，j;

如果（Root == NULL）返回;

i =索引* 2;

j =索引* 2 +1;

gotoxy（BtnPos [索引] .x，BtnPos [索引] .y）；

printf（“％c”，Root->数据）；

如果（i LChild，i）;

如果（j RChild，j）;

}

int GetLR（char *预购，char * InOrder，int i，int数据）

{

int j = 0，k = 0;

while（PreOrder [i]！= InOrder [j]）j ++;

while（Data！= InOrder [k]）k ++;

如果（j

}

void AddBtreeNode（BTREE *根，字符*预订单，字符*订单，整数i）

{

如果（*根== NULL）

{

（*根）=（BTREENODE *）malloc（sizeof（BTREENODE））;

（*根）->数据=预购[i];

（*根）-> LChild = NULL;

（*根）-> RChild = NULL;

}

其他

{

if（GetLR（PreOrder，InOrder，i，（* Root）-> Data）== LEFT）

AddBtreeNode（＆（*根）-> LChild，PreOrder，InOrder，i）;

其他

AddBtreeNode（＆（*根）-> RChild，PreOrder，InOrder，i）;

}

}

BTREE CreatBtreeByOrder（无效）

{

char PreOrder [32]，InOrder [32];

BTREE根= NULL;

int i;

printf（“ Input PreOrder: ”）;

获取（PreOrder）;

printf（“输入顺序: ”）;

获取（InOrder）;

for（i = 0;预购[i]！= 0; i ++）

AddBtreeNode（＆根，PreOrder，InOrder，i）；

返回根；

}

void main（）

{

BTREE根；

clrscr（）;

InitBtreeNodePos（）;

Root = CreatBtreeByOrder（）;

ShowBtree（Root，1）;

DestroyBtree（Root）;

}

这里是完整版，您可以在复制后直接运行它. 下面给出了一些测试用例来检测该算法.

第一组: 预购: ABDHJEICFG，订购: DJHBEIAFCG

第二组: 预购: ABDHEICFG，订购: DHBIEAFGC

第三组: 预购: ABCDEFG，订购: BCAFEGD

【摘要】

通过充分利用预遍历和中遍历的特征，可以生成二叉树. 如果将预购订单替换为层序列，则无需更改算法. 如果将其替换为后订单，则仅需反转后续遍历. 使用此反向序列执行此算法将不会用于任何更改. 可以看出，这里的中阶遍历非常重要. 但是，如果您不提供中间顺序遍历，例如仅提供顺序遍历和后续遍历，则无法确定二叉树. 目前，该算法不容易修改，因此在此不再讨论.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-175971-1.html