快捷導(dǎo)航

C++實(shí)現(xiàn)查找二叉樹中和為某一值的所有路徑的示例

更新時(shí)間：2016年02月04日 17:29:43 作者：Zhang_H

這篇文章主要介紹了C++實(shí)現(xiàn)查找二叉樹中和為某一值的所有路徑的示例,文中的方法是根據(jù)數(shù)組生成二叉排序樹并進(jìn)行遍歷,需要的朋友可以參考下

從樹的根結(jié)點(diǎn)開始往下訪問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。
打印出和與輸入整數(shù)相等的所有路徑。
例如輸入整數(shù)22和如下二元樹

201624172555583.png (138×105)

則打印出兩條路徑：10, 12和10, 5, 7。

先序遍歷樹即可得到結(jié)果。
算法: FindPath(BTree * root,int sum,int target,Stack * s) 用來(lái)計(jì)算，sum為棧中的元素的和，target為目標(biāo)值。
到達(dá)一個(gè)節(jié)點(diǎn)之后計(jì)算當(dāng)前節(jié)點(diǎn)和sum的和，如果為target，輸出路徑返回，如果大于target，則直接返回，如果小于，則將當(dāng)前節(jié)點(diǎn)的值入棧，更新sum的值，繼續(xù)遍歷，遍歷完成之后，也就是從當(dāng)前節(jié)點(diǎn)返回的時(shí)候，將其從棧中彈出，更新sum
代碼如下（GCC編譯通過(guò)）：

#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("二叉樹內(nèi)元素升序排列：");
 Iorder(root);
 printf("\n");
 
 printf("目標(biāo)值：%d,路徑：",target);
 FindPath(root,0,target,&stack);
 
 printf("\n");
 return 0;
}
 
//根據(jù)數(shù)組生成二叉排序樹
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("棧滿，無(wú)法入棧！\n");
  return;
 }
 s->data[(s->top)++] = val;
 
}
 
//出棧
int Pop(Stack *s)
{
 if(s->top == 0)
 {
  printf("?？眨瑹o(wú)法出棧!\n");
  return;
 }
  
 return s->data[--(s->top)];
}

您可能感興趣的文章: