如何通过C语言实现树的简单应用算法学习？

本文共计1815个文字，预计阅读时间需要8分钟。

1. 找树根和子节点[题目描述]给定一棵树，输出树的根节点、子节点最多的节点及其子节点。[输入]第一行：n（节点个数，100以内）m（边个数，200以内）以下m行：每行两个节点x和y，表示它们之间有一条边。[输出]输出树的根节点、子节点最多的节点及其子节点。

1、找树根和孩子

给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。

第一行：n（结点个数≤100），m（边数≤200）。

以下m行：每行两个结点x和y，表示y是x的孩子(x,y≤1000)。

第一行：树根：root；

第二行：孩子最多的结点max；

第三行：max的孩子（按编号由小到输出）。

8 7 4 1 4 2 1 3 1 5 2 6 2 7 2 8 4 2 6 7 8

#include<iostream> #include<cmath> #include<algorithm> #include<vector> #include<queue> using namespace std; int tree[105]; int main() { int n,m,x,y; cin>>n>>m; for(int i=0;i<m;i++) { cin>>x>>y; tree[y]=x;// y的父亲结点是x } int root; for(int i=1;i<=n;i++) { if(tree[i]==0)// 父亲结点为0的结点是根节点 { root=i; break; } } int maxt=0,sumt=0; for(int i=1;i<=n;i++) { int sum=0;// 孩子结点的个数 for(int j=1;j<=n;j++) { if(tree[j]==i)sum++;// 对每一个结点i，寻找其孩子结点 } if(sum>sumt) { sumt=sum; maxt=i; } } cout<<root<<"\n"<<maxt<<endl; for(int i=1;i<=n;i++) { if(tree[i]==maxt) { cout<<i<<" "; } } return 0; }

2、求后序遍历

输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。

共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。

一行，表示树的后序遍历序列。

abdec dbeac debca

#include<iostream> #include<cstring> using namespace std; const int N=100000; // 定义二叉树的结点类型 struct Node { char data; Node* lchild; Node* rchild; }; // 先序、中序、后序序列 char pre[N],in[N],post[N]; // 重建二叉树，递归方法 // 利用先序[preL,preR]，中序[inL,inR]序列 Node* create(int preL,int preR,int inL,int inR) { if(preL>preR)return NULL;//遍历完了 Node *root=new Node; root->data=pre[preL];// 先序序列的第一个即为根结点 int k;// 找到根节点在中序序列中的位置 for(k=inL;k<=inR;k++) { if(in[k]==root->data) { break; } } int numLeft=k-inL; // 左子树的结点数量 root->lchild=create(preL+1,preL+numLeft,inL,k-1);// 递归创建左子树 root->rchild=create(preL+numLeft+1,preR,k+1,inR);// 递归创建右子树 return root; // 返回根结点 } // 二叉树的后序遍历 左-右-根 的顺序 void postOrder(Node* root) { if(root==NULL) return; postOrder(root->lchild);// 先递归遍历左子树 postOrder(root->rchild);// 先递归遍历右子树 cout<<root->data; // 输出结点的值 } int main() { scanf("%s",pre); scanf("%s",in); int len=strlen(pre); Node *root=create(0,len-1,0,len-1);// 下标是从0开始的 postOrder(root); return 0; }

3、树的凹入表示法输出

树的凹入表示法主要用于树的屏幕或打印输出，其表示的基本思想是兄弟间等长，一个结点的长度要不小于其子结点的长度。二叉树也可以这样表示，假设叶结点的长度为1，一个非叶结点的长度等于它的左右子树的长度之和。

一棵二叉树的一个结点用一个字母表示（无重复），输出时从根结点开始：

每行输出若干个结点字符（相同字符的个数等于该结点长度），

如果该结点有左子树就递归输出左子树；

如果该结点有右子树就递归输出右子树。

假定一棵二叉树一个结点用一个字符描述，现在给出先序和中序遍历的字符串，用树的凹入表示法输出该二叉树。

两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的先序遍历和中序遍历的序列。

行数等于该树的结点数，每行的字母相同。

ABCDEFG CBDAFEG AAAA BB C D EE F G

#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N=100000; struct Node { char data; Node* lchild; Node* rchild; }; char pre[N],in[N]; int cnt[N]; // 建树 Node* create(int preL,int preR,int inL,int inR) { if(preL>preR)return NULL; Node *root=new Node; root->data=pre[preL]; int k; for(k=inL;k<=inR;k++) { if(in[k]==root->data) { break; } } int numLeft=k-inL; root->lchild=create(preL+1,preL+numLeft,inL,k-1); root->rchild=create(preL+numLeft+1,preR,k+1,inR); return root; } // 计算每个结点的长度 int count(Node* root) { if(root->lchild==NULL&&root->rchild==NULL) { cnt[root->data]=1;// 叶子结点的长度为1 return 1; } int cntL=0,cntR=0; // 递归，求左、右子树的长度 if(root->lchild!=NULL) { cntL=count(root->lchild); } if(root->rchild!=NULL) { cntR=count(root->rchild); } cnt[root->data]=cntL+cntR;//父节点的长度=左右子树长度之和 return cntL+cntR; } int main() { scanf("%s",pre); scanf("%s",in); int len=strlen(pre); Node *root=create(0,len-1,0,len-1); count(root); // 对应每一个结点，输出其长度个元素值 for(int i=0;i<len;i++) { for(int j=0;j<cnt[pre[i]];j++) { cout<<pre[i]; } cout<<endl; } return 0; }

4、查找二叉树

题目描述】 已知一棵二叉树用邻接表结构存储，中序查找二叉树中值为x的结点，并指出是第几个结点。例：如图二叉树的数据文件的数据格式如下:

第一行n为二叉树的结点个树，n<=100；第二行x表示要查找的结点的值；以下第一列数据是各结点的值，第二列数据是左儿子结点编号，第三列数据是右儿子结点编号。

一个数即查找的结点编号。

7 15 5 2 3 12 4 5 10 0 0 29 0 0 15 6 7 8 0 0 23 0 0 4

#include<iostream> using namespace std; const int N=100000; struct Node { int data; int lchild; int rchild; }arr[N]; bool flag[N]; int val; int x=0; // 按照左根右顺序 void in(int root) { if(arr[root].lchild>0) { in(arr[root].lchild); } x++;// 遍历到的结点数加1 if(arr[root].data==val) { cout<<x; return; } if(arr[root].rchild>0) { in(arr[root].rchild); } } int main() { int n; cin>>n>>val; for(int i=1;i<=n;i++) { cin>>arr[i].data>>arr[i].lchild>>arr[i].rchild; flag[arr[i].lchild]=true;// 都不是树根 flag[arr[i].rchild]=true; } int rt; for(int i=1;i<=n;i++) { if(!flag[i]) { rt=i;// 找到树根 break; } } in(rt); return 0; }