二叉树的基本操作-建立-遍历-求深度等
二叉树的基本操作
1、按照前序次序建立一棵二叉树;
2、用前、中、后序递归遍历的方法遍历二叉树;
3、求二叉树的深度;
4、求二叉树的所有结点数;
掌握二叉树的链式存储结构的建立方法和对二叉树的各种操作算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<iostream> using namespace std; typedef struct node{ char data; struct node *left,*right; }BiNode,*BiTree; /*creat lianbiao*/ BiTree creatTree(){ BiTree t; char a; cin>>a; if(a == '@'){ return NULL; }else{ t = (BiTree)malloc(sizeof(BiNode)); t->data=a; t->left = creatTree(); t->right = creatTree(); return t; } } /*qian*/ void PreorderBT(BiTree t) { if(t) { cout<<t->data; PreorderBT(t->left); PreorderBT(t->right); } } /*zhong*/ void InorderBT(BiTree t) { if(t) { InorderBT(t->left); cout<<t->data; InorderBT(t->right); } } /*hou*/ void PoorderBT(BiTree t) { if(t) { PoorderBT(t->left); PoorderBT(t->right); cout<<t->data; } } /*count*/ int Count(BiTree t) { if(t==NULL) return -1; else if((t->left==NULL)&&(t->right==NULL)) return 0; else return Count(t->left)+Count(t->right)+2; } /*deep*/ int deep(BiTree t){ if(t==NULL) return 0; else if((t->left==NULL)&&(t->right==NULL)) return 1; else return Count(t->left)>Count(t->right)?Count(t->left):Count(t->right)+1; } int main(){ BiTree t; t=creatTree(); cout<<"Preorder"<<endl; PreorderBT(t); cout<<endl; cout<<"Inorder"<<endl; InorderBT(t); cout<<endl; cout<<"Poorder"<<endl; PoorderBT(t); cout<<endl; cout<<"count:"<<" "<<Count(t)+1<<endl; cout<<"count:"<<" "<<deep(t)+1<<endl; return 0; } |