我们知道，任何的树都可以转化成二叉树，因此，本系列文章仅提供二叉树的实现，在二叉树中，高度为 $h$ 的满二叉树由 $2^{h}-1$ 个结点，直观来看，将满二叉树的最深一层，删除最右侧的若干个叶子结点则为完全二叉树。二叉树可以用顺序二叉树或链二叉树来实现，但是顺序二叉树只有在完全二叉树时才没有内存浪费，故本文只实现链二叉树。

首先，创建一个头文件erchashu.h，写一个求两个数最大值的函数备用。

#include<iostream>
#include<math.h>
#include<string.h>
using namespace std; 
int max2(int a, int b)//求两个数最大值函数，备用
{
	if (a > b)
		return a;
	else
		return b;
}

创建二叉树的结点，包含数据，左孩子指针，右孩子指针。

struct btNode //二叉树结点
{
	char data;
	btNode* lchild, *rchild;
};

为二叉树赋值

void createBT(btNode *&b,char str[])//用括号型表示法为二叉树赋值
{
	btNode* stack[100];
	int top = -1;//实现一个栈
	int k = 1, j = ;
	btNode* p;
	char ch;//用于扫描括号型表示字符串
	b = NULL;
	ch = str[j];
	p = (btNode*)malloc(sizeof(btNode));
	while (ch != '\0')
	{
		switch (ch)
		{
		case '(':
			top++;
			stack[top] = p;
			k = 1;
			break;
		case ')':
			top--;
			break;
		case ',':
			k = 2;
			break;
		default:
			p = (btNode*)malloc(sizeof(btNode));
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (b == NULL)
				b = p;
			else
			{
				if (k == 1)
					stack[top]->lchild = p;
				if (k == 2)
					stack[top]->rchild = p;
			}
		}
		j++;
		ch = str[j];
	}
}

接下来的操作要频繁用到递归的思想；销毁二叉树。

void destroyBT(btNode*& b)//销毁二叉树
{
	if (b != NULL)
	{
		destroyBT(b->lchild);
		destroyBT(b->rchild);
		free(b);
	}
}

查找元素。

btNode* findBT(btNode*& b, char x)//寻找数据为x的结点
{
	if (b == NULL)
		return NULL;
	else
	{
		if (b->data == x)
			return b;
		else
		{
			if (findBT(b->lchild, x) == NULL)
			return findBT(b->rchild, x);
			else
				return findBT(b->lchild, x);
		}
	}
}

求高度。

int BTdepth(btNode*& b)//求二叉树高度
{
	if (b == NULL)
		return ;
	else
	return max2(BTdepth(b->lchild), BTdepth(b->rchild))+1;
}

输出括号型表达式。

void dispBT(btNode*& b)//用括号型表示法输出二叉树
{
	if (b != NULL)
	{
		cout << b->data;
			if (b->lchild != NULL || b->rchild != NULL)
			{
				cout << '(';
				dispBT(b->lchild);
				cout << ',';
				dispBT(b->rchild);
				cout << ')';
			}
	}
}

在遍历二叉树中，在任何一个节点处，有三部分需要访问：左子树、右子树、根节点，我们不妨让左子树在右子树前访问，这样就有三种遍历方法，按照根节点的访问位置，分为前序遍历，中序遍历，后序遍历。下面是用访问并输出数据给出一个例子，可以换成其它操作。

void preOrder(btNode*& b)//前序遍历并输出
{
	if (b != NULL)
	{
		cout << b->data;
		preOrder(b->lchild);
		preOrder(b->rchild);
	}
}
void inOrder(btNode*& b)//中序遍历并输出
{
	if (b != NULL)
	{
		inOrder(b->lchild);
		cout << b->data;
		inOrder(b->rchild);
	}
}
void postOrder(btNode*& b)//后序遍历并输出
{
	if (b != NULL)
	{
		postOrder(b->lchild);
		postOrder(b->rchild);
		cout << b->data;
	}
}

以下是验证程序。

#include<iostream>
#include<math.h>
#include<string.h>
#include"erchashu.h"
using namespace std;
int main()
{
	char str[100] = "A(B(D(G,),),C(E,F))";
	btNode* b, * b2;
	b = (btNode*)malloc(sizeof(btNode));
	createBT(b, str);
	b2 = findBT(b, 'B');
	cout << b2->data;
	cout << BTdepth(b) << endl;
	dispBT(b);
	cout << endl;
	dispBT(b2);
	cout << endl;
	preOrder(b);
	cout << endl;
	inOrder(b);
	cout << endl;
	postOrder(b);
	destroyBT(b);
}

ITPub博客

数据结构与算法实现（6）——二叉树

最新文章