数据结构-判断是否为完全二叉树

约定不等于承诺〃 2022-05-18 04:06 223阅读 0赞

***【题目来自灰灰考研】***

**层次遍历题目变形：**

1.二叉树采用二叉链表进行存储（如下所示），每个结点包含数据域Data，左孩子指针域left和右孩子指针域right。请设计算法判断树是否为**完全二叉树**。

Typedef struct BitNode\{

TElemType data;

struct BitNode \*left, \*right;

\} \*BiTree ;

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #define MAXSIZE 20
    using namespace std;
    
    typedef struct TNode{
    	char data;
    	struct TNode *lChild, *rChild;
    }TNode;
    
    TNode *createBTree()
    {
    	//124##57###38#9###
    	TNode *node;
    	char data;
    	cin>>data;
    	if(data == '#')
    		return NULL;
    	else
    	{
    		node = (TNode*)malloc(sizeof(TNode));
    		node->data = data;
    		node->lChild = createBTree();
    		node->rChild = createBTree();
    	}
    	return node;
    }
    
    
    bool isCompleteBTree(TNode *root)
    {
    	/*
    		使用层次遍历 
    	*/
    	int front = 0, rear = 0;
    	TNode *queue[MAXSIZE], *p;
    	rear = (rear + 1) % MAXSIZE;
    	queue[rear] = root;
    	while(rear != front)
    	{
    		front = (front + 1) % MAXSIZE;
    		p = queue[front];
    //		cout<<p->data<<" ";
    		/*
    			如果当前节点为叶子节点，则队列中剩余的节点都是叶子节点
    			如果当前节点只有左孩子，那么这个节点一定是最后一个节点
    			如果当前节点只有右孩子，那么肯定不是完全二叉树 
    		*/ 
    		if(p->lChild && p->rChild)
    		{
    			rear = (rear + 1) % MAXSIZE;
    			queue[rear] = p->lChild;
    			rear = (rear + 1) % MAXSIZE;
    			queue[rear] = p->rChild;
    		}
    		else if(p->lChild && p->rChild == NULL)
    		{
    			int count = (rear - front + MAXSIZE) % MAXSIZE;
    			if(count)
    				return false;
    		}
    		else if(p->rChild && p->lChild == NULL)
    		{
    			return false;
    		}
    		else if(p->rChild == NULL && p->lChild == NULL)
    		{
    			while(rear != front)
    			{
    				front = (front + 1) % MAXSIZE;
    				p = queue[front];
    				if(p->rChild || p->rChild)
    					return false;
    			}
    		}
    	}
    	return true;
    }
    
    int main()
    {
    	TNode *root;
    	root = createBTree();
    	bool result = isCompleteBTree(root);
    	cout<<"If is A Complete Binary Tree?："<<boolalpha<<result<<endl;
    	return 0;
    }