二叉树转换为双向链表，以及二叉树相关操作---纪念考研的时光

       自毕业以来再也没有认真的学习数据结构和算法，工作接近三年，感觉大学期间学习的算法和啥的对实践中的某些业务程序开发，没有实际的指导意义。

       大多数公司的程序员（牛逼的公司、牛逼的研发可能会有很大的不同，也许他们能感受算法和数据结构给人带来的成就感），完成简单业务系统开发，感觉更大的程度上是考虑程序的扩展性、接口的合理性等问题。

       今天，研究生考试，想起13年的考试，心中难免有些遗憾。想起了鸡哥、骚哥、鸡巴鹤、阳哲、傻瑶（你们即将毕业）。先预祝计科考研的学生们取得好的成绩，经历了是美好的。

       下面整理了二叉树的各类操作：

#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include<queue>

using namespace std;

typedef struct _BSTNode
{
int data;
struct _BSTNode *lchild; //*pre
struct _BSTNode *rchild; //*next
}BSTNode;

BSTNode *head = NULL;
BSTNode *index = NULL;

static int InsertBSTNode(BSTNode *&node, int data)
{
BSTNode *tmp = NULL;

if(NULL == node)
{
tmp = (BSTNode *)malloc(sizeof(BSTNode));
if(NULL == tmp)
{
printf("Malloc Error\n");
return 0;
}
tmp->data = data;
tmp->lchild = tmp->rchild = NULL;
node = tmp;
return 1;
}
 //create left or right node
if(node->data > data)
{
InsertBSTNode(node->lchild, data);
}
else
{
InsertBSTNode(node->rchild, data);
}
return 1;
}

//中序遍历 递归算法
void InOrder(BSTNode *node)
{
if(node !=  NULL)
{
InOrder(node->lchild);
printf("%d\n", node->data);
InOrder(node->rchild);
}
}

//中序遍历 非递归算法
void InOrder1(BSTNode *node)
{
BSTNode *p = node;
std::stack<BSTNode *> s;

while(p || !s.empty())
{
if(p != NULL)
{
s.push(p);
p = p->lchild;
}
else
{
p = s.top();
printf("%d\n", p->data);
s.pop();
p = p->rchild;
}
}
}

//前序遍历 递归算法
void PreOrder(BSTNode *node)
{
if(node !=  NULL)
{
printf("%d\n", node->data);
InOrder(node->lchild);
InOrder(node->rchild);
}
}


//前序遍历 非递归算法
void PreOrder1(BSTNode *node)
{
BSTNode *p = node;
std::stack<BSTNode *> s;

while(p || !s.empty())
{
if(p != NULL)
{
printf("%d\n", p->data);
s.push(p);
p = p->lchild;
}
else
{
p = s.top();
s.pop();
p = p->rchild;
}
}
}

//后序遍历 递归算法
void PostOrder(BSTNode *node)
{
if(node !=  NULL)
{
InOrder(node->lchild);
InOrder(node->rchild);
printf("%d\n", node->data);
}
}

//后序遍历 非递归算法
void PostOrder1(BSTNode *node)
{
BSTNode *pre = NULL;
BSTNode *p = node;
std::stack<BSTNode *> s;

while(p || !s.empty())
{
while(p != NULL)
{
s.push(p);
p = p->lchild;
}
p = s.top();
if(p->rchild == NULL || p->rchild == pre)
{
printf("%d\n", p->data);
pre = p;
p = NULL;
s.pop();
}
else
{
p = p->rchild;
}
}
}

void ConvertToDoubleList(BSTNode *node)
{
node->lchild = index;
if(NULL == index)
{
head = node;
}
else
{
index->rchild = node; 
}
index = node;
printf("%d\n", node->data);
}

void InOrderConvert(BSTNode *node)
{
if(node ==  NULL)
{
return;
}
if(NULL != node->lchild)
InOrderConvert(node->lchild);

//printf("%d\n", node->data);
ConvertToDoubleList(node);

if(NULL != node->rchild)
InOrderConvert(node->rchild);


}

//层序遍历
void LevelOrder(BSTNode *node)  
{  
std::queue<BSTNode *> Q;
    if(!node)
{
        return;
}
    Q.push(node);  
    BSTNode *temp=NULL;  
    while(!Q.empty())  
    {  
        temp=Q.front();  
        printf("%d\n", temp->data);
        Q.pop();  
        if(temp->lchild) 
{ 
            Q.push(temp->lchild);  
}
        if(temp->rchild) 
{ 
            Q.push(temp->rchild);  
}
    }  
}  

void Display()
{
BSTNode *tmp = NULL;
if(NULL == head)
{
printf("Not Create Double Link\n");
return;
}
tmp = head;
putchar('\n');
while(tmp)
{
printf("%d", tmp->data);
tmp = tmp->rchild;
}
putchar('\n');
}

int main()
{
BSTNode *root = NULL;
//create BST 
InsertBSTNode(root, 4);
InsertBSTNode(root, 9);
InsertBSTNode(root, 0);
InsertBSTNode(root, 1);
InsertBSTNode(root, 8);
InsertBSTNode(root, 6);
InsertBSTNode(root, 3);
InsertBSTNode(root, 5);
InsertBSTNode(root, 2);
InsertBSTNode(root, 7);
/*
//中序遍历二叉排序树
InOrder(root);
putchar('\n');
//先序遍历二叉排序树
PreOrder(root);
putchar('\n');
//后序遍历二叉排序树
PostOrder(root);
*/
/*
InOrderConvert(root);
//遍历双向链表
Display();
*/
//InOrder1(root);
//PreOrder1(root);
//PostOrder1(root);
LevelOrder(root);
return 0;
}