非递归实现遍历
前序遍历非递归实现
- 使用栈来完成。
- 访问左节点,压入右节点。
- 左节点为空,弹出右节点。
中序遍历非递归实现
- 使用栈来完成
- 遇到一个节点,将其推入栈,遍历其左子树
- 遍历完左子树,弹出栈顶节点并访问
- 同时遍历其右节点,重复上述动作。
非递归后续遍历二叉树
- 从根节点开始,判断栈空还是非空
- 沿左路下降。。。
- 最难的。。总之就是左右子树访问完毕,才访问根节点
O(n)
二叉树的搜索
- 宽度搜索
- 队列来存储
- 类似层序遍历。
- 访问当前节点,将左右节点压入队列
- 弹出当前节点
存储结构
使用二叉链表的信息。当前节点,存储左右节点的指针。(还有的保存了parent指针)
寻找一个指针的父节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| Node* FindParent(Node* root, Node* current){ Node* tmp; if(root == NULL) return NULL; if(root->left == current || root->right == current){ return root; } if(tmp = FindParent(root->left, current) != NULL){ return tmp; } if(tmp = FindParent(root->right, current) != NULL) return tmp; return NULL; }
Node* Tree(Node* current){ stack<Node*> s; Node* tmp = root; s.push(NULL); }
|
完全二叉树,用数组层序存储。
编号为 i 的节点的左节点为 2 i + 1
二叉搜索树
快速搜索,时间复杂度为 O(log n )
其中的构建二叉搜索树比较简单。这里重点记一下,BST删除节点的操作。
我们使用递归的来删除节点,需要分三种情况:
- 节点的左节点为空,直接将右节点复制到删除节点的位置。(不用考虑右节点是否为空)
- 如果左节点非空,右节点为空,那就将左节点复制到删除节点的位置。
- 如果左右节点都不为空,那就找出左子树中的最右节点,将右子树的根节点拼接到该最右节点的右边。
- 这个方法其实会导致挂接后,整个树的高度过长,影响搜索的效率
- 我们可以换另外一种思路,就是找到右子树的最小节点,保存其值,赋值给删除节点,然后删除右子树的最小节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| void removehelp(Node* &root, int val){ if(root == NULL) cout << val << " is not in the tree \n" << endl; else if(val < root->val){ removehelp(root->left, val); } else if(val > root->val){ removehelp(root->right, val); } else{ Node* tmp = root; if(root->left == NULL) root = root->right; else if (root->right == NULL) root = = root->left; else{ tmp = deletemin(root->right); root->setValue(tmp->value); } delete tmp; tmp = NULL; } }
Node* deletemin(Node * &root){ if(root->left != NULL){ return deletemin(root->left); } else{ node *tmp = root; root = root->right; return tmp; } }
|
如何放置BST退化成线性结构?
允许重复关键码吗?
Last updated:
Thanks for your reading :) | URL
https://joshuaqyh.github.io/2019/03/29/数据结构-二叉树/