由数组创建完全二叉树和二叉树的遍历

由数组创建完全二叉树

int main(){ vector<int> a({4,2,5,1,3,-1,6,0}); vector<TreeNode*> tree(a.size(),NULL); // 创建二叉树节点 for(int i=0;i<a.size();++i){ if(a[i]!=-1){ tree[i] = new TreeNode(a[i]); } } // 创建二叉树：对所有非终端节点添加左右子树 for(int i=0;i<=a.size()/2-1;++i){ tree[i]->left = tree[2*i+1]; if(2*i+2 < a.size()){ tree[i]->right = tree[2*i+2]; } } }

一、前序遍历

//递归前序遍历 void preorder(node*& root) { if (root == NULL) { return; } cout << root->val << ' '; //访问根节点 preorder(root->left); preorder(root->right); } //非递归前序遍历 //借助栈，先压入根节点，每访问一个节点时出栈，然后先压右子树，再压左子树。 void preorder(node* root) { stack<node*> st; st.push(root); while (!st.empty()) { node* cur = st.top(); cout << cur->val << ' '; st.pop(); if (cur->right != NULL) { st.push(cur->right); } if (cur->left != NULL) { st.push(cur->left); } } }

二、中序遍历

//递归中序遍历 void inorder(node*& root) { if (root == NULL) { return; } inorder(root->left); cout << root->val << ' '; //访问根节点 inorder(root->right); } //非递归中序遍历 //对于每个父节点，都是先访问其最左下角的节点，然后再访问相应父节点，再考虑右子树。因此借助栈，使用指针p追踪每个节点所有左子节点并入栈， //然后访问栈顶元素，并将指针p指向其右子树；重复同样的操作。只有当p==NULL且栈中也没有元素时，才表明已遍历完所有节点。 void inorder(node*& root) { if (root == NULL) { return; } stack<node*> st; node* p = root; while (!st.empty() || p != NULL) { //扫描p的所有左节点入栈 while (p != NULL) { st.push(p); p = p->left; } if (!st.empty()) { p = st.top(); st.pop(); cout << p->val << ' '; p = p->right; } } }

三、后序遍历

//递归后序遍历 void postorder(node* root) { if (root == NULL) { return; } postorder(root->left); postorder(root->right); cout << root->val << ' '; }

因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用堆栈来存储节点，必须分清返回根节点时，是从左子树返回的，还从右子树返回的。所以，使用辅助指针r，其指向最近访问过的节点。也可以在节点中增加一个标志域，记录是否已被访问。 二叉树后序遍历的非递归实现

void postorder(TreeNode* root){ TreeNode *p = root, *r = NULL; stack<TreeNode*> s; while(p!=NULL || !s.empty()){ if(p!=NULL){ s.push(p); p = p->left; } else{ p = s.top(); if(p->right!=NULL && p->right != r){ p = p->right; } else{ s.pop(); cout<<p->val<<ends; r = p; p = NULL; } } }//while }

四、从前序与中序遍历序列构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/ 对于任意一颗树而言，前序遍历的形式总是 [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ] 即根节点总是前序遍历中的第一个节点。 而中序遍历的形式总是 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样一来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

时间复杂度：O(n)，其中 n 是树中的节点个数。

空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h < n，所以总空间复杂度为 O(n)。

例如：先序：FDXEAG 中序：XDEFAG 先序第一个为根节点，在中序序列中找到此根节点的位置，则其左边size_left个节点为左子树的节点，右边为右子树的节点。把左子树所有节点（如XDE）进行递归得到左子树的序列，先序中对应的左子树的所有节点(如DXE)是从当前根节点（每次递归的根节点都是从先序序列中获取）开始往后的size_left个节点，两个序列中对应的左子树作为递归参数进行递归。

struct node{ char val; node* left, *right; node() { ; } node(char x) :val(x), left(NULL), right(NULL) {} }; void postorder(node* root) { if (root == NULL) { return; } postorder(root->left); postorder(root->right); cout << root->val; } //从前序与中序遍历序列构造二叉树（假设二叉树中无重复元素） //后面4个int参数分别表示每次递归时先序和中序中对应子树的边界 node* buildtree(string& pre,string& in,unordered_map<char,int>& mp,int pre_l,int pre_h,int in_l,int in_h) { //当当前递归的子树（左子树或右子树）的左边界大于有边界时，说明此时该子树已无节点，则递归结束 if (pre_l > pre_h) { return NULL; } //先构造根节点:当前先序子树的第一个元素 node* root = new node(pre[pre_l]); int in_root = mp[pre[pre_l]]; //in_root为中序子树中的根节点下标 int size_left = in_root - in_l; //中序中左子树节点数 //递归构造左子树 root->left = buildtree(pre, in, mp, pre_l+1, pre_l+size_left, in_l, in_root-1); //递归构造右子树 root->right = buildtree(pre, in, mp, pre_l+size_left+1, pre_h, in_root+1, in_h); return root; } int main() { string s1, s2; //s1为前序遍历序列，s2为后序遍历序列 while (cin >> s1 >> s2) { int n = s1.size(); //二叉树节点数 unordered_map<char, int> mp; //将中序序列存入map，便于查找 for (int i = 0; i < n; ++i) { mp[s2[i]] = i; } node* root = buildtree(s1,s2,mp,0,n-1,0,n-1); postorder(root); cout<<endl; } }

五、从中序与后序遍历序列构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/

//从中序与后序遍历序列构造二叉树 node* buildtree(string& in,string& post, unordered_map<char, int>& mp, int post_l,int post_r,int in_l,int in_r) { //递归出口 if (post_l > post_r) { return NULL; } node* root = new node(post[post_r]);//构造根节点：后序中子树的最后一个元素 int in_root = mp[post[post_r]]; //中序子树中根节点下标 int size_right = in_r - in_root; //中序中右子树节点数 //递归构造右子树 //root->right = buildtree(in, post, mp, post_r - size_right, post_r - 1, in_root + 1, in_r); //递归构造左子树 root->left = buildtree(in, post, mp, post_l, post_r - size_right - 1, in_l, in_root - 1); root->right = buildtree(in, post, mp, post_r - size_right, post_r - 1, in_root + 1, in_r); return root; }

六、层次遍历 （广度优先搜索）

void bfs(node *root){ queue<node*> Q; Q.push(root); while(!Q.empty()){ node* tmp = Q.front(); Q.pop(); printf("%d",tmp->val); if(tmp->left!=NULL) Q.push(tmp->left); if(tmp->right!=NULL) Q.push(tmp->right); } }

深度优先搜索

struct Node { int self; // 數據 Node *left; // 左節點 Node *right; // 右節點 }; const int TREE_SIZE = 9; std::stack<Node *> unvisited; Node nodes[TREE_SIZE]; Node *current; //初始化樹 （二叉树的创建） for (int i = 0; i < TREE_SIZE; i++) { nodes[i].self = i; int child = i * 2 + 1; if (child < TREE_SIZE) // Left child nodes[i].left = &nodes[child]; else nodes[i].left = NULL; child++; if (child < TREE_SIZE) // Right child nodes[i].right = &nodes[child]; else nodes[i].right = NULL; } unvisited.push(&nodes[0]); //先把0放入UNVISITED stack // 樹的深度優先搜索在二叉樹的特例下，就是二叉樹的先序遍歷操作（這裡是使用循環實現) // 只有UNVISITED不空 while (!unvisited.empty()) { current = (unvisited.top()); //當前應該訪問的 unvisited.pop(); if (current->right != NULL) unvisited.push(current->right ); if (current->left != NULL) unvisited.push(current->left); cout << current->self << endl; }