本文共 2714 字,大约阅读时间需要 9 分钟。
首先,明天是个很重要的节日,以后我也会过这个节日,在这里,提前祝所有程序猿们,猿猴节快乐,哦不,是1024程序员节快乐。
今天要给大家分享的算法是判断二叉树是否为完全二叉树,相信大家对完全二叉树的概念并不陌生,如果是顺序存储就会很方便,那链式存储怎么判断呢,我的做法是:若当前结点不为空将当前结点入栈,判断结点是否满足完全二叉树,满足返回1,p指向p的左孩子结点;否则返回0。若当前结点为空;出栈,并使p指向p的右孩子继续遍历,直到全部遍历完为止。
其他思路:结合编号,从上到下,从左往右依次对结点进行编号,并判断编号与父节点编号关系,若从0开始编号,则父节点与孩子结点的关系为:
T->lChild == T->parent * 2 + 1T->rChild == (T->parent + 1) * 2
只要出现不满足,则说明不是完全二叉树。该算法比较简单,大家自己尝试做一下。
将下图用二叉树存入,并判断该树是否为完全二叉树。其中圆角矩形内为结点数据,旁边数字为结点编号,编号为0的结点为根节点,箭头指向的结点为箭尾的孩子结点。
#define MAXQUEUESIZE 10#include#include using namespace std;typedef struct BiTNode { int data; int number; struct BiTNode *lChild, *rChild, *parent;}BiTNode, *BiTree;typedef BiTree SElemType;typedef struct LNode{ SElemType data; struct LNode *next;}LNode,*LinkStack;int number = 0;int yon = 0;int yesOrNo[] = { 1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0 };int numData[] = { 1,2,4,3,5,7,8,6 };BiTree treeParent = NULL;int InitStack(LinkStack &S) { S = (LinkStack)malloc(sizeof(LNode)); if (!S) { cout << "空间分配失败(Allocate space failure)" << endl; exit(OVERFLOW); } S->next = NULL; return 1;}int Push(LinkStack &S, SElemType e) { LinkStack p = (LinkStack)malloc(sizeof(LNode)); if (!p) { cout << "结点分配失败(Allocate node failure)" << endl; exit(OVERFLOW); } S->data = e; p->next = S; S = p; return 1;}int Pop(LinkStack &S, SElemType &e) { LinkStack p = S->next; if (!p) { cout << "栈空(The stack is null)" << endl; exit(OVERFLOW); } e = p->data; S->next = p->next; free(p); return 1;}int OperationBiTree(BiTree &T) { T = (BiTree)malloc(sizeof(BiTNode)); if(!T){ cout << "空间分配失败(Allocate space failure.)" << endl; exit(OVERFLOW); } T->number = number; T->data = numData[number]; number++; T->lChild = NULL; T->rChild = NULL; T->parent = treeParent; return 1;}void EstablishBiTree(BiTree &T) { OperationBiTree(T); treeParent = T; if (yesOrNo[yon++]) EstablishBiTree(T->lChild); treeParent = T; if (yesOrNo[yon++]) EstablishBiTree(T->rChild);}int Judge(BiTree T) { BiTree p = T; if (!p->rChild && p->lChild) { if (p->lChild || p->rChild) return 0; } else if (p->rChild && !p->lChild) return 0; else return 1;}int JudgeCompleteBiTree(BiTree T) { BiTree p = T; LinkStack S; InitStack(S); while (p||S->next) { if (p) { Push(S, p); if (Judge(p)) p = p->lChild; else return 0; } else { Pop(S, p); p = p->rChild; } } return 1;}void main() { BiTree T; EstablishBiTree(T); if (JudgeCompleteBiTree(T)) cout << "This binary tree is a complete binary tree" << endl; else cout << "This binary tree isn't a complete binary tree" << endl;}
对于第二颗树,只需要修改两个位置,树创建时候的两个数组:
int yesOrNo[] = { 1,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0 };int numData[] = { 1,2,4,8,9,5,3,6,7 };
结果如下: