首页 > 代码库 > 二叉树

二叉树

2024-08-04 16:26:17   227人阅读

一、二叉树简介

　　二叉树节点定义为：

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     }

 

二叉树


联系
我们