C++实现查找二叉树中和为某一值的所有路径的示例

Z时代
2024-01-10
分类：综合

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

例如输入整数22和如下二元树

则打印出两条路径：10, 12和10, 5, 7。

先序遍历树即可得到结果。

算法: FindPath(BTree * root,int sum,int target,Stack * s) 用来计算，sum为栈中的元素的和，target为目标值。

到达一个节点之后计算当前节点和sum的和，如果为target，输出路径返回，如果大于target，则直接返回，如果小于，则将当前节点的值入栈，更新sum的值，继续遍历，遍历完成之后，也就是从当前节点返回的时候，将其从栈中弹出，更新sum

代码如下（GCC编译通过）：


#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 8
typedef struct node
{
 int data;
 struct node * left;
 struct node * right;
}BTree;
typedef struct 
{
 int top;
 int data[MAXSIZE];
}Stack;
BTree * CreatTree(int a[],int n);
void Iorder(BTree * root);
void Porder(BTree * root);
void FindPath(BTree * root,int sum,int target,Stack * stack);
void InitStack(Stack * stack);
void Push(Stack * s,int val);
int Pop(Stack *s);
int main(void)
{
 int array[MAXSIZE] = {5,3,8,7,2,4,1,9},target;
 BTree * root;
 Stack stack;
 target = 12;
 root = CreatTree(array,MAXSIZE);
 InitStack(&stack);
 printf("二叉树内元素升序排列：");
 Iorder(root);
 printf("\n");
 printf("目标值：%d,路径：",target);
 FindPath(root,0,target,&stack);
 printf("\n");
 return 0;
}
//根据数组生成二叉排序树
BTree * CreatTree(int a[],int n)
{
 BTree * root ,*p,*cu,*pa;
 int i;
 root = (BTree *)malloc(sizeof(BTree));
 root->data = a[0]; 
 root->left = root->right =NULL;
 for(i=1;i<n;i++)
 {
  p = (BTree *)malloc(sizeof(BTree));
  p->data = a[i];
  p->left = p->right =NULL;
  cu = root;
  while(cu)
  {
   pa = cu;
   if(cu->data > p->data)
    cu = cu->left;
   else
    cu = cu->right;
  }
  if(pa->data > p->data)
   pa->left = p;
  else
   pa->right = p;
 } 
 return root;
}
//中根遍历，打印二叉树
void Iorder(BTree * root)
{
 if(root)
 {  
  Iorder(root->left);
  printf("%3d",root->data);
  Iorder(root->right);
 }
}
//寻找路径
void FindPath(BTree * root,int sum,int target,Stack * s)
{
 int i;
 if(!root)
  return ;
 if(sum + root->data == target)
 {
  Push(s,root->data);
  for(i = 0;i<s->top;i++)
   printf("%3d",s->data[i]);
  return;
 }
 else if(sum + root->data > target)
   {
  return;
   }
   else
   {
  Push(s,root->data);
  sum += root->data;
  FindPath(root->left,sum,target,s);
  FindPath(root->right,sum,target,s);
  sum -= root->data;
  Pop(s);
   }
}
//初始化栈
void InitStack(Stack * s)
{
 s->top = 0;
}
//入栈
void Push(Stack *s,int val)
{
 if(s->top == MAXSIZE)
 {
  printf("栈满，无法入栈！\n");
  return;
 }
 s->data[(s->top)++] = val;
}
//出栈
int Pop(Stack *s)
{
 if(s->top == 0)
 {
  printf("栈空，无法出栈!\n");
  return;
 }
 return s->data[--(s->top)];
}