C++实现查找二叉树中和为某一值的所有路径的示例
发布时间:2020-12-16 05:40:21 所属栏目:百科 来源:网络整理
导读:从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如 输入整数22和如下二元树 则打印出两条路径:10,12和10,5,7。 先序遍历树即可得到结果。 算法: FindPath(BTree * root,int sum,int target,Sta
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 则打印出两条路径:10,12和10,5,7。 先序遍历树即可得到结果。
#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,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,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,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,s); FindPath(root->right,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)]; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |