二叉树的链式存储
实现二叉树的基本操作：建立、遍历、计算深度、结点数、叶子数等。
输入C，先序创建二叉树，#表示空节点；
输入H：计算二叉树的高度；
输入L：计算二叉树的叶子个数；
输入N：计算二叉树节点总个数；
输入1：先序遍历二叉树；
输入2：中序遍历二叉树；
输入3：后续遍历二叉树；
输入F：查找值=x的节点的个数；
输入P：以缩格文本形式输出所有节点。
很简单就不需要多解释了，代码贴上
#include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; /*二叉树的链式存储表示*/ typedef char DataType; /*应由用户定义DataType的实际类型*/ typedef struct node { DataType data; node *lchild, *rchild; /*左右孩子指针*/ } BinTNode; /*结点类型*/ typedef BinTNode *BinTree; int sum=0; void DisplayBinTree(BinTree T); /*用格文本形式表示二叉树*/ void CreateBinTree(BinTree *T); /*构造二叉链表*/ void Preorder(BinTree T); /*前序遍历二叉树*/ void Inorder(BinTree T); /*中序遍历二叉树*/ void Postorder(BinTree T); /*后序遍历二叉树*/ int nodes(BinTree T); /*计算总结点数*/ int leafs(BinTree T); /*计算总叶子数*/ int hight(BinTree T); /*计算二叉树的高度*/ int find(BinTree T,char x); //查找值=x的节点的个数； int main() { BinTree T; char flg; while(cin>>flg) switch(flg) { case'C': getchar(); CreateBinTree(&T); cout<<"Created success!"<<endl; break; case'H': cout<<"Height="<<hight(T)<<"."<<endl; break; case'L': cout<<"Leaf="<<leafs(T)<<"."<<endl; break; case'N': cout<<"Nodes="<<nodes(T)<<"."<<endl; break; case'1': printf("Preorder is:"); Preorder(T); cout<<"."<<endl; break; case'2': printf("Inorder is:"); Inorder(T); cout<<"."<<endl; break; case'3': printf("Postorder is:"); Postorder(T); cout<<"."<<endl; break; case'F': char x; int ko; getchar(); cin>>x; ko=find(T,x); cout<<"The count of "<<x<<" is "<<ko<<"."<<endl; break; case'P': cout<<"The tree is:"<<endl; DisplayBinTree(T); break; default: cout<<"输入有误，请重新输入"<<endl; } } /*构造二叉链表*/ void CreateBinTree(BinTree *T) { char ch; if ((ch=getchar())=='#') *T=NULL; else { /*读入非空格*/ *T=(BinTNode *)malloc(sizeof(BinTNode));/*生成结点*/ (*T)->data=ch; CreateBinTree(&(*T)->lchild ); /*构造左子树*/ CreateBinTree(&(*T)->rchild ); /*构造右子树*/ } } /*用缩格文本形式表示二叉树*/ void DisplayBinTree(BinTree T) { BinTree stack[100],p; int level[100],top,n,i; if (T) { top=1; stack[top]=T; level[top]=0; while(top>0) { p=stack[top]; n=level[top]; for (i=1; i<=n; i++) cout<<" "; printf("%cn",p->data); top--; if (p->rchild!=NULL) { top++; stack[top]=p->rchild; level[top]=n+2; } if (p->lchild!=NULL) { top++; stack[top]=p->lchild; level[top]=n+2; } } } } /*计算总结点数*/ int nodes(BinTree T) { if(T) { if( (T->lchild==NULL)&&(T->rchild==NULL)) return 1; else return nodes(T->lchild)+nodes(T->rchild)+1; } return 0; } /*计算总叶子数*/ int leafs(BinTree T) { if(T) { if ((T->lchild==NULL)&&(T->rchild==NULL)) return 1; else return leafs(T->lchild)+leafs(T->rchild); } return 0; } /*计算树的高度*/ int hight(BinTree T) { if(T) { if ((T->lchild==NULL)&&(T->rchild==NULL)) return 1; else if((T->lchild==NULL)&&(T->rchild)) return 1+hight(T->rchild); else if((T->lchild)&&(T->rchild==NULL)) return 1+hight(T->lchild); else return hight(T->lchild)+hight(T->rchild); } return 0; } /*前序遍历二叉树*/ void Preorder(BinTree T) { if(T) { printf("%c ",T->data); /*访问结点*/ Preorder(T->lchild); Preorder(T->rchild); } } /*中序遍历二叉树*/ void Inorder(BinTree T) { if(T) { Inorder(T->lchild); printf("%C ",T->data); Inorder(T->rchild); } } /*后序遍历二叉树*/ void Postorder(BinTree T) { if(T) { Postorder(T->lchild); Postorder(T->rchild); printf("%C ",T->data); } } int find(BinTree T,char x) { if(T) { if((T->data)==x) sum++; find(T->lchild,x); find(T->rchild,x); } return sum; }
以上就是二叉树链式存储的一个小实例，需学习要的同学请参考，谢谢支持
【C语言 二叉树的链式存储实例】相关文章：