【数据结构周周练】013 利用栈和非递归算法求二叉树的高

左手的ㄟ右手 2021-06-11 15:13 406阅读 0赞

# 一、前言 #

二叉树的高是树比较重要的一个概念，指的是树中结点的最大层数本次算法通过非递归算法来求得树的高度，借用栈来实现树中结点的存储。

**学英语真的很重要**，所以文中的注释还有输出以后会尽量用英语写，文中出现的英语语法或者单词使用错误，还希望各位英语大神能不吝赐教。

# 二、题目 #

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

![70][]

#  三、代码 #

#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;
    	int high;
    	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->high = 0;
    	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;
    	p->high = S->high;
    	S = p;
    	S->high += 1;
    	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);
    	S->high -= 1;
    	return 1;
    }
    
    // Operation of the tree
    int OperationBiTree(BiTree &T) {
    	T = (BiTree)malloc(sizeof(BiTNode));
    	if (!T)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	T->number = number;
    	number++;
    	T->data = numData[T->number];
    	T->lChild = NULL;
    	T->rChild = NULL;
    	T->parent = treeParent;
    	return 1;
    }
    
    //establish the tree, utilize recursion
    void EstablishBiTree(BiTree &T) {
    	OperationBiTree(T);
    	treeParent = T;
    	if (yesOrNo[yon++])
    		EstablishBiTree(T->lChild);
    	treeParent = T;
    	if (yesOrNo[yon++])
    		EstablishBiTree(T->rChild);
    }
    
    
    //Seek high of the tree
    int BiTreeHigh(BiTree T) {
    	BiTree p = T;
    	LinkStack S;
    	int high = 0;
    	InitStack(S);
    	while (p||S->next)
    	{
    		if (p) {
    			Push(S, p);
    			p = p->lChild;
    			if (high<S->high)
    				high = S->high;
    		}
    		else
    		{
    			Pop(S, p);
    			p = p->rChild;
    		}
    	}
    	return ++high;
    }
    
    void VisitBiTree(BiTree T) {
    	cout << "The number of present node is ：" << T->number << "; ";
    	cout << "data is ：" << T->data << "; ";
    	if (!T->parent)
    		cout << " this node is the root of the tree.\n";
    	if (!T->lChild && !T->rChild)
    		cout << " this node is the leaf of the tree.\n";
    	cout << endl;
    	
    }
    
    //Visit tree use the preorder technique. 
    void PreOrderBiTree(BiTree T) {
    	if (T)
    	{
    		VisitBiTree(T);
    		PreOrderBiTree(T->lChild);
    		PreOrderBiTree(T->rChild);
    	}
    }
    
    void main() {
    	BiTree T;
    	EstablishBiTree(T);
    	PreOrderBiTree(T);
    	cout << "The high of tree which we establish is " << BiTreeHigh(T) << endl;
    }

# 四、实现效果 #

![70 1][]

[70]: /images/20210516/34093ef9675f43c68f0f4eaf2dc92958.png
[70 1]: /images/20210516/61961006959343a5a6c4970f32ae2565.png