【数据结构周周练】008 二叉树的链式创建及测试

今天药忘吃喽~ 2021-09-16 16:06 323阅读 0赞

# 一、前言 #

二叉树的顺序结构实现虽然很容易，但是在创建过程中，不免要浪费掉很多空间，为了减少空间浪费，从而提出链表的链式存储，虽然链式存储也很浪费空间，但是在某些二叉树中要节约很多空间，同时，浪费的这些空间我们可以用于存储其他信息，我们在后续的线索二叉树代码中会给大家讲解到。

本文的所有代码都是根据自己的理解编写的，严蔚敏老师的数据结构书上并没有在创立之初就给出普通二叉树的创建过程，而是通过二叉树的遍历来实现二叉树的创建过程，而且书上的创建过程通过的是迭代，后面还会写博客应用迭代的方法，本次练习是为了锻炼自己对二叉树创建的操作，因为二叉树的创建过程也是遍历过程，这个过程很重要，会为后续操作起到帮助作用，所以就自己尝试写了一下代码。

同时本文利用到栈的一些基础操作，来辅助生成二叉树，希望大家能喜欢我的算法，如果大家有别的算法，可以一起交流。本文还应用了goto语句，有对goto语句不熟悉的同学可以先看博客：[C++ goto语句详解 ][C_ goto_]，对goto语句做简单了解。

# 二、题目 #

将下图用二叉树存入，并做测试。其中圆角矩形内为结点数据，旁边数字为结点编号，编号为0的结点为根节点，箭头指向的结点为箭尾的孩子结点。要求创建的结点能够查询当前结点的双亲结点、孩子结点、编号。

![70][]

#  三、代码 #

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct BiTNode {
    	int data;
    	int number;
    	int isAsk;
    	struct BiTNode * lChild, * rChild, * parent;
    }BiTNode,*BiTree;
    
    typedef struct LNode{
    	BiTree stackData;
    	struct LNode *next;
    
    }LNode, *LinkStack;
    
    int Push(LinkStack &S, BiTree &bt) {
    	LinkStack p = (LinkStack)malloc(sizeof(LNode));
    	S->stackData = bt;
    	p->next = S;
    	S = p;
    	return 1;
    }
    
    int Pop(LinkStack &S/*, BiTree &bt*/) {
    	if (!S->next)
    	{
    		cout << "栈已空" << endl;
    		return 0;
    	}
    	LinkStack p = S->next;
    	//bt = p->stackData;
    	S->next = p->next;
    	free(p);
    }
    
    BiTree GetTopTree(LinkStack S) {
    	if (S->next)
    	{
    		return S->next->stackData;
    	}
    	return NULL;
    }
    
    int InitBiTree(BiTree &BT,int e) {
    	BT = (BiTree)malloc(sizeof(BiTNode));
    	if (!BT)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	BT->data = e;
    	BT->number = 0;
    	BT->isAsk = 0;
    	BT->lChild = NULL;
    	BT->rChild = NULL;
    	BT->parent = NULL;
    	
    }
    
    int CreatBiTree(BiTree &BT) {
    	//创建一个辅助空间栈，用来创建树
    	LinkStack S = (LinkStack)malloc(sizeof(LNode));
    	if (!S)
    	{
    		cout << "栈空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    
    	BiTree tree = BT;
    	Push(S, tree);
    	BiTree t;
    	//创建剩余结点
    	int e; 
    	int num = 1;
    	int yesOrNo;
    	int nodeNum;
    
    	cout << "请输入该树有多少个结点：";
    	cin >> nodeNum;
    	loop:while (num<nodeNum)
    	{
    		t = (BiTree)malloc(sizeof(BiTNode));
    		t->isAsk = 0;
    		t->lChild = NULL;
    		t->rChild = NULL;
    		cout << "当前结点标号为"<<tree->number<<"，该结点是否有左子树，有请输入1，没有请输入0：";
    		cin >> yesOrNo;
    		tree->isAsk = (tree->isAsk + 1) * 10;
    		if (yesOrNo)
    		{
    			cout << "请输入当前结点 " << tree->number << " 的左孩子的值：";
    			cin >> e;
    			t->data = e;
    			t->number = num;
    			//t->parent = GetTopTree(S);
    			t->parent = tree;
    			tree->lChild = t;
    			tree = t;
    			num++;
    			Push(S, tree);
    			goto loop;
    
    		}
    
    		loopRC:if (tree->isAsk%10 == 0)
    		{
    			cout << "当前结点标号为" << tree->number << "，该结点是否有右子树，有请输入1，没有请输入0：";
    			cin >> yesOrNo;
    			tree->isAsk++;
    			if (yesOrNo)
    			{
    				cout << "请输入当前结点 " << tree->number << " 的右孩子的值：";
    				cin >> e;
    				t->data = e;
    				t->number = num;
    				//t->parent = GetTopTree(S);
    				t->parent = tree;
    				tree->rChild = t;
    				tree = t;
    				num++;
    				Push(S, tree);
    				goto loop;
    			}
    			else
    			{
    				tree = tree->parent;
    				Pop(S);
    				goto loopRC;
    			}
    		}
    		else
    		{
    			tree = tree->parent;
    			Pop(S);
    			goto loopRC;
    		}
    		
    	}
    
    }
    
    void main() {
    	BiTree BT;
    	int e;
    	cout << "请输入根结点数据 : ";
    	cin >> e;
    	InitBiTree(BT, e);
    	CreatBiTree(BT);
    	cout << "\n********************************************************\n" << endl;
    	cout << "根节点数据为 :" << BT->data << endl;
    	if (BT->lChild)
    	{
    		cout << "该树的根有左孩子，左孩子的编号 :" << BT->lChild->number << endl;
    		cout << "                  左孩子的数据 :" << BT->lChild->data << endl;
    		if (BT->lChild->lChild)
    		{
    			cout << "该树的左孩子有左孩子，编号为 :" << BT->lChild->lChild->number << endl;
    		}
    		else
    		{
    			cout << "该树的左孩子没有左孩子." << endl;
    		}
    	}
    }

# 四、实现效果 #

![70 1][]

[C_ goto_]: https://blog.csdn.net/shuiyixin/article/details/83151977
[70]: /images/20210516/c0729c5dba9b469db7b19844bf2c2e34.png
[70 1]: /images/20210516/1f77f176151c4c109cc0282434fc90b2.png