如何创建、重建、改写一个二叉树？

本文共计729个文字，预计阅读时间需要3分钟。

对于二叉树的创建，我们通常只熟悉最简单的创建方式，即逐个输入节点，然后按照先序、中序或后序遍历的方式递归建立二叉树。然而，仅仅掌握这些是不够的。

对于二叉树的创建，一般我们只熟悉最简单的二叉树创建方式，即逐个输入节点，然后按照先序遍历或者中序、后序遍历方式来递归建立二叉树。但是，光掌握这个是不够的，我们还得掌握二叉树的重建（先序中序重建二叉树，后序中序重建二叉树），数组转换为二叉树，链表转换为二叉树等等。

1、最简单的创建方式

我们可以根据先序遍历递归创建二叉树，当然也可以中序或者后序遍历方式创建二叉树。

struct node *creat() //前序建立 { struct node *root; char c; c = a[l1++];//li在int main函数里表现出来 if(c == ',') return NULL; else { root = (struct node *)malloc(sizeof(struct node)); root->data = c; root->l=creat(); root->r=creat(); } return root;

2、根据前序序列和中序序列建二叉树

根据二叉树的前序后中序遍历的结果来重建二叉树。
前序：A B D E H I C F G
中序：D B H E I A F C G

怎么做了？注意，前序遍历第一个节点A肯定是根节点；那么，我们可以在中序遍历中找到这个根节点A，那么中序遍历中根节点A左边的点（D B H E I）就是A的左子树的节点，右边的点（F C G）就是A节点右子树的节点。再看前序遍历的节点B，对于节点B也是一样，中序遍历中根节点B左边的点（D）就是B的左子树的节点，右边的点（H E I）就是B节点右子树的节点………

根据上述这种思想递归下去，可以逐步找到每个点的位置，然后就可以将树建立起来，具体看代码

struct node *creat(char a[], char b[], int n)//前序和中序建立二叉树 { int i; if(n == 0) { return NULL; } struct node *root; root = (struct node *)malloc(sizeof(struct node)); root->data = a[0]; for(i = 0; i < n; i++) { if(b[i] == a[0]) { break; } } root->lc = creat(a+1,b,i); root->rc = creat(a+i+1,b+1+i,n-1-i); return root; };

3、根据后序序列和中序序列建二叉树

struct node *creat(char a[], char b[], int n)//中序和后序建立二叉树 { int i; struct node *root; if(n == 0) { return NULL; } root = (struct node *)malloc(sizeof(struct node)); root->data = b[n-1]; for(i = 0; i < n; i++) { if(a[i] == b[n-1]) { break; } } root->lc = creat(a,b,i); root->rc = creat(a+i+1,b+i,n-1-i); return root; };