데이터 구조의 이 진 트 리 깊이 우선 옮 겨 다 니 기

이 진 트 리 의 옮 겨 다 니 는 방식 을 두 가지 로 나 눌 수 있 습 니 다.
깊이
선착순
중간 순서 로 배열 하 다.
뒤 순 서 를 옮 겨 다 닌 다.
2. 넓이 (즉 왼쪽 에서 오른쪽으로)
차례차례 편력 하 다
다음은 깊이 의 세 가지 스 트 리밍 방식 입 니 다.
#include

using namespace std;


typedef struct BitNode{
	char data;
	struct  BitNode *lchild, *rchild;
}BitNode,*BiTree;

void CreateBiTree(BiTree &T);
void PreOrderTraverse(BiTree T);
void InOrderTraverse(BiTree T);
void PostOrderTraverse(BiTree T);



void CreateBiTree(BiTree &T)
{
	
	//                  ,
	//  :ab##c##

	char ch;
	scanf("%c",&ch);
	if (ch == '#')	T = NULL;//     
	else
	{
		T = new BitNode;
		if (T)
		{
			T->data = ch;
			CreateBiTree(T->lchild);
			CreateBiTree(T->rchild);
		}
	}
}


//       
void PreOrderTraverse(BiTree T)
{
	if (T != NULL)
	{
		cout << T->data << endl;
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

//       
void InOrderTraverse(BiTree T)
{
	if (T != NULL)
	{
		InOrderTraverse(T->lchild);
		cout << T->data << endl;
		InOrderTraverse(T->rchild);
	}
}


//       
void PostOrderTraverse(BiTree T)
{
	if (T != NULL)
	{
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		cout<< T->data << endl;
	}
}




int main()
{
	BiTree T;
	CreateBiTree(T);
	cout << "       ,      :" << endl;
	PreOrderTraverse(T);
	cout << "      :" << endl;
	InOrderTraverse(T);
	cout << "      :" << endl;
	PostOrderTraverse(T);
	return 0;
}

좋은 웹페이지 즐겨찾기