日常练手用,熟悉一下几种结构的代码实现。
1.通过给定中序遍历和后序遍历的数列重建二叉树
#include <stdio.h>
#include <stdlib.h>
typedef struct Node *Tree;
struct Node
{
int data;
Tree left, right;
};
/*定义树*/
Tree buildTree (int inorder[], int postorder[], int n);
/*建树函数*/
void preorderTraversal (Tree theTree);
/*先序遍历函数(用于验证)*/
int main ()
{
int n, i;
scanf ("%d", &n);
/*输入含 n 个数的数列*/
int inorder[n], postorder[n];
for (i = 0; i < n; i++)
scanf ("%d", &inorder[i]);
for (i = 0; i < n; i++)
scanf ("%d", &postorder[i]);
/*输入中序和后序数列*/
Tree theTree = buildTree (inorder, postorder, n);
/*建树*/
preorderTraversal (theTree);
/*遍历重建的树*/
return 0;
}
Tree buildTree (int inorder[], int postorder[], int n)
{
Tree T = (Tree)malloc(sizeof (struct Node));
T->data = postorder[n - 1];
/*后序遍历的最后一个数即根结点数据*/
if (n == 1)
{
T->left = NULL;
T->right = NULL;
return T;
}
/*若只剩一个数,则直接返回(别忘了令左右子树为 NULL )*/
int i;
for (i = 0; i < n; i++)
{
if (inorder[i] == postorder[n - 1])
break;
}
if (i == 0)
{
T->left = NULL;
T->right = buildTree (&inorder[1], postorder, n - 1);
}
/*中序遍历的第一个数是树的最左端,故该 T 无左子树,从中序遍历第二项开始继续建树*/
else if (i == n-1)
{
T->right = NULL;
T->left = buildTree (inorder, postorder, n - 1);
}
/*中序遍历的最后一个是树的最右端,故该 T 无右子树,再次遍历至倒数第二项为止*/
else//此时 T 既有左子树又有右子树
{
T->left = buildTree (inorder, postorder, i);
/*用前 i 个数建左子树*/
T->right = buildTree (&inorder[i + 1], &postorder[i], n - 1 - i);
/*用后 n-i 个数建右子树( n-1-i 即 n-(1+i) )*/
}
return T;
}
void preorderTraversal (Tree theTree)
{
Tree T = theTree;
if (T != NULL)
{
printf ("%d ", T->data);
preorderTraversal (T->left);
preorderTraversal (T->right);
}
}
2.通过给定中序遍历和先序遍历的数列重建二叉树
#include <stdio.h>
#include <stdlib.h>
typedef struct Node *Tree;
struct Node
{
int data;
Tree left, right;
};
/*定义树*/
Tree buildTree (int inorder[], int preorder[], int n);
/*建树函数*/
void postorderTraversal (Tree theTree);
/*后序遍历函数(用于验证)*/
int main ()
{
int n, i;
scanf ("%d", &n);
/*输入含 n 个数的数列*/
int inorder[n], preorder[n];
for (i = 0; i < n; i++)
scanf ("%d", &inorder[i]);
for (i = 0; i < n; i++)
scanf ("%d", &preorder[i]);
/*输入中序和后序数列*/
Tree theTree = buildTree (inorder, preorder, n);
/*建树*/
postorderTraversal (theTree);
/*遍历重建的树*/
return 0;
}
Tree buildTree (int inorder[], int preorder[], int n)
{
Tree T = (Tree)malloc(sizeof (struct Node));
T->data = preorder[0];
/*先序遍历的第一个数即根结点数据*/
if (n == 1)
{
T->left = NULL;
T->right = NULL;
return T;
}
/*只剩一个数时直接返回*/
int i;
for (i = 0; i < n; i++)
{
if (inorder[i] == preorder[0])
break;
}
if (i == 0)
{
T->left == NULL;
T->right = buildTree (&inorder[1], &preorder[1], n - 1);
}
else if (i == n-1)
{
T->right = NULL;
T->left = buildTree (inorder, &preorder[1], n - 1);
}
else
{
T->left = buildTree (inorder, &preorder[1], i);
T->right = buildTree (&inorder[i + 1], &preorder[i + 1], n - i - 1);
}
/*原理类比上个代码*/
return T;
}
void postorderTraversal (Tree theTree)
{
Tree T = theTree;
if (T != NULL)
{
postorderTraversal (T->left);
postorderTraversal (T->right);
printf ("%d ", T->data);
}
}
标签:练习,int,编程,Tree,buildTree,FDS,遍历,right,inorder
From: https://blog.csdn.net/MrSkillless/article/details/137059889