題目:輸入一個整數和一棵二元樹。
從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
打印出和與輸入整數相等的所有路徑。
例如輸入整數 22 和如下二元樹
10
/ \
5 12
/ \
4 7
則打印出兩條路徑:10, 12 和 10, 5, 7。
代碼思路
1)遞歸前序創建二叉樹
2)借鑒二叉樹的前序遍歷,然後加遞歸,回溯算法。
代碼c語言實現
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
int k = 0;
typedef struct BSTreeNode
{
int date;
struct BSTreeNode *leftnode;
struct BSTreeNode *rightnode;
}BSTree;
BSTree *creatree()
{
int num;
BSTree *node;
scanf("%d", &num);
if (num==0)
{
node = NULL;
}
else
{
node = (BSTree *)malloc(sizeof(BSTree));
node->date = num;
node->leftnode=creatree();
node->rightnode=creatree();
}
return node;
}
void printree(BSTree *node)
{
printf("%d ", node->date);
}
void inorder(BSTree *node, void(*visit)(BSTree *))
{
if (node)
{
inorder(node->leftnode, visit);
visit(node);
inorder(node->rightnode, visit);
}
}
void path(BSTree *node, int n, int num,int *p)
{
if (node)
{
n = n - node->date;
p[num++] = node->date;
if (node->leftnode == NULL&&node->rightnode == NULL&&n == 0)
{
printf("第%d組路徑: ", ++k);
for (int i=num - 1; i >= 0; i--)
{
printf("%d ", p[i]);
}
printf("\n");
}
else
{
if (node->leftnode != NULL)
{
path(node->leftnode, n, num, p);
}
if (node->rightnode != NULL)
{
path(node->rightnode, n,num, p);
}
}
num--;
n = n + node->date;
}
}
void initree(BSTree *root)
{
root=NULL;
}
void main()
{
int n = 22;
int num = 0;
int a[10] = { 0 };
BSTree *root;
root=creatree();
printf("中序遍歷為:\n");
inorder(root, printree);
printf("\n");
path(root, n, num, a);
system("pause");
}