2023年6月22日发(作者：)

前序、中序、后序、层次遍历（超详细解答，实例含代码关于前序、中序、后序、层次遍历完整代码放在⽂章末尾：⼆叉树遍历顺序书上的概念emmm（虽然看了概念，但是很迷糊，可能是我有点莽，还是实例好理解）：前序遍历1.访问根节点2.前序遍历左⼦树3.前序遍历右⼦树（所以到底是怎么遍历的嘛，，，o(￣︶￣)o看图前序遍历：对于所遍历的当前节点，直接输出，然后先找它的左孩⼦，最后找它的右孩⼦。注意，我的意思是说找到它的左孩⼦，那么更新它的左孩⼦为当前节点，⼜从左孩⼦的左孩⼦开始找那么当它左孩⼦这条线的所有后代都遍历完全了才去遍历祖宗的右孩⼦具体过程如下：前序遍历顺序结果：1 2 4 8 10 5 3 6 7 9（1）输出 1：1是根节点，遍历左孩⼦2（2）输出 2：遍历左孩⼦4（3）输出 4：没有左孩⼦，遍历右孩⼦8（4）输出 8：没有左孩⼦，输出右孩⼦10（5）输出10：没有孩⼦，回到⽗节点，⽗节点遍历完全，回到祖⽗节点， 祖⽗节点遍历完全，再回到曾祖⽗节点2，因为2已经遍历过 左孩⼦，所以遍历右孩⼦5（6）输出 5：没有孩⼦。往上⼀辈⾛。（7）输出 3：输出左孩⼦6（8）输出 6：没有孩⼦，回到⽗节点3，遍历右孩⼦（9）输出 7：只有左孩⼦，输出左孩⼦9（10）输出 9：遍历完毕前序遍历代码：templatevoid binaryTree::preOrder(binaryTreeNode *t){// Preorder traversal. if (t != NULL) { counts[(t->element)-1]=treeCount(t); deep[(t->element)-1]=height(t); binaryTree::visit(t); preOrder(t->leftChild); preOrder(t->rightChild); }}中序遍历1.中序遍历左⼦树2.访问根节点3.中序遍历右⼦树（所以概念是在⼲嘛，我还是⽊知，继续实例中序遍历：对于所遍历的当前节点，先找出它的左孩⼦输出，再输出它本⾝，最后找出它的右孩⼦。我的意思就是你需要⼀直找到最晚辈的左边，然后输出它，再把最晚辈的第⼀个祖宗的右孩⼦输出。（有点抽象，看实例.原来书上的概念就是让你好好理解⼦树和树，根，理解了应该莫得问题具体过程如下：中序遍历：4 8 10 2 5 1 6 3 9 7（1）输出 4：1的左孩⼦2，2的左孩⼦4，4没有左孩⼦，输出，再看4的右孩⼦8 为当前节点。8没有左孩⼦，输出（2）输出 8：8的右孩⼦10（3）输出 10：回到⾃⼰的祖宗2，2的左⼦树遍历完全，输出（4）输出 2：再看右⼦树， 只有⼀个右孩⼦，输出（5）输出 5：找祖宗，发现1的左⼦树遍历完全（6）输出 1：找1的右晚辈（右⼦树），右孩⼦3，3有左孩⼦，左孩⼦没孩⼦，输出（7）输出 6：6的⽗亲3（8）输出 3：3的右孩⼦7，但是7有左孩⼦9（9）输出 9：9的⽗亲7（10）输出 7：遍历完全中序遍历代码：templatevoid binaryTree::inOrder(binaryTreeNode *t){// Inorder traversal. if (t != NULL) { inOrder(t->leftChild); binaryTree::visit(t); inOrder(t->rightChild); }}后序遍历1.后序遍历左⼦树2.后序遍历右⼦树3.访问根节点（看完了前两个讲解，我认为你应该对概念有意识了吧，还⽊有？？？我们继续，谁让⽂章题⽬叫做超详细呢，╭(╯^╰)╮后序遍历： 对于当前节点，先找出它的左晚辈（左⼦树），再找出它的右晚辈，最后输出它 ⾃⼰。我的意思就是对于当前节点，我就从它开始，找它左孩⼦，再看它左孩⼦ 有⽊有孩⼦，左孩⼦那边找完了，再找右边，右边找完了，就是它⾃⼰。 Do you understand?（⽊有？？？具体过程如下：后序遍历：10 8 4 5 2 6 9 7 3 1（1）输出 10：1是⽼祖宗，找它最左晚辈4，4⽊有左孩⼦，找4的右孩⼦8， 8⽊有左孩⼦，找8的右孩⼦10，10没有孩⼦，输出（2）输出 8：10的⽗亲，找到8的⽗亲4（3）输出 4：4的⽗亲是2，但是2还有右孩⼦，输出5（4）输出 5：再找5的⽗亲（5）输出 2：发现2的⽗亲1是⽼祖宗，那么整棵树的左⼦树就遍历完了，遍历右⼦树（6）输出 6：1的左孩⼦3，3的左孩⼦6，6⽊有孩⼦，只能输出，3有右孩⼦呀，所以 更新3的右孩⼦为当前节点，继续往下找（7）输出 9：9没有孩⼦（8）输出 7：7是9的⽗亲，3的孩⼦呀，孙⼦呀等就遍历完了（9）输出 3：发现只剩下⽼祖宗了，肯定要输出吧（10）输出 1后序遍历代码：templatevoid binaryTree::postOrder(binaryTreeNode *t){// Postorder traversal. if (t != NULL) { postOrder(t->leftChild); postOrder(t->rightChild); binaryTree::visit(t); }}层次遍历1.层次遍历当前层（从左⾄右2.层次遍历下⼀层（-_-|| ，⼤概概念是这个，话不多说，看图有真相层次遍历：⽐前⾯3种遍历简单得多，但是代码有点困难。就是从当前层最左节点开始，⼀直往其右边找点。找完了就进⼊下⼀层具体过程如下：层次遍历：1 2 3 4 5 6 7 8 9 10（1）输出 1：第⼀层只有 1，进⼊下⼀层（2）输出 2：第⼆层有2 和 3，2是最左端，3是最右端（3）输出 3：进⼊下⼀层（4）输出 4：第三层有4个元素，4是最左端，7是最右端，依次输出（5）输出 5（6）输出 6（7）输出 7：进⼊下⼀层（8）输出 8：第四层有2个元素（9）输出 9：进⼊下⼀层（10）输出 10：最后⼀层，只有⼀个元素，遍历完层次遍历代码：template void binaryTree::levelOrder(){// Level-order traversal. binaryTreeNode * q[treeSize]; q[0]=root;//起始元素肯定是根 cout<element<<" "; for(int i=1;ileaves==1) { index++; } if(i%2!=0) { q[i]=q[index]->leftChild; if(q[i]!=NULL) cout<element<<" "; } else { q[i]=q[index]->rightChild; q[index]->leaves=1; if(q[i]!=NULL) cout<element<<" "; } }}实例完整代码题⽬创建⼆叉树类。⼆叉树的存储结构使⽤链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算⼆叉树结点数⽬、计算⼆叉树⾼度。输⼊格式第⼀⾏为⼀个数字n (10<=n<=100000)，表⽰有这棵树有n个节点，编号为1~n。之后n⾏每⾏两个数字，第 i ⾏的两个数字a、b表⽰编号为 i 的节点的左孩⼦节点为 a，右孩⼦节点为 b，-1表⽰该位置没有节点。保证数据有效，根节点为1。输出格式第⼀⾏，n个数字，表⽰该树的层次遍历。第⼆⾏，n个数字，第i个数字表⽰以 i 节点为根的⼦树的节点数⽬。第三⾏，n个数字，第i个数字表⽰以 i 节点为根的⼦树的⾼度。输⼊：52 34 5-1 -1-1 -1-1 -1输出：1 2 3 4 55 3 1 1 13 2 1 1 1输⼊：53 2-1 -14 5-1 -1-1 -1输出：1 3 2 4 55 1 3 1 13 1 2 1 1输⼊：102 -14 36 -15 89 7-1 -1-1 -1-1 -110 -1-1 -1输出：1 2 4 3 5 8 6 9 7 1010 9 2 6 4 1 1 1 2 16 5 2 4 3 1 1 1 2 1#includeusing namespace std;int counts[999999];int deep[999999];templatestruct binaryTreeNode{ T element;int leaves; binaryTreeNode *leftChild,*rightChild; //左⼦树和右⼦树

};templatevoid erase(binaryTreeNode*& proot){ if(proot!=NULL) { erase(proot->leftChild); erase(proot->rightChild); delete proot; proot=NULL; }}templateclass binaryTree{ public: binaryTree(){root=NULL;treeSize=0;}//构造函数

~binaryTree(){erase(root);}//析构函数

bool empty() const{return treeSize==0;} int size() const{return treeSize;} binaryTreeNode** rootElement(){return &root;} void makeTree(T* elem,int n); void preOrder(binaryTreeNode* t); void inOrder(binaryTreeNode* t); void postOrder(binaryTreeNode* t); int treeCount(binaryTreeNode * t); void levelOrder(); int height(binaryTreeNode *t); private: binaryTreeNode *root;

int treeSize;

static void (*visit)(binaryTreeNode*);

};

