代码实现二叉树
#include<stdlib.h> //二叉树的节点定义 typedef struct treenode { char ch; //数据域 struct treenode *lchild; //左孩子 struct treenode *rchild; //右孩子 }btnode,*pbtnode; //先序构造二叉树 void createbtree(pbtnode *root) { char ch; ch=getchar(); if(ch=='#') *root=null; else{ *root=(pbtnode)malloc(sizeof(btnode)); (*root)->ch=ch; (*root)->lchild=null; (*root)->rchild=null; createbtree(&(*root)->lchild); createbtree(&(*root)->rchild); } } //先序遍历二叉树 void preorder(pbtnode root) { if(root==null) return; printf("%-3c",root->ch); preorder(root->lchild); preorder(root->rchild); } //中序遍历二叉树 void inorder(pbtnode root) { if(root==null) return; preorder(root->lchild); printf("%-3c",root->ch); preorder(root->rchild); } //后序遍历二叉树 void postorder(pbtnode root) { if(root==null) return; preorder(root->lchild); preorder(root->rchild); printf("%-3c",root->ch); } //输出叶子结点 void displyleaf(pbtnode root) { if(root==null) return; if(root->lchild==null&&root->rchild==null) printf("%-3c",root->ch); else{ displyleaf(root->lchild); displyleaf(root->rchild); } } //左结点插入 void inseartleftnode(pbtnode root,char ch) { pbtnode p,newnode; if(root==null) return; p=root->lchild; newnode=(pbtnode)malloc(sizeof(btnode)); newnode->ch=ch; newnode->rchild=null; newnode->lchild=p; root->lchild=newnode; } //右结点插入 void inseartrightnode(pbtnode root,char ch) { pbtnode p,newnode; if(root==null) return; p=root->rchild; newnode=(pbtnode)malloc(sizeof(btnode)); newnode->ch=ch; newnode->lchild=null; newnode->rchild=p; root->rchild=newnode; } //销毁一颗二叉树 void clear(pbtnode* root) { pbtnode pl,pr; if(*root==null) return; pl=(*root)->lchild; pr=(*root)->rchild; (*root)->lchild=null; (*root)->rchild=null; free((*root)); *root=null; clear(&pl); clear(&pr); } //删除左子树 void deletelefttree(pbtnode root) { if(root==null) return; clear(&root->lchild); root->lchild=null; } //删除右子树 void deleterighttree(pbtnode root) { if(root==null) return; clear(&root->rchild); root->rchild=null; } //查找结点 pbtnode search(pbtnode root,char ch) { pbtnode p; if(root==null) return null; if(root->ch==ch) return root; else{ if((p=search(root->lchild,ch))!=null) return p; else return search(root->rchild,ch); } } //求二叉树的高度 int btreeheight(pbtnode root) { int lchildheight,rchildheight; if(root==null) return 0; lchildheight=btreeheight(root->lchild); rchildheight=btreeheight(root->rchild); return (lchildheight>rchildheight)?(1+lchildheight):(1+rchildheight); } //求叶子结点的个数 int countleaf(pbtnode root) { if(root==null) return 0; if(root->lchild==null&&root->rchild==null) return 1; else{ return countleaf(root->lchild)+countleaf(root->rchild); } } //求所有结点的个数 int countall(pbtnode root) { if(root==null) return 0; return countall(root->lchild)+countall(root->rchild)+1; } //复制二叉树 pbtnode copybtree(pbtnode root) { pbtnode p,lchild,rchild; if(root==null) return null; lchild=copybtree(root->lchild); rchild=copybtree(root->rchild); p=(pbtnode)malloc(sizeof(btnode)); p->ch=root->ch; p->lchild=lchild; p->rchild=rchild; return p; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607407.html