- #include<cstdio>
- #include<stack>
- typedef struct TNode *Position;
- typedef Position BinTree;
- struct TNode
- {
- int Data;
- BinTree Left;
- BinTree Right;
- };
- /* 二叉树递归先序遍历 */
- void PreorderTravseral(BinTree t)
- {
- if(t){
- printf("%d",t->Data);
- PreorderTravseral(t->Left);
- PreorderTravseral(t->Right);
- }
- }
- /* 二叉树递归中序遍历 */
- void InorderTravseral(BinTree t)
- {
- if(t){
- InorderTravseral(t->Left);
- printf("%d",t->Data);
- InorderTravseral(t->Right);
- }
- }
- /* 二叉树递归后序遍历 */
- void PostorderTravseral(BinTree t)
- {
- if(t){
- InorderTravseral(t->Left);
- InorderTravseral(t->Right);
- printf("%d",t->Data);
- }
- }
- /* 二叉树的非递归遍历都需要使用数据结构栈栈 */
- /* 二叉树非递归先序遍历 */
- void PreorderTraversal_unrecursive(BinTree t)
- {
- using std::stack;
- stack<BinTree>s;
- while(t || !s.empty()){
- while(t){
- s.push(t);
- printf("%d",t->Left);
- t = t->Left;
- }
- if(!s.empty()){
- t = s.top();
- s.pop();
- t = t->Right;
- }
- }
- }
- /* 二叉树非递归中序遍历 */
- void InorderTraversal_unrecursive(BinTree t)
- {
- using std::stack;
- stack<BinTree>s;
- while(t || !s.empty()){
- while(t){
- s.push(t);
- t = t->Left;
- }
- if(!s.empty()){
- t = s.top();
- s.pop();
- printf("%d",t->Data);
- t = t->Right;
- }
- }
- }
下面单独介绍树的后序遍历非递归算法.
在树的非递归后序遍历, 对于每个根节点, 要确保其左结点和右结点都被访问了以后才能访问根结点. 没有孩子则可以直接访问. 若非上述两种情况, 则将 P 的右孩子和左孩子依次入栈, 这样就保证了 每次取栈顶元素的时候, 左孩子在右孩子前面被访问, 左孩子和右孩子都在根结点前面被访问.
- void PostorderTraversal_unrecusive(BinTree t)
- {
- if(!t)
- return;
- stack<BinTree>s;
- s.push(t);
- BinTree cur,prev = NULL;
- // 对于兄弟结点, 栈一定先弹出左兄弟, 然后再弹出右兄弟
- // 栈元素排列顺序一定是: 根 右结点 左结点
- while(!s.empty()){
- cur = s.top();
- if((cur->Left == NULL && cur->Data == NULL) ||
- prev != NULL && (prev == cur->Left || prev == cur->Right)){
- printf("%d",cur->Data);
- s.pop();
- prev = cur;
- }
- else{
- if(t->Right)
- s.push(t->Right);
- if(t->Left)
- s.push(t->Left);
- }
- }
- }
BST 常用函数实现
- typedef int ElementType;
- typedef struct TNode *Position;
- typedef Position BinTree;
- struct TNode{
- ElementType Data;
- BinTree Left;
- BinTree Right;
- };
- BinTree Insert( BinTree BST, ElementType X )
- {
- if(!BST){
- BinTree node = (BinTree)malloc(sizeof(struct TNode));
- node->Left = node->Right = NULL;
- node->Data = X;
- return node;
- }
- else if(X> BST->Data)
- BST->Right = Insert(BST->Right,X);
- else if(X <BST->Data)
- BST->Left = Insert(BST->Left,X);
- return BST;
- }
- BinTree Delete( BinTree BST, ElementType X )
- {
- Position temp;
- if(!BST){
- printf("Not Found\n");
- return BST;
- }
- else if(X> BST->Data)
- BST->Right = Delete(BST->Right,X);
- else if(X <BST->Data)
- BST->Left = Delete(BST->Left,X);
- else if(X == BST->Data){
- if(BST->Right && BST->Left){
- temp = FindMin(BST->Right);
- BST->Data = temp->Data;
- BST->Right = Delete(BST->Right, BST->Data);
- }
- else{
- temp = BST;
- if(!BST->Left)
- BST = BST->Right;
- else
- BST = BST->Left;
- free(temp);
- }
- }
- return BST;
- }
- Position Find( BinTree BST, ElementType X )
- {
- if(!BST)
- return NULL;
- else if(X> BST->Data)
- return Find(BST->Right,X);
- else if(X <BST->Data)
- return Find(BST->Left,X);
- else
- return BST;
- }
- Position FindMin( BinTree BST )
- {
- if(!BST)
- return NULL;
- while(BST->Left)
- BST = BST->Left;
- return BST;
- }
- Position FindMax( BinTree BST )
- {
- if(!BST)
- return NULL;
- while(BST->Right)
- BST = BST->Right;
- return BST;
- }
下面着重介绍 AVL 树
因为 BST 不是严格 O(logn) 的. 极端情况它有可能就退化成了一个链表. 为了提高效率, 于是就有了自平衡二叉树 (AVL). 我们再插入结点后通过旋转来保证二叉树的平衡 (所谓平衡, 其实就是让结点在左右子树分布的更均匀, 对于每一个子树的结点, 左右子树高度的绝对值的差不超过 1).
右单旋
对于 A 结点来说, 它的平衡被破坏了, 我们就用图中的旋转来使其再次平衡. 要注意的是, 右单旋的这个名字很有误导性的, 至少我一开始记错了! 右单旋并不是向右旋转, 而是新插入的结点在根结点的右子树的根结点的右子树上 (所以又叫 RR 旋转).
左单旋同理.
左单旋就是 LL 旋转.
下面介绍左右旋.
到了左右旋的情况下, 新结点的插入不再是像以往一样一路下去不改变方向了. 左右旋对应的情况是新结点插入了根结点的左子树的根节点的右子树上. 旋转时我们需要从后往前旋转, 即先旋转 B(根节点的左子树的根结点), 对于 B 来说, 结点插入在它的右子树上, 所以先对 B 结点进行右单旋. 最后对于 A 进行旋转. 对于 A 来说, 新结点插入在它的左子树上, 再对 A 进行左旋. 左右旋其实就是两种单旋的组合. 右左旋同理.
下图为右左旋.
- Code
- #include<algorithm>
- #include<cstdlib>
- using namespace std;
- struct AVLnode{
- int val;
- AVLnode* left;
- AVLnode* right;
- };
- typedef AVLnode* AVL;
- typedef AVL Poisition;
- AVL NewNode(int val)
- {
- AVL temp = (AVL)malloc(sizeof(AVLnode));
- temp->val = val;
- temp->left = temp->right = NULL;
- return temp;
- }
- AVL SingleLeftRotation(AVL tree)
- {
- AVL temp = tree->left;
- tree->left = temp->right;
- temp->right = tree;
- return temp;
- }
- AVL SingleRightRotation(AVL tree)
- {
- AVL temp = tree->right;
- tree->right = temp->left;
- temp->left = tree;
- return temp;
- }
- AVL LeftRightRotation(AVL tree)
- {
- tree->left = SingleRightRotation(tree->left);
- return SingleLeftRotation(tree);
- }
- AVL RightLeftRotation(AVL tree)
- {
- tree->right = SingleLeftRotation(tree->right);
- return SingleRightRotation(tree);
- }
- int GetHeight(AVL tree)// 给一个根结点, 计算树的高度
- {
- if(!tree)
- return 0;
- else
- return max(GetHeight(tree->left),GetHeight(tree->right))+1;
- }
- Poisition InsertNode(AVL tree,int v)
- {
- if(!tree){
- tree = NewNode(v);
- }
- else{
- if(v> tree->val){
- tree->right = InsertNode(tree->right,v);// 插入的地方在右边
- if(GetHeight(tree->right) - GetHeight(tree->left) == 2){// 失衡了
- if(v> tree->right->val)// 插入到右子树的右边, 右单旋
- tree = SingleRightRotation(tree);
- else if(v <tree->right->val)// 插入到右子树的左边, 右左旋
- tree = RightLeftRotation(tree);
- }
- }
- else if(v <tree->val){
- tree->left = InsertNode(tree->left,v);// 插入到左子树上
- if(GetHeight(tree->left) - GetHeight(tree->right) == 2){// 失衡了
- // 不建议对子树的高度进行储存, 现用现算, 否则不易更新
- if(v> tree->left->val)// 左子树的右子树上, 左右旋
- tree = LeftRightRotation(tree);
- else if(v <tree->left->val)// 左子树的左子树上, 左单旋
- tree = SingleLeftRotation(tree);
- }
- }
- }
- return tree;
- }
来源: http://www.bubuko.com/infodetail-3495812.html