templatevoid (*binaryTree::visit)(binaryTreeNode*);templateint binaryTree::treeCount(binaryTreeNode * t){ int n=0; if(t!=NULL) { n=treeCount(t->leftChild)+treeCount(t->rightChild)+1; } return n;}templatevoid binaryTree::makeTree(T* elem,int n){ binaryTreeNode ** (array[n/2])={}; array[0]=&root; root=new binaryTreeNode; root->element=elem[0]; root->leftChild=NULL; root->rightChild=NULL; root->leaves=0; for(int i=1;i* p=new binaryTreeNode; if(elem[i]!=-1) { p->element=elem[i]; p->leftChild=NULL; p->rightChild=NULL; p->leaves=0; } else p=NULL; if(i%2!=0) { (*array[index])->leftChild=p; if(p!=NULL) array[(p->element)-1]=&((*array[index])->leftChild); } else { (*array[index])->rightChild=p; if(p!=NULL) array[(p->element)-1]=&((*array[index])->rightChild); }

} treeSize=n;}templatevoid binaryTree::preOrder(binaryTreeNode *t){// Preorder traversal. if (t != NULL) { counts[(t->element)-1]=treeCount(t); deep[(t->element)-1]=height(t); //binaryTree::visit(t); preOrder(t->leftChild); preOrder(t->rightChild); }}templatevoid binaryTree::inOrder(binaryTreeNode *t){// Inorder traversal. if (t != NULL) { inOrder(t->leftChild); binaryTree::visit(t); inOrder(t->rightChild); }}templatevoid binaryTree::postOrder(binaryTreeNode *t){// Postorder traversal. if (t != NULL) { postOrder(t->leftChild); postOrder(t->rightChild); binaryTree::visit(t); }}template void binaryTree::levelOrder(){// Level-order traversal. binaryTreeNode * q[treeSize]; q[0]=root; cout<element<<" "; for(int i=1;ileaves==1) { index++; } if(i%2!=0) { q[i]=q[index]->leftChild; if(q[i]!=NULL) cout<element<<" "; } else { q[i]=q[index]->rightChild; q[index]->leaves=1; if(q[i]!=NULL) cout<element<<" "; } }}template int binaryTree::height(binaryTreeNode *t){// Return height of tree rooted at *t. if (t == NULL) return 0; // empty tree int hl = height(t->leftChild); // height of left int hr = height(t->rightChild); // height of right if (hl > hr) return ++hl; else return ++hr;}int main(){ int n; cin>>n; int *tr=new int[2*n+1]; binaryTree tre; tr[0]=1; for(int i=1;i<=(2*n);i++) { cin>>tr[i]; } ee(tr,2*n+1); rder(); cout<* node=*ement(); er(node); for(int i=0;i

return 0;}