C++树的相关知识

二叉树遍历

有4种遍历二叉树的常用方法：

前序遍历中序遍历后序遍历层次遍历

前序遍历

void preOrder(binaryTreeNode<T> *t) //递归版 { if(t!=NULL) { visit(t); preOrder(t->leftChild); preOrder(t->rightChild); } }

迭代使用栈来实现前序遍历

void PreOrderIter(TreeNode* root) //迭代版 { if (root == NULL) { return; } stack<TreeNode*> stack; stack.push(root); while (!stack.empty()) { auto top = stack.top(); stack.pop(); cout << top->val << " "; if (top->right != NULL) { stack.push(top->right); //先右 } if(top->left!=NULL) { stack.push(top->left); //后左 } } }

中序遍历

void inOrder(binaryTreeNode<T> *t) //递归 { if(t!=NULL) { inOrder(t->leftChild); visit(t); inOrder(t->rightChild); } }

先把root、以及root左孩子都压入栈中 栈顶出栈并访问，把栈顶的右孩子作为新的根节点

void InOrderIter(TreeNode* root) //迭代 { stack<TreeNode*> stack; if (root == NULL) { return; } while (!stack.empty() || root!=NULL ) { while (root != NULL) { stack.push(root); root = root->left; } auto top = stack.top(); stack.pop(); cout << top->val << " "; root = top->right; } }

后序遍历

void postOrder(binaryTreeNode<T> *t) //递归 { if(t!=NULL) { postOrder(t->leftChild); postOrder(t->rightChild); visit(t); } }

迭代使用栈来实现后序遍历

vector<int> PostOrderIter(TreeNode* root) //迭代 { vector<int> result; if (root == NULL) { return result; } stack<TreeNode*> stack; stack.push(root); while (!stack.empty()) { auto top = stack.top(); stack.pop(); result.push_back(top->val); if (top->left != NULL) { stack.push(top->left); //先右 } if (top->right != NULL) { stack.push(top->right); //后左 } } reverse(result.begin(), result.end()); //反转容器 return result; }

visit函数

void visit(binaryTreeNode<t> *x) {//访问节点*x,仅输出element域 cout<<x->element<<" "; }

层次遍历

void levelOrder(binaryTreeNode<T> *t) { arrayQueue<binaryTreeNode<T>*> q; while(t!=NULL) { visit(t); //将t的孩子插入队列 if(t->leftChild!=NULL) q.push(t->leftChild); if(t->rightChild!=NULL) q.push(t->rightChild); //提取下一个要访问的节点 try{t=q.front();} catch(queueEmpty) {return;} q.pop(); } }

仅当树非空时，才进入while循环。进入while循环后，首先访问根节点，再把其子节点（如果有）加到队列中，然后访问队首元素。若队列为空，则front()抛出一个类型为queueEmpty的异常；若队列不为空，则front()的返回值指向队首元素指针，下一次循环将访问这个元素。