C语言 二叉树的链式存储实例

概述二叉树的链式存储实现二叉树的基本 *** 作：建立、遍历、计算深度、结点数、叶子数等。

二叉树的链式存储

实现二叉树的基本 *** 作：建立、遍历、计算深度、结点数、叶子数等。

输入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("%c\n",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语言 二叉树的链式存储实例全部内容，希望文章能够帮你解决C语言 二叉树的链式存储实例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。