#include <stdio.h> #include <string.h> #include <malloc.h> #include <iostream> #include <stack> using namespace std; #define NULL 0 typedef struct BiTNode //定义数据结构 { char data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode,*BiTree; BiTree create(BiTree T) //建立二叉树 { char ch; ch = getchar(); if (ch==' ') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) printf("Error!"); T->data = ch; T->lchild = create(T->lchild); T->rchild = create(T->rchild); } return T; } void preorder(BiTree T) { //先序遍历二叉树 if (T) { printf("%c",T->data); preorder(T->lchild); preorder(T->rchild); } } void midview(BiTree T) //非递归中序遍历 { stack<BiTree> Stack; if (!T) { printf("empty tree\n"); return; } while (T||!Stack.empty()) { while (T) { Stack.push(T); T = T->lchild; } T = Stack.top(); Stack.pop(); printf("%c",T->data); T = T->rchild; } } void lastview(BiTree T) //后续遍历 { if (T) { lastview(T->lchild); lastview(T->rchild); printf("%c",T->data); } } int sumleaf(BiTree T) { //求叶子节点的个数 int sum = 0,m,n; if (T) { if ((!T->lchild)&&(!T->rchild)) sum++; m = sumleaf(T->lchild); sum = sum + m; //左子树的叶子节点数目m n = sumleaf(T->rchild); sum = sum + n; //右子树的叶子节点数目n } return sum; } int sumdutwo(BiTree T) { //求度为2节点的个数 int sum2 = 0,a,b; if (T) { if ((T->lchild)&&(T->rchild)) sum2++; a = sumdutwo(T->lchild); sum2 = sum2 + a; b = sumdutwo(T->rchild); sum2 = sum2 + b; } return sum2; } int depth(BiTree T) //求二叉树的深度 { int dep = 0,depl,depr; if (!T) dep = 0; else { depl = depth(T->lchild); depr = depth(T->rchild); dep = 1 + (depl>depr?depl:depr); } return dep; } int main() { BiTree T; int sum,sum2,dep; T = create(T); printf("二叉树建立成功!\n"); printf("先序遍历\n"); preorder(T); printf("\n"); printf("中序遍历\n"); midview(T); printf("\n"); printf("后序遍历\n"); lastview(T); printf("\n"); printf("叶子节点数目\n"); sum = sumleaf(T); printf("%d\n",sum); printf("度为2的节点数目\n"); sum2 = sumdutwo(T); printf("%d\n",sum2); printf("树的深度\n"); dep = depth(T); printf("%d\n",dep); return 0; }