二叉树的存储与遍历

文章目录

• 二叉树的存储结构
• 遍历二叉树

二叉树的存储结构

1.顺序存储结构

存储的结构体为：

typedef struct
{
    DataType data[MaxTreeNodeNum];
    int n;
}QBTree;
           

这种存储方式的优点是：空间利用率高、寻找孩子和双亲比较容易。

缺点：若二叉树不是完全二叉树的话，那么就必然会有空缺的位置，空缺的位置需要用特定的符号填补，若空缺节点比较多，势必造成空间利用率的下降。

2.链式存储结构

结构体为：

typedef struct bnode
{
    DataType data;
    struct bnode *lchild,*rchild;
}Bnode,*BTree;
           

优点：寻找孩子节点比较容易，空间利用率比较高

缺点：寻找双亲比较困难。

如果需要频繁的访问双亲的话，可以给每一个节点添加一个指向双亲节点的指针域。

遍历二叉树

四种遍历方式：先序遍历，中序遍历，后序遍历，层次遍历。

下面我们遍历一下这颗二叉树。

在创建这颗树的时候，用#表示空结点。

层次遍历的结果是ABCDEFGH

#include<iostream>
#include<queue>
using namespace std;
typedef char DataType;
typedef struct bnode
{
	DataType data;
	struct bnode *lchild, *rchild;
}Bnode,*BTree;
//将s里面从第i个字符开始生成长度为m的树
Bnode* CreatBTree(string s,int i,int m)
{
	if (i >= m)  //无效结点
	{
		return NULL;
	}
	Bnode *p=new Bnode;
	p->data = s[i];
	p->lchild = CreatBTree(s, 2 * i + 1, m);//创建新结点的左结点
	p->rchild = CreatBTree(s, 2 * i + 2, m);//创建新结点的右结点
	return p;
}

//先序遍历
void PreOrder(BTree t)
{
	if (t && t->data != '#')
	{
		cout << t->data;     //输出结点数据
		PreOrder(t->lchild);//访问左孩子
		PreOrder(t->rchild);//访问右孩子
	}
}

//中序遍历
void InOrder(BTree t)
{
	if (t && t->data != '#')
	{
		InOrder(t->lchild);//访问左孩子
		cout << t->data;     //输出结点数据
		InOrder(t->rchild);//访问右孩子
	}
}

//后序遍历
void PostOrder(BTree t)
{
	if (t && t->data != '#')
	{
		PostOrder(t->lchild);//访问左孩子
		PostOrder(t->rchild);//访问右孩子
		cout << t->data;     //输出结点数据
	}
}

//按层次遍历
void CengOrder(BTree t)
{
	BTree p ;
	queue<BTree> s;   //创建队列
	s.push(t);   //将第一个元素入队
	while (!s.empty())
	{
		p = s.front();   //获得队首元素
		if (p->lchild && p->lchild->data != '#')
		{
			s.push(p->lchild);  //将这个结点的左孩子入队
		}
		if (p->rchild && p->rchild->data != '#')
		{
			s.push(p->rchild);  //将这个结点的右孩子入队
		}
		cout << p->data;  //输出结点数据

		s.pop();   //将队首元素弹出
	}
}
int main()
{
	string s = "ABCD#EF#G####H#";
	//创建二叉树，无效结点使用#来替代
	BTree BT = CreatBTree(s, 0, s.size());

	//遍历二叉树
	cout << "先序遍历的结果是：";
	PreOrder(BT);  //先序遍历
	cout << endl;
	cout << "中序遍历的结果是：";
	InOrder(BT);   //中序遍历
	cout << endl;
	cout << "后序遍历的结果是：";
	PostOrder(BT);  //后序遍历
	cout << endl;
	cout << "层次遍历的结果是：";
	CengOrder(BT);
}