数据结构--二叉树的创建、先序遍历、中序遍历、后序遍历、深度、叶子结点数

时间:2023-02-23 17:03:06

*用cin来读取char类型时,没法读入“ ”(space),所以要改用getchar()(在头文件

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
typedef struct BiTNode {
char date;
struct BiTNode *lchild, *rchild;
}BiNode, *BiTree;
int CreateBiTree(BiTree &T) {
char date;
date = getchar();
if (date == ' ')
T = NULL;
else {
T = (BiTree)malloc(sizeof(BiNode));
T->date = date;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}

return 0;
}
void Visit(BiTree &T) {
if (T->date != ' ')
cout << T->date;
}
void PreOrder(BiTree T) {
if (T) {
Visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T) {
if (T) {
InOrder(T->lchild);
Visit(T);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T) {
if (T) {
PostOrder(T->lchild);
PostOrder(T->rchild);
Visit(T);
}
}
int BiTreeDepth(BiTree &T) {
int leftdepth = 0;
int rightdepth = 0;
if (T) {
cout << "left1___:" << leftdepth << endl;
leftdepth = BiTreeDepth(T->lchild);
cout << "left2___:" << leftdepth << endl;
cout << "right1___:" << rightdepth << endl;
rightdepth = BiTreeDepth(T->rchild);
cout << "right2___:" << rightdepth << endl;
return leftdepth > rightdepth ? (leftdepth + 1) : (rightdepth + 1);
}
return leftdepth > rightdepth ? leftdepth : rightdepth;
}
int Countleaf(BiTNode *T, int &count)
{
if (T) {
if (!T->lchild && !T->rchild)
count++;
Countleaf(T->lchild, count);
Countleaf(T->rchild, count);
}
return 1;
}
int main() {
BiTree T;
cout << "input the BiTree:" << endl;
CreateBiTree(T);
cout << "The PreOrder of BiTree :" << endl;
PreOrder(T);
cout << endl;
cout << "The InOrder of BiTree :" << endl;
InOrder(T);
cout << endl;
cout << "The PostOrder of BiTree :" << endl;
PostOrder(T);
cout << endl;
cout << "The BiTree's depth is :" << endl;
int x;
x = BiTreeDepth(T);
cout << x << endl;
cout << "The BiTree's leafcount :" << endl;
int count = 0;
Countleaf(T, count);
cout << count << endl;

}