如何做美食网站设计,称多网站建设,制作购物网站教程,大数据开发平台二叉树的知识点1#xff1a; 二叉树存储结构 前序建立二叉树 前序遍历、中序遍历、后序遍历#xff08;递归、非递归#xff09; 二叉树节点总数 二叉树叶子节点数 二叉树深度 遍历二叉树第i层节点 分层遍历二叉树#xff08;递归、非递归#xff09; 求二叉树中节点的最大… 二叉树的知识点1 二叉树存储结构 前序建立二叉树 前序遍历、中序遍历、后序遍历递归、非递归 二叉树节点总数 二叉树叶子节点数 二叉树深度 遍历二叉树第i层节点 分层遍历二叉树递归、非递归 求二叉树中节点的最大距离 已知前序、中序重建二叉树: 以下为具体程序在devc中验证正确 /* abd##e##c## 前序a b d e c 中序d b e a c 后序d e b c a */ #includestdio.h #includestdlib.h #includestack #includevector using namespace std; struct node{ char value; struct node * left; struct node * right; }; typedef struct node Node; int max_dis0; //建树 Node* create_tree(){ Node * root NULL; char input; scanf(%c,input); if(input #){ return NULL; }else{ root (Node *)malloc(sizeof(Node)); if(NULL root){ printf(memory allocation wrong); return NULL; } root-value input; root-left create_tree(); root-right create_tree(); } return root; } //递归前序遍历 void qianxu_travel(Node * root){ if(NULL root){ return; } printf(%c ,root-value); qianxu_travel(root-left); qianxu_travel(root-right); } //递归中序遍历 void zhongxu_travel(Node * root){ if(NULL root){ return; } zhongxu_travel(root-left); printf(%c ,root-value); zhongxu_travel(root-right); } //递归后序遍历 void houxu_travel(Node * root){ if(NULL root){ return; } houxu_travel(root-left); houxu_travel(root-right); printf(%c ,root-value); } //前序遍历非递归 void qianxu_no_rec(Node* root){ stackNode* s; while(NULL ! root || !s.empty()){ if(NULL ! root){ printf(%c ,root-value); s.push(root); root root-left; }else{ root s.top(); s.pop(); root root-right; } } } //中序遍历非递归 void zhongxu_norec(Node* root){ stackNode* s; while(NULL !root || !s.empty()){ if(NULL ! root){ s.push(root); root root-left; }else{ root s.top(); s.pop(); printf(%c ,root-value); root root-right; } } } //递归遍历第i层节点 int level_i_travle(Node* root, int level){ if(NULL root || level 0){ return 0; } if(level 1){ printf(%c ,root-value); } return level_i_travle(root-left,level-1)level_i_travle(root-right,level-1); } //非递归分层遍历二叉树 void level_norec(Node* root){ if(NULL root){ return; } vectorNode* v; v.push_back(root); int cur 0, last 0; while(cur v.size()){ //使用游标不出队列 last v.size(); while(cur last){ printf(%c ,v[cur]-value); if(v[cur]-left){ v.push_back(v[cur]-left); } if(v[cur]-right){ v.push_back(v[cur]-right); } cur ; } printf(\n); } } //求叶子节点的个数 int leaf_num(Node* root){ if(NULL root){ return 0; } if(NULL root-left NULL root-right){ return 1; } return leaf_num(root-left) leaf_num(root-right); } //求二叉树的节点个数 int node_num(Node* root){ if(NULL root){ return 0; } return 1node_num(root-left)node_num(root-right); } //求二叉树的高度 int height(Node* root){ if(NULL root){ return 0; } int num1 height(root-left); int num2 height(root-right); if(num1 num2){ return 1num1; }else{ return 1num2; } } //求二叉树中节点的最大距离 int max_distance(Node* root){ if(NULL root){ return 0; } int num1 max_distance(root-left); int num2 max_distance(root-right); if(max_dis (1num1num2)){ max_dis 1num1num2; } if(num1 num2){ return 1num1; }else{ return 1num2; } } //根据前序、中序重建二叉树 void rebuild(char* preOrder, char* inOrder, int treeLen, Node** root){ //边界判断 if(NULL preOrder || NULL inOrder){ return; } Node* p (Node*)malloc(sizeof(Node)); //根节点赋值 p-value preOrder[0]; p-left NULL; p-right NULL; if(NULL *root){ *root p; } if(treeLen 1){ //剪枝 return; } int left_len 0; int right_len 0; int tmp_len 0; char* left_inOrder inOrder; //求左子树的长度 while(*left_inOrder ! *preOrder){ if(NULL left_inOrder || NULL preOrder){ return; } tmp_len ; if(tmp_len treeLen){ break; } left_inOrder; } left_len left_inOrder - inOrder; right_len treeLen - 1 - left_len; if(left_len 0){ rebuild(preOrder1,inOrder,left_len,((*root)-left)); //递归建造左子树 } if(treeLen-left_len1 0){ rebuild(preOrderleft_len1,inOrderleft_len1,right_len,((*root)-right)); //递归建造右子树 } } int main(){ Node * root NULL; char* szPreOrder abdcef; char* szInOrder dbaecf; //传指针的指针用于后续打印 /* rebuild1(szPreOrder, szInOrder, 6, root); printf(前序递归遍历序列\n); qianxu_travel(root); printf(\n); */ printf(输入以建立二叉树:\n); root create_tree(); printf(非递归分层遍历二叉树\n); level_norec(root); int k 3; printf(第%d层节点:\n,k); level_i_travle(root,k); printf(\n); printf(叶子节点个数%d\n,leaf_num(root)); printf(节点个数%d\n,node_num(root)); printf(高度%d\n,height(root)); printf(前序递归遍历序列\n); qianxu_travel(root); printf(\n); printf(前序非递归遍历序列\n); qianxu_no_rec(root); printf(\n); printf(中序遍历序列\n); zhongxu_travel(root); printf(\n); printf(中序非递归遍历序列\n); zhongxu_norec(root); printf(\n); printf(后序遍历序列\n); houxu_travel(root); printf(\n); printf(后序非递归遍历序列\n); // houxu_norec(root); printf(节点之间的最大距离:\n); max_distance(root); printf(%d\n,max_dis); destory_tree(root); system(pause); return main(); }
