数据结构-树与二叉树-算法实现
2021/4/25 20:27:20
本文主要是介绍数据结构-树与二叉树-算法实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
任务
- 假设二叉树采用链式方法存储,数据结构定义如下:
typedef char DataType; struct node { DataType info ; struct node *lchild , *rchild ; };
完成两个函数编写
- 请编写算法计算二叉树T的高度的函数
- 请编写算法计算二叉树T的叶子结点数的函数
- 已知某二叉树的先根周游序列是:ABDEGCFHIJ,中根周游序列是:DBGEAHFIJC,画出这课二叉树,并给出二叉树的后根周游序列。
3.已知了一棵二叉树的顺序存储结构如下,其中空白表示结点不存在。请画出这棵二叉树
元素 | A | B | C | D | F | E | G | H | |||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
4.已知一棵度为m的树中有n1个度为1 的结点,n2个度为2的结点,.....nm个
度为m的结点,问该树中有多少个终端结点? ( 要求写出计算推导过程)。
5.设给定权集w={2,3,4,7,8,9}
- 求各权值对应等长二进制编码
- 试构造关于w的一棵哈夫曼树,并求其哈夫曼编码。
代码实现
第一题
#include <iostream> using namespace std; typedef char DataType; struct node{ DataType info ; struct node *lchild , *rchild ; }; typedef struct node *BiTree; /* 函数名:createBiTree 函数功能:创建二叉树,并返回二叉树的根结点指针 参数:无 返回值:二叉树的根结点指针 */ BiTree createBiTree() { DataType ipt; BiTree root; cin>>ipt; if(ipt == '#'){ root = NULL; return root; } else{ root = new node; root->info = ipt; root->lchild = createBiTree(); root->rchild = createBiTree(); } return root; } // 计算叶子数 int countLeaf(BiTree T) { static int num = 0; if(T) { if(T->lchild==NULL && T->rchild==NULL) num++; countLeaf(T->lchild); countLeaf(T->rchild); } return num; } // 计算树高 int countLevel(BiTree root){ if(root == NULL) return -1; else{ int left, right; left = 1 + countLevel(root->lchild); right = 1 + countLevel(root->rchild); return left>right?left:right; } } int main(){ BiTree root = createBiTree(); cout<<countLeaf(root)<<" ->叶子"<<endl; cout<<countLevel(root)<<" ->树高"<<endl; return 0; }
第三题
#include <iostream> using namespace std; typedef char DataType; struct BinTree{ int curNum; int maxNum; DataType *info; }; typedef struct BinTree * tree; // 创建树 tree createTree(DataType ipt[], int len){ int i; tree root = new struct BinTree; root->info = new DataType(len); root->curNum = 0; for(i=0; i<len; i++) { root->info[i] = ipt[i]; root->curNum++; } root->maxNum = i; return root; } // 输出节点元素值 void visit(tree root, int i){ cout<< root->info[i]<<" "; } // 左树 int leftChild(int i){ return 2*i+1; } // 右树 int rightChild(int i){ return 2*i+2; } // 先序 void preOrder(tree root, int k){ if(root->info[k] == ' ') return ; visit(root, k); if(leftChild(k) < root->curNum){ preOrder(root, leftChild(k)); } if(rightChild(k) < root->curNum){ preOrder(root, rightChild(k)); } } // 中序 void midOrder(tree root, int k){ if(root->info[k] == ' ') return ; if(leftChild(k) < root->curNum){ midOrder(root, leftChild(k)); } visit(root, k); if(rightChild(k) < root->curNum){ midOrder(root, rightChild(k)); } } // 后序 void lastOrder(tree root, int k){ if(root->info[k] == ' ') return ; if(leftChild(k) < root->curNum){ lastOrder(root, leftChild(k)); } if(rightChild(k) < root->curNum){ lastOrder(root, rightChild(k)); } visit(root, k); } int main(){ DataType ipt[] = {'A', 'B', 'C', ' ', ' ', 'D', 'F', ' ', ' ', ' ', ' ', 'E', 'G', ' ', 'H'}; tree root = createTree(ipt, 14); cout<<"先序输出"<<endl; preOrder(root, 0); cout<<"\n中序输出"<<endl; midOrder(root, 0); cout<<"\n后序输出"<<endl; lastOrder(root, 0); return 0; }
运行结果
第一题
第二题
第三题
第四题
这篇关于数据结构-树与二叉树-算法实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现