好贷网好贷款

数据结构——链式二叉树

发布时间:2016-12-3 17:45:05 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数据结构——链式二叉树",主要涉及到数据结构——链式二叉树方面的内容,对于数据结构——链式二叉树感兴趣的同学可以参考一下。

#include <iostream> using namespace std; typedef struct treenode { struct treenode *left; char data; struct treenode *right; }Treenode,* Treep; //初始化二叉树 void init_tree(Treep &root) { root=NULL; cout<<"初始化成功!"<<endl; } //创建二叉树 void creat_tree(Treep &rt) { char ch; ch=getchar(); if('#'==ch) rt=NULL; else { rt=(Treep )malloc(sizeof(Treenode)); rt->data=ch; creat_tree(rt->left); //构造左子树 creat_tree(rt->right); //构造右子树 } } //前序遍历二叉树 void pre_order(Treep &rt) { if(rt!=NULL) { cout<<rt->data<<" "; pre_order(rt->left); pre_order(rt->right); } } //中序遍历二叉树 void mid_order(Treep &rt) { if(rt!=NULL) { mid_order(rt->left); cout<<rt->data<<" "; mid_order(rt->right); } } //后序遍历二叉树 void back_order(Treep &rt) { if(rt!=NULL) { back_order(rt->left); back_order(rt->right); cout<<rt->data<<" "; } } //层序遍历 void leve_lorder(Treep &rt) { Treep q[100]; //指针数组,存放每个节点的地址 q[0]=rt; int front=0,rear=1; while(front<rear) { if(q[front]) { cout<<q[front]->data<<" "; if(q[front]->left) q[rear++]=q[front]->left; if(q[front]->right) q[rear++]=q[front]->right; front++; } } } //求二叉树的深度 int depth_tree(Treep &rt) { int depth1=0,depth2=0; if(NULL==rt) return 0; else { depth1=depth_tree(rt->left); depth2=depth_tree(rt->right); return (depth1>depth2) ? (depth1+1) : (depth2+1); } } //求二叉树的节点个数 int leaf_tree(Treep &rt) { if(rt) { if(rt->left==NULL && rt->right==NULL) { return 1; } return ( leaf_tree(rt->left) + leaf_tree(rt->right) + 1 ); } else { return 0; } } //查找二叉树中是否存在某元素 int seach_tree(Treep &rt,char key) { if(rt==NULL) return 0; else { if(rt->data==key) { return 1; } else { if(seach_tree(rt->left,key) || seach_tree(rt->right,key)) return 1; //如果左右子树有一个搜索到,就返回1 else return 0; //如果左右子树都没有搜索到,返回0 } } } //销毁二叉树 int destroy_tree(Treep &root) { if(root==NULL) { return 0; } else { if(root->left) destroy_tree(root->left); if(root->right) destroy_tree(root->right); free(root); root=NULL; //释放内存后的指针要指向NULL return 1; } } //更改某节点的值 void assign_tree(Treep &rt,char c,char value) { if(rt!=NULL) { if(c==rt->data) rt->data=value; assign_tree(rt->left,c,value); assign_tree(rt->right,c,value); } } //求双亲 void parent_tree(Treep &rt,char value) { if(rt!=NULL) { if(value==rt->data) { cout<<"此节点是根节点!"<<endl; } if( (rt->left!=NULL && rt->left->data==value ) || (rt->right!=NULL && rt->right->data==value) ) cout<<rt->data<<endl; else { parent_tree(rt->left,value); parent_tree(rt->right,value); } } } //求左孩子 void leftchild_tree(Treep &rt ,char value ) { if(rt!=NULL) { if(value==rt->data) { if(rt->left) cout<<rt->left->data<<endl; else cout<<"左孩子为空!"<<endl; } else { leftchild_tree(rt->left ,value ); leftchild_tree(rt->right ,value ); } } } //求右孩子 void rightchild_tree(Treep &rt ,char value ) { if(rt!=NULL) { if(value==rt->data) { if(rt->right) cout<<rt->right->data<<endl; else cout<<"右孩子为空!"<<endl; } else { rightchild_tree(rt->left ,value ); rightchild_tree(rt->right ,value ); } } } //求左兄弟 void leftbrother_tree(Treep &rt ,char value ) { if(rt!=NULL) { if(value==rt->data) { cout<<"此节点是根节点!"<<endl; } if(rt->left!=NULL && value==rt->left->data) { cout<<"此节点就是左孩子!"<<endl; } else if(rt->left!=NULL && value==rt->right->data) { if(rt->left) cout<<rt->left->data<<endl; else cout<<"左兄弟为空!"<<endl; } else { leftbrother_tree(rt->left ,value ); leftbrother_tree(rt->right ,value ); } } } //求右兄弟 void rightbrother_tree(Treep &rt ,char value ) { if(rt!=NULL) { if(value==rt->data) { cout<<"此节点是根节点!"<<endl; } if(rt->right!=NULL && value==rt->right->data) { cout<<"此节点就是右孩子!"<<endl; } else if(rt->left!=NULL && value==rt->left->data) { if(rt->right) cout<<rt->right->data<<endl; else cout<<"左兄弟为空!"<<endl; } else { rightbrother_tree(rt->left ,value ); rightbrother_tree(rt->right ,value ); } } } //删除子树 void delete_tree(Treep &rt,char ch,int bl) { if(rt!=NULL) { if(ch==rt->data) { if(!bl) rt->left=NULL; else rt->right=NULL; } else { delete_tree(rt->left, ch, bl); delete_tree(rt->right, ch, bl); } } } //插入子树 void insert_tree(Treep &rt1,char ch,int bl,Treep &rt2) { if(rt1!=NULL) { if(ch==rt1->data) { if(!bl) { if( NULL==rt1->left) { rt1->left=rt2; } else { cout<<ch<<"的左节点非空!"<<endl; } } else { if(NULL==rt1->right) { rt1->right=rt2; } else { cout<<ch<<"的右节点非空!"<<endl; } } } else { insert_tree(rt1->left, ch, bl,rt2); insert_tree(rt1->right, ch, bl,rt2); } } } int main() { Treep root; init_tree(root); //初始化树 cout<<"请输入二叉树,空值以#代表,输完要以Ctrl+Z表示结束,否则影响下个树的创建!:"<<endl; creat_tree(root); //创建二叉树 //前序遍历二叉树 cout<<"前序遍历序列是:"<<endl; pre_order(root); cout<<endl; //中序遍历二叉树 //cout<<"中序遍历序列是:"<<endl; //mid_order(root); //cout<<endl; //后序遍历二叉树 //cout<<"后序遍历序列是:"<<endl; //back_order(root); //cout<<endl; //层序遍历二叉树 //cout<<"层序遍历序列是:"<<endl; //leve_lorder(root); //cout<<endl; //求二叉树的深度 //cout<<"二叉树的深度:"<<endl; //cout<<depth_tree(root); //cout<<endl; //查找二叉树中是否存在某元素 /* cout<<"输入要查找的元素!"<<endl; char ch; cin>>ch; if(seach_tree(root,ch)==1) cout<<"yes!"<<endl; else cout<<"no!"<<endl; */ //更改节点的值 /* cout<<"输入你要改变的值和要改成的值:"<<endl; char ch,value; cin>>ch>>value; assign_tree(root,ch,value); pre_order(root); cout<<endl; */ //求双亲 //cout<<"你要找谁的双亲:"<<endl; //char value; //cin>>value; //parent_tree(root ,value ); //求左孩子 //cout<<"你要找谁的左孩子:"<<endl; //char value; //cin>>value; //leftchild_tree(root ,value ); //求右孩子 //cout<<"你要找谁的右孩子:"<<endl; //char value; //cin>>value; //rightchild_tree(root ,value ); //求左兄弟 //cout<<"你要找谁的左兄弟:"<<endl; //char value; //cin>>value; //leftbrother_tree(root ,value ); //求右兄弟 //cout<<"你要找谁的右兄弟:"<<endl; //char value; //cin>>value; //rightbrother_tree(root ,value ); //cout<<"你要删除谁的子树:"<<endl; //char value; //cin>>value; //delete_tree(root, value, 1); //pre_order(root); //cout<<endl; //Treep root2; //init_tree(root2); //初始化树 //cout<<"请输入二叉树,空值以#代表:"<<endl; //creat_tree(root2); //创建二叉树 //cout<<"前序遍历序列是:"<<endl; //pre_order(root2); //cout<<endl; //cout<<"你要插入谁的子树:"<<endl; //char value; //cin>>value; //insert_tree(root,value,1,root2); //pre_order(root); //cout<<endl; //求叶子结点个数 cout<<"结点个数:"<<endl; cout<<leaf_tree(root)<<endl; cout<<"销毁二叉树:"<<endl; if(destroy_tree(root)) cout<<"销毁成功!"<<endl; else cout<<"空树,销毁不成功!"<<endl; return 0; }

上一篇:Bootloader概述
下一篇:英特尔重新定义电视 必须跨越哪些障碍?

相关文章

相关评论