二叉树的基本操作

二叉树的基本操作，包括递归和非递归遍历

// 面试题6-1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <malloc.h>
#include <stack>    //栈: 先中后遍历非递归
#include <queue>    //队列：层次遍历

typedef struct BiTNode {
intdata;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

/*************二叉树基本操作***************/
//创建二叉树的单结点
BiTNode* CreateBiTNode(int value)
{
BiTNode* pNode = (BiTNode*) malloc(sizeof(BiTNode));
pNode->data = value;
pNode->lchild = NULL;
pNode->rchild = NULL;

return pNode;
}

//连接结点
void ConnectBiTNode(BiTNode* parent, BiTNode* pLeft, BiTNode* pRight)
{
if(parent == NULL)
return;
parent->lchild = pLeft;
parent->rchild = pRight;
}

//打印单个结点
void PrintBiTNode(BiTNode* pNode)
{
if(pNode == NULL)
{
printf("this node is null.\n");
return;
}
printf("the value of the node is %d\n", pNode->data);
if(pNode->lchild != NULL)
printf("the left child of the node is %d\n", pNode->lchild->data);
else
printf("the left child of the node is null\n");

if(pNode->rchild != NULL)
printf("the right child of the node is %d\n", pNode->rchild->data);
else
printf("the right child of the node is null\n");
printf("\n");
}

void VisitData(BiTNode* pNode)
{
if(pNode != NULL)
{
printf("%d ", pNode->data);
}
}

//遍历二叉树
//1.先序遍历(递归)
void PreOderTraverse(BiTNode* pRoot)
{
if(pRoot != NULL)
{     
PrintBiTNode(pRoot);
//if(pRoot->lchild != NULL)
PreOderTraverse(pRoot->lchild);
//if(pRoot->rchild != NULL)
PreOderTraverse(pRoot->rchild);
}
}

//2.中序遍历（递归）
void InOderTraverse(BiTNode* pRoot)
{
if(pRoot != NULL)
{
InOderTraverse(pRoot->lchild);
PrintBiTNode(pRoot);
InOderTraverse(pRoot->rchild);
}
}

//3.后续遍历（递归）
void PostOderTraverse(BiTNode* pRoot)
{
if(pRoot != NULL)
{
PostOderTraverse(pRoot->lchild);
PostOderTraverse(pRoot->rchild);
PrintBiTNode(pRoot);
}
}

//1.先序遍历(非递归)
void PreOderTraverse1(BiTNode* pRoot)
{
std::stack<BiTNode*> pNode;
BiTNode* p = pRoot;

while(p != NULL || !pNode.empty())
{
while(p != NULL)  //遍历左子树
{
VisitData(p); 
pNode.push(p);
p = p->lchild;
}

if(!pNode.empty())
{
p = pNode.top();
p = p->rchild;
pNode.pop();
}
}
}

//2.中序遍历（非递归）
void InOderTraverse1(BiTNode* pRoot)
{
std::stack<BiTNode*> pNode;
pNode.push(pRoot);   //根指针入栈
BiTNode* p = pRoot;

while(!pNode.empty()) 
{
while(pNode.top() != NULL && p != NULL)  //向左走到尽头，最后一个入栈的是一个NULL指针
{
p = p->lchild;
pNode.push(p);
}
pNode.pop();          //栈顶的空指针出栈

if(!pNode.empty())
{
p = pNode.top();  //栈顶元素
//PrintBiTNode(p);
VisitData(p);
p = p->rchild;    //右子
pNode.pop();      //出栈
pNode.push(p);    //右子入栈
}
}
}

void InOderTraverse2(BiTNode* pRoot)
{
std::stack<BiTNode*> pNode;
BiTNode* p = pRoot;

while(p != NULL || !pNode.empty())
{
if(p != NULL)
{
pNode.push(p); //入栈，直到左树的左边
p = p->lchild;
}
else
{
p = pNode.top();   //栈顶
VisitData(p);
pNode.pop();   //出栈
p = p->rchild;
}
}
}

void InOderTraverse3(BiTNode* pRoot)
{
std::stack<BiTNode*> pNode;
BiTNode* p = pRoot;

while(p != NULL || !pNode.empty())
{
while(p != NULL)    //遍历左子树
{
pNode.push(p);  //入栈，直到左树的左边
p = p->lchild;
}

if(!pNode.empty())
{
p = pNode.top();   //栈顶
VisitData(p);
pNode.pop();   //出栈
p = p->rchild;
}
}
}
//3.后续遍历（非递归）
void PostOderTraverse1(BiTNode* pRoot)
{
std::stack<BiTNode*> pNode;
BiTNode* p = pRoot, *q;
int flag;

do
{
while(p != NULL)    //遍历左子树
{
pNode.push(p); 
p = p->lchild;
}
q = NULL;
flag = 1;

while(!pNode.empty() && flag)
{
p = pNode.top();    //栈顶
if(p->rchild == q)
{
VisitData(p);
q = p;
pNode.pop();
}
else
{
p = p->rchild;  //遍历右子树
flag = 0;
}
}
}while(!pNode.empty());
}

void PostOderTraverse2(BiTNode* pRoot)
{
std::stack<BiTNode*> pNode;
BiTNode* p = pRoot, *q;
int flag;

do
{
while(p != NULL)    //遍历左子树
{
pNode.push(p); 
p = p->lchild;

}
q = NULL;
flag = 1;

while(!pNode.empty() && flag)
{
p = pNode.top();    //栈顶
if(p->rchild == q)
{
VisitData(p);
q = p;
pNode.pop();
}
else
break;
}

if(!pNode.empty())
{
flag = 0;
p = p->rchild;  //遍历右子树
}

}while(!pNode.empty());
}

//4.层次遍历(队列实现)
void BFSTraverse(BiTNode* pRoot)
{
if(pRoot == NULL)
return;

std::queue<BiTNode*> pNode;
pNode.push(pRoot);//根结点进队列

while(!pNode.empty())
{
BiTNode* pHead = pNode.front(); //队首元素
VisitData(pHead);
pNode.pop();   //首元素出队列
if(pHead->lchild != NULL)
pNode.push(pHead->lchild); //左孩子进队列
if(pHead->rchild != NULL)
pNode.push(pHead->rchild); //右孩子进队列
}
}


//销毁二叉树
void DestroyBiTree(BiTNode* pRoot)
{
if(pRoot == NULL)
return;

BiTNode* pLeft  = pRoot->lchild;
BiTNode* pRight = pRoot->rchild;

free(pRoot);
DestroyBiTree(pLeft);
DestroyBiTree(pRight);
}

/****************测试二叉树的基本操作******************/
void Test1()
{
//创建二叉树结点
BiTNode* pNode1 = CreateBiTNode(1);
BiTNode* pNode2 = CreateBiTNode(2);
BiTNode* pNode3 = CreateBiTNode(3);
BiTNode* pNode4 = CreateBiTNode(4);
BiTNode* pNode5 = CreateBiTNode(5);
BiTNode* pNode6 = CreateBiTNode(6);
BiTNode* pNode7 = CreateBiTNode(7);
BiTNode* pNode8 = CreateBiTNode(8);

//连接结点构成二叉树
ConnectBiTNode(pNode1,pNode2,pNode3);
ConnectBiTNode(pNode2,pNode4,NULL);
ConnectBiTNode(pNode3,pNode5,pNode6);
ConnectBiTNode(pNode4,NULL,pNode7);
ConnectBiTNode(pNode6,pNode8,NULL);

//输出二叉树
//先序遍历（递归）
//PreOderTraverse(pNode1);
//中序遍历（递归）
//InOderTraverse(pNode1);
//后序遍历（递归）
//PostOderTraverse(pNode1);

//先序遍历（非递归）
//PreOderTraverse1(pNode1);
//中序遍历（非递归）
//InOderTraverse1(pNode1);
//InOderTraverse2(pNode1);
//InOderTraverse3(pNode1);
//后序遍历（非递归）
//PostOderTraverse1(pNode1);
PostOderTraverse2(pNode1);

//层次遍历 
//BFSTraverse(pNode1);

//销毁二叉树
DestroyBiTree(pNode1);

}


int _tmain(int argc, _TCHAR* argv[])
{
Test1();
return 0;
}