首页 > 代码库 > 二叉树
二叉树
一、二叉树简介
二叉树节点定义为:
1 struct TreeNode 2 {3 int val;4 TreeNode *left;5 TreeNode *right;6 TreeNode(int x) : val(x), left(NULL), right(NULL) {}7 };
有时需要增加parent等其他信息。
二叉树的创建采用输入满二叉树数组的形式,例如 A = [1, -2, -3, 1, 3, 2, NIL, -1], 表示为:
1
-2 -3
1 3 2
-1
由数组A构建一颗二叉树:
1 TreeNode* create_node(int x) 2 { 3 if (x == NIL) /* means null */ 4 return NULL; 5 else 6 return new TreeNode(x); 7 } 8 9 TreeNode* btree_create(TreeNode *root, int va[], int n)10 {11 TreeNode *nt = NULL, *pt = NULL;12 queue<TreeNode *> qtree;13 int i = 1;14 15 root = new TreeNode(va[0]);16 qtree.push(root);17 while (qtree.size() > 0)18 {19 pt = qtree.front();20 qtree.pop();21 if (pt == NULL)22 continue; 23 /* create left node */24 if (i >= n)25 break;26 pt->left = create_node(va[i]);27 i++;28 qtree.push(pt->left); 29 /* create right node */30 if (i >= n)31 break;32 pt->right = create_node(va[i]);33 i++;34 qtree.push(pt->right);35 }36 return root;37 }
二、二叉树基本操作
1、min/max depth
int minDepth(TreeNode *root) { if (root == NULL) return 0; int ml = minDepth(root->left); int mr = minDepth(root->right); if (ml == 0) /* the min depth should contain leaf, not only the root node. */ return (mr + 1); if (mr == 0) return (ml + 1); return min(ml, mr) + 1; }int maxDepth(TreeNode *root) { if (root == NULL) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; }
2、二叉树广度优先/深度优先遍历
2.1、BFS
二叉树的bfs记为层次遍历,使用队列做辅助,如下:
a)将root放入队列queue
b)queue不为空,取出队列元素node,并访问
c)node左右节点入队,重复b
1 vector<int> btree_bfs(TreeNode* root) 2 { 3 vector<int> tree_nodes; 4 queue<TreeNode*> qtree; 5 TreeNode* pt = root; 6 7 if (pt == NULL) 8 return tree_nodes; 9 10 qtree.push(pt);11 while (!qtree.empty())12 {13 pt = qtree.front();14 qtree.pop();15 tree_nodes.push_back(pt->val);16 17 if (pt->left != NULL)18 qtree.push(pt->left);19 if (pt->right != NULL)20 qtree.push(pt->right);21 }22 23 return tree_nodes;24 }
2.2 DFS
二叉树深度优先遍历,不妨以左节点优先,即左子树存在则先查询左节点,如下:
a) 当前节点不为空,访问之。并将右节点压栈,继续访问左节点。
b)节点为空,则从栈中取出node,继续a,直至访问完。
1 vector<int> btree_dfs(TreeNode* root) 2 { 3 vector<int> tree_nodes; 4 stack<TreeNode*> stree; 5 TreeNode* pcur = root; 6 7 if (pcur == NULL) 8 return tree_nodes; 9 10 while (!stree.empty() || (pcur != NULL))11 {12 if (pcur != NULL)13 {14 tree_nodes.push_back(pcur->val); // visit current15 if (pcur->right != NULL)16 stree.push(pcur->right);17 pcur = pcur->left;18 }19 else20 {21 pcur = stree.top();22 stree.pop();23 }24 }25 26 return tree_nodes;27 }
3、pre/in/post order traverse
这三种方式遍历二叉树,递归遍历比较简单,非递归遍历则需要借助queue/stack。
3.1、preorder
1 void preorder(TreeNode *root, vector <int> &ret)2 {3 if (root == NULL)4 return;5 ret.push_back(root->val);6 preorder(root->left, ret);7 preorder(root->right, ret);8 }
preorder迭代形式和dfs完全一致。
3.2、inorder
void inorder(TreeNode *root, vector <int> &ret) { if (root == NULL) return; inorder(root->left, ret); ret.push_back(root->val); inorder(root->right, ret); }
迭代方式遍历:
a)当前节点不为空,则压栈并访问左子树。
b)否则,出栈并访问元素,再访问右子树,重复a。
1 vector<int> inorderTraversal(TreeNode *root) 2 { 3 vector<int> tree_nodes; 4 stack<TreeNode*> stree; 5 TreeNode* pcur = root; 6 7 while (!stree.empty() || (pcur != NULL)) 8 { 9 if (pcur != NULL)10 {11 stree.push(pcur);12 pcur = pcur->left; //left13 }14 else15 {16 pcur = stree.top(); 17 stree.pop();18 tree_nodes.push_back(pcur->val); 19 pcur = pcur->right; //right20 }21 }22 return tree_nodes;23 }
3.3 post order
void inorder(TreeNode *root, vector <int> &ret) { if (root == NULL) return; inorder(root->left, ret); inorder(root->right, ret); ret.push_back(root->val); }
后序遍历非递归形式:
a)当前节点pcur不为空,节点入栈,访问左节点
b)否则,获取栈顶节点peek,如果peek->right不为空且不是last_vist_node, pcur变为peek->right
c)否则last_vist_node为栈顶元素,并访问last_vist_node,继续a)
1 vector<int> postorderTraversal(TreeNode *root) 2 { 3 vector<int> tree_nodes; 4 stack<TreeNode *> stree; 5 TreeNode *current = root, *last_visit_node = NULL, *peek_node = NULL; 6 7 while (!stree.empty() || (current != NULL)) 8 { 9 if (current != NULL)10 {11 stree.push(current);12 current = current->left;13 }14 else15 {16 peek_node = stree.top();17 if ((peek_node->right != NULL) && (peek_node->right != last_visit_node))18 { // peek‘s right child exists and it‘s not come from last child19 current = peek_node->right;20 }21 else22 {23 last_visit_node = peek_node;24 stree.pop();25 tree_nodes.push_back(last_visit_node->val);26 }27 }28 }29 30 return tree_nodes;31 }
二叉树