#include <iostream>
using namespace std;
// 二叉链表
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
BiTNode()
{
lchild = NULL;
rchild = NULL;
}
} BiTNode;
// 初始化二叉链表
void InitBiTree(BiTNode *&T)
{
T = NULL;
}
// 先序遍历
void PreOrderTraverse(BiTNode *T)
{
if (!T)
{
return;
}
cout << T->data << " ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
// 中序遍历
void InOrderTraverse(BiTNode *T)
{
if (!T)
{
return;
}
InOrderTraverse(T->lchild);
cout << T->data << " ";
InOrderTraverse(T->rchild);
}
// 后序遍历
void PostOrderTraverse(BiTNode *T)
{
if (!T)
{
return;
}
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data << " ";
}
// 求树的高度(深度)
int Height(BiTNode *T)
{
if (!T)
{
return 0;
}
int lh = Height(T->lchild);
int rh = Height(T->rchild);
return (lh > rh) ? (lh + 1) : (rh + 1);
}
// 层序遍历
#include <queue>
void LevelOrderTraverse(BiTNode *T)
{
if (!T)
{
return;
}
queue<BiTNode *> q;
// 根入队
q.push(T);
while (!q.empty())
{
// 获取当前队首
BiTNode *p = q.front();
cout << p->data << " ";
// 队首离开
q.pop();
if (p->lchild)
{
q.push(p->lchild);
}
if (p->rchild)
{
q.push(p->rchild);
}
}
}
int main()
{
BiTNode *root = new BiTNode;
root->data = 1;
BiTNode *lchild = new BiTNode;
lchild->data = 2;
BiTNode *rchild = new BiTNode;
rchild->data = 3;
root->lchild = lchild;
root->rchild = rchild;
BiTNode *lchild2 = new BiTNode;
lchild2->data = 4;
BiTNode *rchild2 = new BiTNode;
rchild2->data = 5;
lchild->lchild = lchild2;
lchild->rchild = rchild2;
PreOrderTraverse(root);
cout << endl;
LevelOrderTraverse(root);
cout << endl;
cout << Height(root) << endl;
return 0;
}