⼆叉树相关根据前序、中序确定⼆叉树
树相关概念（参考⼤话数据结构）：
树是⼀对多的数据结构。
根节点：⼀个树中只有⼀个根节点（root）。
⼦树：节点的⼦树数量是指与它相邻的（⽽不是节点下⾯所有的）下⼀层有⼏个节点。
度：节点拥有的⼦树数量称为节点的度（Degree）。树的度是指树内所有节点度的最⼤值。先序中序后序遍历二叉树
度为0的节点称为叶节点或终端节点。度不为0的节点称为⾮终端节点或分⽀节点。
深度：是指树的⾼度，有⼏层。
将树中节点的各⼦树看成从左到右是有次序的，不能互换的，称该树为有序树，否则为⽆序树。
森林是m(m>=0)棵互不相交的树的集合。对于树中每个节点⽽⾔，其⼦树的集合即为森林。
⼆叉树相关：
特点：
1.每个节点最多有两个⼦树，所以⼆叉树中不存在度⼤于2的节点。
2.⼆叉树是有序树，左⼦树和右⼦树顺序不能颠倒。
3.⼆叉树中某节点只有⼀棵⼦树时，也要区分是左⼦树还是右⼦树。
特殊⼆叉树：
斜树：所有节点都只有左（右）⼦树的称为左（右）斜树。斜树跟线性表结构⼀样。
满⼆叉树：所有分⽀节点都存在左右⼦树，并且所有叶节点都在同⼀层。
完全⼆叉树：将满⼆叉树的最后⼀层最后⼀个节点从右到左连续删除任意个节点（必须包含最后⼀个节点，必须从右到左，必须连续）得到的树就是完全⼆叉树（这个定义是⾃⼰写的，这样写了觉得好理解多了）。
⼆叉树性质：
1.终端节点（叶节点）数量为a，度为2的节点数量为b，则a=b+1(可使⽤满⼆叉树推导，满⼆叉树的最后⼀层叶节点的数量-1=不包含最后⼀层的树的所有节点和)
⼆叉树存储结构：
1.可以使⽤⼆叉链表（包含左⼦指针和右⼦指针）或三叉链表（多个⽗指针）的⽅式表⽰
⼆叉树遍历：
定义：从根节点出发，按照某种次序依次访问⼆叉树中所有节点，使得每个节点被访问⼀次且仅被访问⼀次。
前序遍历（preorder Travelsal VLR）：先访问根节点，然后前序遍历左⼦树，再前序遍历右⼦树。
中序遍历（inorder Travelsal LDR）：从根节点开始（不是先访问根节点），中序遍历根节点的左⼦树，然后访问根节点，最后中序遍历右⼦树。
后序遍历（postorder Travelsal LDR）：从左到右先叶节点后节点的⽅式遍历访问左右⼦树，最后访问根节点。
层序遍历：从树的第⼀层根节点开始，从上⽽下逐层遍历，同⼀层中，按从左到右的顺序遍历。
这⾥的前、中、后指的是访问根节点的顺序，前指最先访问根节点，中是指中间访问根节点、后是指最后访问根节点，可以对⽐前中后三种遍历代码对应理解。
下图分别为前序、中序、后序、层序。
推导遍历结果：
1.已知前序遍历和中序遍历，可以确定唯⼀⼆叉树。
2.已知后序遍历和中序遍历，可以确定唯⼀⼆叉树。
3.已知前序和后序，不能确定⼆叉树。
前序和中序推导树，推导流程如下：
1.⾸先确定根节点（前序的第⼀个字母，后序的最后⼀个字母），根据根节点可将中序分割成左⼦树和右⼦树。
2.将左⼦树和右⼦树看成新的树，重复第⼀步，递归求解树。
⽐如前序是ABCDEF，中序是CBAEDF,A是根节点，CB是A的左⼦树,EDF是A的右⼦树。
对左⼦树CB进⾏重新分析。前序是BC，中序是CB，说明B是左⼦树的根节点，C是B的⼦节点。中序是CB,C为B的左⼦节点。对右⼦树EDF进⾏重新分析。前序是DEF，中序是EDF，说明D是右⼦树的根节点，EF是D的⼦节点。继续分析即可。
后序和中序推导树，推导流程如下：
1.后序的最后⼀个节点是根节点，根据根节点在中序中的位置可以将树划分为左右⼦树。
2.得到左右⼦树的后序和中序，可以到左右⼦树的根节点，继续递归分析即可。
⽐如中序是CBAEDF，后序是CBEFDA
根节点为后序的最后⼀个节点A，左⼦树的中序是CB，左⼦树的后序是CB，右⼦树的中序是EDF，右⼦树的后序是EFD。  左⼦树的根节点是B，继续分析即可。
前序、中序、后序遍历及基于前序、中序创建树，基于后序、中序创建树的C代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<signal.h>  //signal()
#include<string.h>
#include<sys/stat.h>
#include<time.h>
#include<stdarg.h>
#if 1
#define INFO_DEBUG    "%d lines in "__FILE__", complie time is "__TIME__" "__DATE__" \n",__LINE__
#define ADI_RUN_ERROR      1
#define ADI_NULL_POINTER  -1
#define ADI_OK            0
#define ADI_PRINT        printf("[%s][%d]:",__FUNCTION__,__LINE__);printf
#define ADI_ASSERT(c,prt,ret)      if(c) {printf(prt);return ret;}
#endif
#define SUCCESS 0
#define NULL_POINTER 1
#define eleType char
int strLength(char *str)
{
int length = 0;
while('\0' != str[length])
{
length++;
}
return length;
}
/*
⼆叉树相关
*/
typedef struct BitNode{
eleType ele;
struct BitNode *left,*right;
}BitNode;
/*只创建⼀个根节点，要指定根节点的值，并将左右指针都设为NULL*/
BitNode *initBitTree(eleType elem)
{
BitNode *root = malloc(sizeof(BitNode));
if(NULL==root) {printf("NULL");return root;}
root->ele = elem;
root->right = NULL;
root->left = NULL;
return root;
}
/*
指定插⼊的位置：有两种⽅式，1是指定插⼊的节点对应的值及左右位置，或者指定插⼊节点的节点号及左右位置这⾥实现指定插⼊的值及左右位置。
参数意义：
bitTree：要插⼊的⼆叉树
parent：⽗节点值
child：⼦节点值
pos；插⼊⽗节点的左还是右， =0，左;=1，右
*/
int insertBitTree(BitNode *bitTree,eleType parent,eleType child,int pos)
{
}
/*⼆叉树前序遍历算法，使⽤递归实现*/
void preorderBitTree(BitNode *bitTree)
{
if(NULL == bitTree)
{
return;
}
printf("%c",bitTree->ele);
preorderBitTree(bitTree->left);
preorderBitTree(bitTree->right);
}
/*⼆叉树中序遍历算法，使⽤递归实现*/
void inorderBitTree(BitNode *bitTree)
{
if(NULL == bitTree)
{
return;
}
inorderBitTree(bitTree->left);
printf("%c",bitTree->ele);
inorderBitTree(bitTree->right);
}
/*⼆叉树后序遍历算法，使⽤递归实现*/
void postorderBitTree(BitNode *bitTree)
{
if(NULL == bitTree)
{
//ADI_PRINT("NULL pointer\n");
return;
}
postorderBitTree(bitTree->left);
postorderBitTree(bitTree->right);
printf("%c",bitTree->ele);
}
/*根据前序和中序创建树
root：待创建树的根节点
pre：前序
mid：中序
size：树的size
这⾥涉及⼆级指针的使⽤及C语⾔运算符优先级相关
*/
int treeFromPreMid(BitNode **root,char *pre,char *mid,int size)
{
/*0 == size_length意味着上⼀次的i=0，即pre[0]=mid[0]（树中只有⼀个节点），递归结束*/
if(0 == size)
{
return SUCCESS;
}
ADI_PRINT("size=%d\n",size);
(*root) = (BitNode *)malloc(sizeof(BitNode));
(*root)->ele = pre[0];
/*到根节点元素在中序中的位置i*/
int i=0;
while(mid[i] != pre[0])
{i++;}
treeFromPreMid(&(*root)->left,&pre[1],mid,i);//左⼦树递归求解，C语⾔运算符优先级：()等于->⼤于&，所以先*root，接着->，再&    treeFromPreMid(&(*root)->right,&pre[i+1],&mid[i+1],size-i-1);//右⼦树递归求解
}
/*根据中序，后序求树*/
int treeFromPostMid(BitNode **root, char *post, char *mid,int size)
{
if(0 == size)
{
return SUCCESS;
}
ADI_PRINT("size=%d\n",size);
*root = (BitNode *)malloc(sizeof(BitNode));
(*root)->ele = post[size-1];
int i=0;
while(post[size-1] != mid[i])
{i++;}
treeFromPostMid(&(*root)->left,post,mid,i);
treeFromPostMid(&(*root)->right,&post[i],&mid[i+1],size-i-1); }
int main()
{
char *pre  = "ABCDEF";
char *mid  = "CBAEDF";
char *post = "CBEFDA";
BitNode *ROOT = NULL;
treeFromPreMid(&ROOT,pre,mid,strLength(pre));
postorderBitTree(ROOT);
printf("\n");
treeFromPostMid(&ROOT,post,mid,strLength(pre));
preorderBitTree(ROOT);
return SUCCESS;
}

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