二叉樹的存儲與周遊

文章目錄

• 二叉樹的存儲結構
• 周遊二叉樹

二叉樹的存儲結構

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);
}