数据结构-树的高度

深碍√TFBOYSˉ_ 2022-05-18 02:53 137阅读 0赞

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

（**2017武汉科技大学初试**）

二叉树采用二叉链表进行存储（如下所示），每个结点包含数据域Data，左孩子指针域left和右孩子指针域right。请设计非递归算法统计二叉树的高度。

Typedef struct BitNode\{

TElemType data;

struct BitNode \*left, \*right;

\} \*BiTree ;

#include<iostream>
    #include<cstring>
    #include<cstdlib>
    #define MAXSIZE 30 
    using namespace std;
    
    typedef struct TNode{
    	char data;
    	struct TNode *lChild;
    	struct TNode *rChild;
    }TNode;
    
    int height = 0;
    
    TNode *createBTree()
    {
    	//124##57###38#9###
    	char data;
    	cin>>data;
    	TNode *bt = NULL;
    	if(data == '#')
    		return NULL;
    	else
    	{
    		
    		bt = (TNode*)malloc(sizeof(TNode));
    		bt->data = data;
    		bt->lChild = createBTree();
    		bt->rChild = createBTree();
    	}
    	return bt;
    }
    
    void preOrderRecursionVisit(TNode *bt)
    {
    	/*
    		先序遍历二叉树 
    	*/ 
    	if(bt == NULL)
    		return;
    	else
    	{
    		cout<<bt->data<<" ";
    		preOrderRecursionVisit(bt->lChild);
    		preOrderRecursionVisit(bt->rChild);
    	}
    }
    
    void getTreeHeight(TNode *root)
    {
    	/*
    		使用层次遍历，使用temp 记录访问节点的个数 
    		在第一层我们易知只有一个节点（如果存在的话），
    			循环出队，访问元素个数temp+1，然后将出队元素的子女节点加入队列（如果存在）
    				判断：如果访问节点的个数大于等于当前层的节点数，则当前层访问完毕，访问计数归零，树高+1，
    					同时我们可以进行计算下一 层节点的个数，因为当前队列存储的所有节点都是下一层的，计算队列长度就是下一层的节点数 
    			 
    		循环执行，直到队列为空 
    	*/
    	int front = 0, rear = 0, temp = 0, count = 1;
    	TNode *queue[MAXSIZE], *t;
    	rear = (rear + 1) % MAXSIZE;
    	queue[rear] = root;
    	while(rear != front)
    	{
    		front = (front + 1) % MAXSIZE;
    		t = queue[front];
    		temp++;
    		if(t->lChild)
    		{
    			rear = (rear + 1) % MAXSIZE;
    			queue[rear] = t->lChild;
    		}
    		if(t->rChild)
    		{
    			rear = (rear + 1) % MAXSIZE;
    			queue[rear] = t->rChild;
    		}
    		if(temp >= count)
    		{
    			temp = 0;
    			count = (rear - front + MAXSIZE) % MAXSIZE;
    			height++;
    		}
    	}
    }
    
    int main()
    {
    	TNode *root;
    	root = createBTree();
    	preOrderRecursionVisit(root);
    	cout<<endl;
    	
    	getTreeHeight(root);
    	cout<<"The Height Is"<<height<<endl;
    	return 0;
    }