二叉树某一节点的左旋
程序员文章站
2022-07-09 12:42:52
...
题目:树左旋
Description
给定二叉树的前序遍历,每个节点用一个字符表示,节点间存在一个空格,约定“#”代表空节点,请建立二叉树;
例如给定的前序遍历:a b d # # e f # # g h # # i # # c # #
给定二叉树的一个节点N,请对此节点进行左旋操作。
Input
输入数据有两行,第一行是二叉树的前序遍历,第二行是需要左旋的节点N
Output
请按照中序遍历输出左旋后的二叉树
Sample Input
a b d # # e f # # g h # # i # # c # #
b
Sample Output
d b f e h g i a c
难点分析:
对某一个节点的旋转通过指针实现并不困难,难点在于找到某一个节点的父节点,并实现与新的子树的连接。
代码如下:
Node.h
#pragma once
#include<iostream>
using namespace std;
typedef struct Node
{
char data;
struct Node* Left;
struct Node* Right;
Node();
};
typedef struct Node* ptr;
Node.cpp
#include "Node.h"
Node::Node() {
Left = NULL;
Right = NULL;
}
Tree.h
#pragma once
#include"Node.h"
class Tree
{
public:
Tree();
ptr root;
void Build_tree(ptr& aroot, string& s, int& index);
void Print();
void RotateL(ptr& aroot);
//bool isbalance(ptr aroot);
ptr search_for_node(ptr aroot, char target);
ptr search_for_parent(ptr aroot, char target);
//int Getvec(vector<int>v1, vector<int>v2);
private:
void recursive_print(ptr& aroot);
//int Getheight(ptr& aroot);
};
Tree.cpp
#include "Tree.h"
Tree::Tree()
{
root = NULL;
}
void Tree::Build_tree(ptr& aroot, string& s, int& index)
{
int length = s.size() - 1;
if (index <= length)
{
if (s[index] == ' ')
Build_tree(aroot, s, ++index);
else if (s[index] == '#')
aroot = NULL;
else
{
aroot = new Node;
aroot->data = s[index];
Build_tree(aroot->Left, s, ++index);
Build_tree(aroot->Right, s, ++index);
}
}
}
void Tree::Print()
{
return recursive_print(root);
}
void Tree::recursive_print(ptr& aroot)
{
if (aroot != NULL)
{
recursive_print(aroot->Left);
cout << aroot->data << " ";
recursive_print(aroot->Right);
}
}
void Tree::RotateL(ptr& aroot)
{
ptr sub=aroot;
aroot = sub->Right;
sub->Right=aroot->Left;
aroot->Left = sub;
}
ptr Tree::search_for_node(ptr aroot, char target)
{
if (aroot->data == target)
{
return aroot;
}
ptr temp = NULL;
if (aroot->Left != NULL) {
if (aroot->Left->data == target)
return aroot->Left;
else
{
temp = search_for_node(aroot->Left,target);
if (temp != NULL)
return temp;
}
}
if (aroot->Right!= NULL) {
if (aroot->Right->data == target)
return aroot->Right;
else
temp = search_for_node(aroot->Right,target);
return temp;
}
return NULL;
}
ptr Tree::search_for_parent(ptr aroot, char target)
{
ptr p;
if (aroot->Left->data == target || aroot->Right->data == target)
return aroot;
else
{
p = search_for_node(aroot->Left, target);
if (p != NULL)
search_for_parent(aroot->Left, target);
else
search_for_parent(aroot->Right, target);
}
}
main.cpp
#include"Tree.h"
#include<string>
int main()
{
string S;
getline(cin, S);
char ch;
cin >> ch;
Tree t;
int m = 0;
t.Build_tree(t.root, S, m);
ptr p;
p = t.search_for_node(t.root, ch);
ptr q;
q = t.search_for_parent(t.root, ch);
t.RotateL(p);
q->Left = p;
t.Print();
return 0;
}
上一篇: 二叉树节点为某一值的路径
下一篇: logstash详解