樹和二叉樹基本概念以及二叉樹周遊

一、 樹    

 
 樹是具有層次結構的n(n>0)個結點的有限集。       
     
      
  
          

    樹的結點包含一個資料元素及若幹指向其子樹的分支。

    結點的度：結點擁有子樹的數量；A的度為3，K的度為0。

    葉子結點(終端結點)：度為0的結點；K、L、F、G、M、I、J為葉子結點。

    分支結點(非終端結點)：度不為0的結點。A、B、C、D、E、H為分支結點。

    内部結點：除根結點外，其餘分支結點；B、C、D、E、H為内部結點。

    有序樹：有序樹的子樹從左到右是有序的；

例如：B是A的第1個孩子；D是A的最後一個孩子。

    森林：m(m>0)棵互不相交的樹；

二、 二叉樹

    二叉樹的每個結點至多有兩棵子樹，且二叉樹的子樹有左右之分，次序不能颠倒。（二叉樹是一個遞歸定義）。

    二叉樹的存儲方式：

    2.1  順序存儲結構：用一組位址連續的存儲單元依次自上而下、自左而右存儲二叉樹上的結點元素。僅适用于完全二叉樹（完全二叉樹包含滿二叉樹）。

    2.2  鍊式存儲結構：

           2.2.1： （二叉連結清單）連結清單結點包含3個域：資料域、左指針域、右指針域

           2.2.2： （三叉連結清單）連結清單結點包含4個域：資料域、左指針域、父指針域、右指針域

三、 周遊二叉樹

     周遊二叉樹：按照某條搜尋路徑通路樹中的每個結點，使得每個結點均被通路一次，且僅被通路一次。

     二叉樹周遊實作了對一個非線性結構進行線性化的操作，進而使每個結點線上性序列中有且隻有一個直接前驅和直接後繼。

     按照根節點被通路的順序，有3種周遊方案：先序周遊、中序周遊、後序周遊；二叉樹的周遊方案也是遞歸。

     二叉樹的遞歸周遊：先序周遊，中序周遊，後序周遊；以及非遞歸周遊：先序周遊，中序周遊；層次周遊代碼如下：

#include "stdafx.h"
#include "iostream"
#include "stack"
#include "queue"
using namespace std;
typedef char ElemType;
typedef struct node
{
	ElemType data;
	struct node *lChild, *rChild;
}BiTNode,*BiTree;
//按照先序順序建立二叉樹
void createBiTree(BiTree &T) {
	ElemType elem;    
	//'#'代表空樹
	cin >> elem;
	if (elem=='#')    //遞歸的出口條件
	{
		T = NULL;
	}
	else
	{
		T = new node;
		T->data = elem;
		createBiTree(T->lChild);
		createBiTree(T->rChild);
	}
}
void visit(ElemType elem) {
	if (elem!='#')
		cout << elem << "  ";
}
//遞歸寫法，先序周遊
void preOrderTraverse(BiTree &T) {
	if (T!=NULL) {
		visit(T->data);
		preOrderTraverse(T->lChild);
		preOrderTraverse(T->rChild);
	}
}
//中序周遊
void inOrderTraverse(BiTree &T) {
	if (T!=NULL)
	{
		inOrderTraverse(T->lChild);
		visit(T->data);
		inOrderTraverse(T->rChild);
	}
}
//後序周遊
void postOrderTraverse(BiTree &T) {
	if (T!=NULL)
	{
		postOrderTraverse(T->lChild);
		postOrderTraverse(T->rChild);
		visit(T->data);
	}
}
//非遞歸周遊,将T入棧，周遊完左子樹傳回時，棧頂應該為T，T出棧，然後通路右子樹
void postOrderTraverse2(BiTree &T) {
	stack<BiTree> stack;
	if (T==NULL)
	{
		cout << "二叉樹不存在！" << endl;
		exit(1);
	}
	BiTree p = T;
	//棧或目前結點p不為空時循環
	while(p||!stack.empty())
	{
		if (p!=NULL)
		{
			stack.push(p);
			visit(p->data);
			p = p->lChild;
		}
		else
		{
			p = stack.top();
			stack.pop();
			p = p->rChild;
		}
	}
}
//非遞歸周遊，中序周遊
void inOrderTraverse2(BiTree &T) {
	stack<BiTree> stack;
	BiTree p = T;
	while (p||!stack.empty())
	{
		if (p!=NULL)
		{
			stack.push(p);
			p = p->lChild;
		}
		else
		{
			p = stack.top();
			visit(p->data);
			stack.pop();
			p = p->rChild;
		}
	}
}
//按層次周遊，運用隊列，自頂向下，自左向右逐層通路每個結點
void levelOrderTraverse(BiTree &T) {
	BiTree p = T;
	queue<BiTree> queue;
	queue.push(p);              //根結點入隊
	while (!queue.empty())
	{
		p = queue.front();     //周遊隊頭節點，出隊，
		visit(p->data);
		queue.pop();
		if (p->lChild!=NULL)   //每次都将隊頭節點的左、右子結點入隊
		{
			queue.push(p->lChild);
		}
		if (p->rChild!=NULL)
		{
			queue.push(p->rChild);
		}
	}
}
int main()
{
	BiTree tree;
	createBiTree(tree);
	cout << "遞歸周遊："<<endl;
	cout << "先序周遊：";
	preOrderTraverse(tree);
	cout << endl << "中序周遊：";
	inOrderTraverse(tree);
	cout << endl << "後序周遊：";
	postOrderTraverse(tree);
	cout << endl << "非遞歸周遊" << endl;
	cout << "先序周遊：";
	postOrderTraverse2(tree);
	cout << endl << "中序周遊：";
	inOrderTraverse2(tree);
	cout << endl;
	cout << "層次周遊：";
	levelOrderTraverse(tree);
	cout << endl;
	return 0;
}