二叉树基本操作

定义一棵二叉树：

typedef struct node { char data; struct node *lchild; struct node *rchild; }bitnode, *bitree;

二叉树建立：

void createtree (bitree &T){ char ch; scanf("%c",&ch); if(ch==' '){ T=NULL; } else{ T = new bitnode; T->data=ch; T->lchild=T->rchild=NULL; createtree(T->lchild); createtree(T->rchild); } }

二叉树的前序遍历：

void preprint (bitree &T){ if(T){ printf("%c ",T->data); preprint(T->lchild); preprint(T->rchild); } }

二叉树的中序遍历：

void midprint (bitree &T){ if(T){ midprint(T->lchild); printf("%c ",T->data); midprint(T->rchild); } }

二叉树后序遍历：

void endprint (bitree &T){ if(T){ endprint(T->lchild); endprint (T->rchild); printf("%c ",T->data); } }

二叉树层序遍历：

void levelprint (bitree &T){ bitree root=T; queue <bitree> que; if(root){ que.push(root); } while (!que.empty()){ bitree q=que.front(); que.pop(); printf("%c ",q->data); if(q->lchild){ que.push(q->lchild); } if(q->rchild){ que.push(q->rchild); } } }

完整代码：

#include <stdio.h> #include <queue> using namespace std; typedef struct node { char data; struct node *lchild; struct node *rchild; }bitnode, *bitree; void createtree (bitree &T){ char ch; scanf("%c",&ch); if(ch==' '){ T=NULL; } else{ T = new bitnode; T->data=ch; T->lchild=T->rchild=NULL; createtree(T->lchild); createtree(T->rchild); } } void preprint (bitree &T){ if(T){ printf("%c ",T->data); preprint(T->lchild); preprint(T->rchild); } } void midprint (bitree &T){ if(T){ midprint(T->lchild); printf("%c ",T->data); midprint(T->rchild); } } void endprint (bitree &T){ if(T){ endprint(T->lchild); endprint (T->rchild); printf("%c ",T->data); } } void levelprint (bitree &T){ bitree root=T; queue <bitree> que; if(root){ que.push(root); } while (!que.empty()){ bitree q=que.front(); que.pop(); printf("%c ",q->data); if(q->lchild){ que.push(q->lchild); } if(q->rchild){ que.push(q->rchild); } } } int main (){ bitree T; createtree(T); preprint(T); printf("\n"); midprint(T); printf("\n"); endprint(T); printf("\n"); levelprint(T); return 0; }

给一个水题吧。。。

以二叉链表作为二叉树的存储结构，求二叉树的叶子结点个数。

输入格式:

输入二叉树的先序序列。

提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:

输出有两行：

第一行是二叉树的中序遍历序列；

第二行是二叉树的叶子结点个数。

输入样例:

ABC##DE#G##F###

输出样例:

CBEGDFA

3

#include <iostream> #include <cstdio> using namespace std; typedef struct Node { char val ; Node *lchild, *rchild ; }bitnode, *bitree ; void BuildTree (bitree &T){ char ch ; scanf("%c",&ch); if (ch == '#'){ T = NULL; } else{ T = new bitnode; T-> val = ch ; T->lchild = T->rchild = NULL; BuildTree(T->lchild); BuildTree(T->rchild); } } void midprint(bitree &T){ if (T){ midprint(T->lchild); printf("%c",T->val); midprint(T->rchild); } } int F (bitree T){ // 求叶子节点的个数 if (T == NULL){ return 0; } if (T->lchild == NULL && T->rchild == NULL){ return 1; } return F(T->lchild) + F(T->rchild); } int main (){ bitree root; BuildTree(root); midprint(root); puts(""); printf("%d\n",F(root)); return 0; }

二叉树还是很简单的很简单？