【数据结构】二叉树的应用。
1、分别采用递归和非递归的方式编写两个函数,求一棵给定二叉树中叶子节点的个数
2、返回一棵给定二叉树在中序遍历下的最后一个结点
3、假设二叉树采用链式方式存储,root为其根节点,p和q分别指向二叉树中任意两个结点,编写一个函数,返回p和q最近的共同祖先。
在第三小题中采用递归:
思想:
1.判断root是不是NULL如果root为NULL,那么就无所谓祖先节点,直接返回NULL就好了
2.如果p在左子树中,q在右子树中,那么root肯定就是最近祖先
3.如果pq都在root的左子树,那么就需要递归root的左子树,右子树同理
(在找公共祖先上,find_ancestor函数有bug,暂勿复制!!!)
#include <stdio.h> #include <stdlib.h> typedef struct node{ char data; struct node *lchild,*rchild; }bintnode; bintnode *node,*p; int count; typedef struct stack{ bintnode *data[100]; int tag[100]; int top; }seqstack; void push(seqstack *s,bintnode *t) { s->data[s->top]=t; s->top++; } bintnode* pop(seqstack *s) { if(s->top!=0) { s->top--; return (s->data[s->top]); } else { return NULL; } } bintnode *createbintree() { char ch; bintnode *t; if((ch=getchar())==#) { t=NULL; } else { t=(bintnode *)malloc(sizeof(bintnode)); t->data=ch; t->lchild=createbintree(); t->rchild=createbintree(); } return t; } //递归前序遍历,返回叶子节点数 void digui_preorder(bintnode *t) { if(t) { if(!t->lchild && !t->rchild) { count++; return ; } digui_preorder(t->lchild); digui_preorder(t->rchild); } else return ; } //非递归前序遍历,返回叶子节点数 void preorder(bintnode *t) { seqstack s; s.top=0; while((t)||(s.top!=0)) { if(t) { if(!t->lchild && !t->rchild) { count++; } push(&s,t); t=t->lchild; } else { t=pop(&s); t=t->rchild; } } } //返回非递归中序遍历的最后一个结点 void inorder(bintnode *t) { seqstack s; s.top=0; while((t!=NULL) || (s.top!=0)) { if(t) { push(&s,t); t=t->lchild; } else { t=pop(&s); p=t; t=t->rchild; if(t==NULL && s.top==0) { printf("非递归中序遍历情况下,最后一个结点是:%c ",p->data); } } } } bintnode *find(bintnode *t, char str) { bintnode *p1; if(!t) return NULL; if(t->data==str) return t; else { p1=find(t->lchild,str); if(p1) return p1; else p1=find(t->rchild,str); } } bintnode *find_ancestor(bintnode *t,bintnode *p,bintnode *q) { if (!t) return NULL; if (t == p || t == q) return t; bintnode *left = find_ancestor(t->lchild, p, q); bintnode *right = find_ancestor(t->rchild, p, q); if (left && right) return t; if(left) return left; if(right) return right; } int main () { count=0; node = createbintree(); getchar(); digui_preorder(node); printf("递归求解:一共有%d个叶子节点 ",count); count = 0; preorder(node); printf("非递归求解:一共有%d个叶子节点 ",count); inorder(node); char p,q; printf("请输入要查找的两个节点的值:"); scanf("%c%c",&p,&q); getchar(); bintnode *p1,*q1; p1=find(node,p); q1=find(node,q); bintnode *t1; t1=find_ancestor(node,p1,q1); printf("最近的共同祖先为:%c",t1->data); return 0; }
下一篇:
算法与数据结构核心套路