#include <iostream>
#include <windows.h>
usingnamespacestd;
typedefstructBiTNode {
chardata;
structBiTNode*lchild, *rchild;
}BiTNode, *BiTree;
// 先序次序输入二叉树中结点的值，创建二叉链表表示的二叉树
voidcreateTree(BiTree&T) {
charch;
cin>>ch;
if (ch=='#') {
// 递归结束，创建空树
T=NULL;
} else {
T=newBiTNode; // 生成根结点
T->data=ch;
createTree(T->lchild); // 生成左子树
createTree(T->rchild); // 生成右子树
}
}
// 先序遍历 NLR
voidpreOrderTraverse(BiTreeT) {
if (T) {
cout<<T->data; // 访问根结点
preOrderTraverse(T->lchild); // 先序遍历左子树
preOrderTraverse(T->rchild); // 先序遍历右子树
}
}
// 中序遍历 LNR
voidinOrderTraverse(BiTreeT) {
if (T) {
inOrderTraverse(T->lchild); // 中序遍历左子树
cout<<T->data; // 访问根结点
inOrderTraverse(T->rchild); // 中序遍历右子树
}
}
// 后序遍历 LRN
voidpostOrderTravese(BiTreeT) {
if (T) {
postOrderTravese(T->lchild); // 后序遍历左子树
postOrderTravese(T->rchild); // 后序遍历右子树
cout<<T->data; // 访问根结点
}
}
// 二叉树的深度
intdepth(BiTreeT) {
if (T==NULL) {
return0;
} else {
intl=depth(T->lchild); // 左子树的深度
intr=depth(T->rchild); // 右子树的深度
returnl<r? (r+1) : (l+1);
}
}
// 二叉树的结点数
intnodeCount(BiTreeT) {
if (T==NULL) {
return0;
} else {
returnnodeCount(T->lchild) +nodeCount(T->rchild) +1; // 左子树结点树 + 右子树结点树 + 1（根结点）
}
}
intmain() {
BiTreeT;
createTree(T);
cout<<"前序遍历："<<endl;
preOrderTraverse(T);
cout<<endl;
cout<<"中序遍历："<<endl;
inOrderTraverse(T);
cout<<endl;
cout<<"后序遍历："<<endl;
postOrderTravese(T);
cout<<endl;
cout<<"二叉树的深度："<<depth(T) <<endl;
cout<<"二叉树的结点个数："<<nodeCount(T) <<endl;
system("pause");
return0;
}
