二叉樹層次周遊和深度周遊

二叉樹層次周遊和深度周遊

源碼實作過程：

#include <stdio.h>

#include <QUEUE> //必須使用的是QUEUE，和using namespace std,缺一不可;

#include <STACK>

using namespace std;

typedef  char DataType;

typedef struct Node {

DataType elem;

Node * rChild;

Node * lChild;

}NODE,*pNode;

queue<pNode> Q;

bool creat(pNode &root){

DataType temp;

scanf("%c",&temp);

if (temp==EOF)

{

return false;

}else if(temp=='#')

{

root = NULL;

}else{

root = (pNode )malloc(sizeof(Node));

root->elem=temp;

creat(root->lChild);

creat(root->rChild);

}

return true;

}

void preOrder(pNode root){

if (root!=NULL)

{

printf("%c ",root->elem);

if (root->lChild)

{

preOrder(root->lChild);

}

if (root->rChild)

{

preOrder(root->rChild);

}

}

}

void inOrder(pNode root){

if (root!=NULL)

{

if (root->lChild)

{

inOrder(root->lChild);

}

printf("%c ",root->elem);

if (root->rChild)

{

inOrder(root->rChild);

}

}

}

//這是錯誤的，原因是使用了遞歸，将所有節點都加入到了隊列中，再開始出隊。造成了有重複的節點加入。

void level_print(pNode &root){

if (root != NULL)

{

// printf("%c",root->elem);

if (Q.empty())//放入第一個節點

{

Q.push(root);

}

if (root->lChild)

{

Q.push(root->lChild);

}

if (root->rChild)

{

Q.push(root->rChild);

}

if (root->lChild)

{

level_print(root->lChild);

}

if (root->rChild)

{

level_print(root->rChild);

}

}

while(!Q.empty())

{

pNode temp = Q.front();

printf("%c ",temp->elem);

Q.pop();

}

}

//這個算法是成功的實作了樹的層次周遊

void level_print2(pNode root){

while (!Q.empty())//清空隊列

{

Q.pop();

}

if (root)//先使根節點入隊

{

Q.push(root);

}

do 

{

pNode temp; 

temp = Q.front();

printf("%c ",temp->elem);

Q.pop();

if (temp->lChild)//如果左子樹不為空，将左子樹入隊

{

Q.push(temp->lChild);

}

if (temp->rChild)//如果右子樹不為空，将右子樹入隊

{

Q.push(temp->rChild);

}

}while (!Q.empty());

}

// 如果要實作按層列印數的話，還是修改樹的層次周遊，注意的是要統計樹中每層的個數

void level_print3(pNode root){

int parentSize=1;

int childSize=0;

// 1.清空樹；

while (!Q.empty())

{

Q.pop();

}

// 2.将樹分層次加入到隊列中

Q.push(root);

do 

{

pNode temp = Q.front();

printf("%c ",temp->elem);

Q.pop();

parentSize--;

if (temp->lChild)

{

Q.push(temp->lChild);

childSize++;

}

if (temp->rChild)

{

Q.push(temp->rChild);

childSize++;

}

if (parentSize==0)

{

parentSize=childSize;

childSize=0;

printf("\n");

}

} while (!Q.empty());

}

// 因為深度優先周遊，周遊了根節點後，就開始周遊左子樹，

// 是以右子樹肯定最後周遊。我們利用棧的性質，先将右子

// 樹壓棧，然後在對左子樹壓棧。此時，左子樹節點是在top上的，

// 是以可以先去周遊左子樹。

void DepthFirstTravel(pNode root){

stack<pNode> S;

if (root)

{

S.push(root);

}

while (!S.empty())

{

pNode temp = S.top();

printf("%c ",temp->elem);

S.pop();

if (temp->rChild)

{

S.push(temp->rChild);

}

if (temp->lChild)

{

S.push(temp->lChild);

}

}

}

int main(){

pNode T;

creat(T);

printf("preOrder:");

preOrder(T);

printf("\n");

printf("inOrder:");

inOrder(T);

printf("\n");

printf("level_travel is :\n");

  level_print2(T);

printf("\n");

printf("level_travel is :\n");

level_print3(T);

printf("\n");

printf("DepthFirstTravel is :\n");

DepthFirstTravel(T);

printf("\n");

// queue<int> q;

// q.push(1);

// q.push(2);

// q.push(3);

// q.push(4);

// while(!q.empty()){

// printf("%d ",q.front());

// q.pop();

// }

// printf("\n");

return 0;

}