链式存储二叉树基本操作函数.rar

#include<stdio.h> #include<iostream> using namespace std; #define MAX 100 typedef char Elemtype; typedef struct tNode { Elemtype data; struct tNode *lchild, *rchild; }BiTNode, *BiTree; BiTNode *createtree() { BiTNode *T; char str; str = getchar(); if (str == '#') return NULL; else { T = (BiTNode*)malloc(sizeof(BiTNode)); T->data = str; T->lchild = createtree(); T->rchild = createtree(); return T; } } void preorder(BiTNode *bt) { if (bt == NULL) return; cout << bt->data << " "; preorder(bt->lchild); preorder(bt->rchild); } void inorder(BiTNode *bt) { if (bt == NULL) return; inorder(bt->lchild); cout << bt->data << " "; inorder(bt->rchild); } void postorder(BiTree bt) { if (bt == NULL) return; postorder(bt->lchild); postorder(bt->rchild); cout << bt->data << " "; } void levelorder(BiTNode *bt) { BiTNode *p; BiTNode *q[MAX]; int front, rear; front = rear = 0; //置队空 rear++; q[rear] = bt; //根节点指针入队 while (front != rear) { front = (front + 1) % MAX; p = q[front]; //出队结点p cout << p->data << " "; if (p->lchild != NULL) // 有左孩子时入队 { rear = (rear + 1) % MAX; q[rear] = p->lchild; } if (p->rchild != NULL) //有右孩子时进队 { rear = (rear + 1) % MAX; q[rear] = p->rchild; } } } BiTree search(BiTNode *bt, Elemtype x) { BiTree p; p = bt; if (p->data == x) return p; if (p->lchild != NULL) return(search(p->lchild, x)); if (p->rchild != NULL) return(search(p->rchild, x)); return NULL; } int countall(BiTNode *bt) { int l, r; if (bt == NULL) return(0); l = countall(bt->lchild); r = countall(bt->rchild); return(l + r + 1); } int countleaf(BiTNode *bt) { if (bt == NULL) return(0); else if (bt->lchild == NULL && bt->lchild == NULL) return(1); else return(countleaf(bt->lchild) + countleaf(bt->rchild)); } int treehigh(BiTNode *bt) { int rh, lh, h; if (bt == NULL) h = 0; else { lh = treehigh(bt->lchild); rh = treehigh(bt->rchild); h = (lh > rh ? lh : rh) + 1; } return h; } void main() { //AB#D##CE##F## cout << "创建二叉树" << endl; cout << "请以先序输入节点的值，为空时输入'#'：" << endl; BiTNode *bt = createtree(); while (1) { cout << "请选择要进行的操作：" << endl; cout << "-------------------------------------" << endl; cout << "1.二叉树的前序遍历" << endl; cout << "2.二叉树的中序遍历" << endl; cout << "3.二叉树的后序遍历" << endl; cout << "4.二叉树的层次遍历" << endl; cout << "5.求二叉树的叶子节点及节点数" << endl; cout << "6.二叉树的查找" << endl; cout << "7.求二叉树的深度" << endl; int index; cin >> index; switch (index) { case 1: preorder(bt); cout << endl; break; case 2: inorder(bt); cout << endl; break; case 3: postorder(bt); cout << endl; break; case 4: levelorder(bt); cout << endl; break; case 5: cout << "叶子结点数目为：" << countleaf(bt) << " 结点数目为：" << countall(bt) << endl; break; case 6: { Elemtype x; cout << "请输入要查找的元素值："; cin >> x; if (search(bt, x) == NULL) cout << "查无此数"; cout << "该二叉树中已查到数：" << x << endl; break; } case 7: cout << "二叉树深度为：" << treehigh(bt) << endl; break; } } system("pause"); }