【数据结构周周练】014 利用栈和非递归算法求链式存储的二叉树是否为完全二叉树

不念不忘少年蓝@ 2021-06-11 15:13 398阅读 0赞

# 一、前言 #

首先，明天是个很重要的节日，以后我也会过这个节日，在这里，提前祝所有程序猿们，猿猴节快乐，哦不，是**1024程序员节快乐**。

今天要给大家分享的算法是判断二叉树是否为完全二叉树，相信大家对完全二叉树的概念并不陌生，如果是顺序存储就会很方便，那链式存储怎么判断呢，我的做法是：**若当前结点不为空将当前结点入栈，判断结点是否满足完全二叉树，满足返回1，p指向p的左孩子结点；否则返回0。若当前结点为空；出栈，并使p指向p的右孩子继续遍历，直到全部遍历完为止**。

其他思路：**结合编号，从上到下，从左往右依次对结点进行编号，并判断编号与父节点编号关系，若从0开始编号，则父节点与孩子结点的关系为**：

T->lChild == T->parent * 2 + 1
    T->rChild == (T->parent + 1) * 2

**只要出现不满足，则说明不是完全二叉树**。该算法比较简单，大家自己尝试做一下。

# 二、题目 #

将下图用二叉树存入，并判断该树是否为完全二叉树。其中圆角矩形内为结点数据，旁边数字为结点编号，编号为0的结点为根节点，箭头指向的结点为箭尾的孩子结点。

![70][] 不是完全二叉树

![70 1][] 是完全二叉树

#  三、代码 #

#define MAXQUEUESIZE 10
    
    #include<iostream>
    #include<malloc.h>
    
    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;
    
    }

# 四、实现效果 #

![70 2][] 第一棵树

对于第二颗树，只需要修改两个位置，树创建时候的两个数组：

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 };

结果如下：

![70 3][] 第二棵树

[70]: /images/20210516/ffda3e95b6744ca99a3554bf3ad3f40b.png
[70 1]: /images/20210516/d5bd50377f1b4f7ea9f679d30d2b6777.png
[70 2]: /images/20210516/5bf6c49e2f034638ac58474ffb916df6.png
[70 3]: /images/20210516/0f770b6a63e34491aa18e96dcb41c70e.png