1.前序遍历
2.中序遍历
3.后序遍历
4.层次遍历（层次遍历的时候需要用到队列）
这里解释一下层次遍历：先把root节点压入队列，然后判断队列是否为空，非空，输出队首节点（root），压入root的左节点A，再压入root的右节点B，再判断，再输出输出队首节点（A），再压入A的左节点C，再压入A的右节点Ｄ，以此循环，直到队空。
上代码（Ｃ＋＋版）：
/*
*二叉树
*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//宏定义
#define YES 1
#define NO 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
typedef int ElemType;
//树节点
typedef struct Node
{
ElemType data;
struct Node * lchild;
struct Node * rchild;
}Node,*BinTree;
//定义队列节点结构体
typedef struct LNode
{
BinTree data;
struct LNode* next;
}LNode,*LinkList;
//定义队列结构体
//用于树的层次遍历
typedef struct Queue
{
LinkList front;
LinkList rear;
}Queue;
Status initQueue(Queue &queue)
{
queue.front = (LinkList)malloc(sizeof(LNode)); //这是在堆中分配地址，后面需要释放
if(queue.front == NULL)
{
exit(ERROR);
}
queue.rear = queue.front; //单独写这一行也可以
//是在静态区分配内存的，所以不需要手动释放。
return OK;
}
Status queueIsEmpty(Queue queue)
{
if(queue.front->next == queue.rear->next)
{
return YES;
}else{
return NO;
}
}
Status enQueue(Queue &queue,Node* ele)
{
LinkList list;
list = (LinkList)malloc(sizeof(LinkList));
if(!list)
{
exit(ERROR);
}
list->data = ele;
list->next = NULL;
if(queue.front->next == NULL)
{
queue.front->next = list;
}
queue.rear->next = list;
queue.rear = queue.rear->next;
return OK;
}
Status deQueue(Queue &queue,Node* &ele)
{
LinkList list;
if(queueIsEmpty(queue) == YES)
{
cout << "队列为空" << endl;
return ERROR;
}
ele = queue.front->next->data;
list = queue.front->next;
queue.front->next = list->next;
free(list);
return OK;
}
//创建树
Status createBinTree(BinTree &binTree)
{
int temp;
cin >> temp;
if(temp == 0 )
{
binTree = NULL;
}else{
binTree = (BinTree)malloc(sizeof(Node));
if(!binTree)
{
exit(OVERFLOW);
}
binTree->data = temp;
createBinTree(binTree->lchild);
createBinTree(binTree->rchild);
}
return OK;
}
//前序遍历
Status preOrder(BinTree binTree)
{
if(!binTree)
{
return ERROR;
}
cout << binTree->data << " ";
preOrder(binTree->lchild);
preOrder(binTree->rchild);
return OK;
}
//中序遍历
Status inOrder(BinTree binTree)
{
if(!binTree)
{
return ERROR;
}
inOrder(binTree->lchild);
cout << binTree->data << " ";
inOrder(binTree->rchild);
return OK;
}
//后序遍历
Status postOrder(BinTree binTree)
{
if(!binTree)
{
return ERROR;
}
postOrder(binTree->lchild);
postOrder(binTree->rchild);
cout << binTree->data << " ";
return OK;
}
//层次遍历
Status levelOrder(BinTree binTree)
{
Queue queue;
Node* temp;
initQueue(queue);
enQueue(queue,binTree);
while(queueIsEmpty(queue) != YES)
{
deQueue(queue,temp);
cout << temp->data << " ";
if(temp->lchild != 0)
{
enQueue(queue,temp->lchild);
}
if(temp->rchild != 0)
{
enQueue(queue,temp->rchild);
}
}
return OK;
}
//叶子节点个数
int getLeafNum(BinTree binTree)
{
if (binTree == 0)
{
return 0;
}else if(binTree->lchild == 0 && binTree->rchild == 0)
{
return 1;
}else{
int lchildNum = getLeafNum(binTree->lchild);
int rchildNum = getLeafNum(binTree->rchild);
return lchildNum + rchildNum;
}
}
//树深度
int getTreeHeight(BinTree binTree)
{
int height = 1;
if(binTree != 0)
{
int lchildHeight = getTreeHeight(binTree->lchild);
int rchildHeight = getTreeHeight(binTree->rchild);
if(lchildHeight > rchildHeight)
{
height = lchildHeight + 1;
}else{
height = rchildHeight + 1;
}
}else{
height = 0;
}
return height;
}
int main(int argc, char const *argv[])
{
BinTree binTree;
createBinTree(binTree);
cout << "先序遍历：";
preOrder(binTree); //先序遍历
cout << endl;
cout << "中序遍历：";
inOrder(binTree); //中序遍历
cout << endl;
cout << "后序遍历：";
postOrder(binTree); //后序遍历
cout << endl;
cout << "层次遍历：";
levelOrder(binTree); //层次遍历
cout << endl;
int binTreeHeight;
binTreeHeight = getTreeHeight(binTree);
cout << "树深度：" << binTreeHeight << endl;
int leafNUm;
leafNUm = getLeafNum(binTree);
cout << "叶节点："<< leafNUm << endl;
return 0;
}
//结果：
//3 4 2 0 0 1 0 0 5 6 0 0 7 0 0
//先序遍历：3 4 2 1 5 6 7
//中序遍历：2 4 1 3 6 5 7
//后序遍历：2 1 4 6 7 5 3
//层次遍历：3 4 5 2 1 6 7