二叉树数组转in-order二叉树数组
Binary tree array to in-order Binary tree array
我正在解决 HackerEarth 问题之一。问题陈述如下,
给定一棵具有 N 个节点的完整二叉树,并且每个节点都有一个不同的整数 ai,求将二叉树转换为的最小交换次数二叉搜索树。在一次交换中,您可以 select 任意两个节点并交换它们的值。
你将得到二叉树的数组表示。树的根将在 a[1] 根的左 child 将在 a[2] 和右 [=根的 34=] 将位于 a3。数组位置 k 节点的左 child 将在节点的 a[2*k] 和右 child在数组位置 k 将在 a[2*k+1].
问题是如何将给定数组转换为 tree.I 的 in-order 数组,尝试了以下代码。在网上我没有找到任何 link.
static void inOrderArr(int destIndex,int index, int[] source, int[] dest) {
int leftIndex = (index ) * 2;
int rightIndex = (((index ) * 2) + 1);
if(leftIndex<source.length){
inOrderArr(destIndex,leftIndex, source,dest);
}
System.out.println(index);
dest[destIndex++] = source[index-1];
if(rightIndex<source.length){
inOrderArr(destIndex,rightIndex, source,dest);
}
}
试试这个!
思路是利用二叉搜索树的中序遍历是它们的递增顺序value.So,求出二叉树的中序遍历存入数组,尝试对数组。
这是 c 中的代码,用于将给定数组转换为树的有序数组。
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;
while (!done)
{
/* Reach the left most tNode of the current tNode */
if(current != NULL)
{
/* place pointer to a tree node on the stack before traversing
the node's left subtree */
push(&s, current);
current = current->left;
}
/* backtrack from the empty subtree and visit the tNode
at the top of the stack; however, if the stack is empty,
you are done */
else
{
if (!isEmpty(s))
{
current = pop(&s);
printf("%d ", current->data);
/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
current = current->right;
}
else
done = 1;
}
} /* end of while */
}
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}
/* put in the data */
new_tNode->t = t;
/* link the old list off the new tNode */
new_tNode->next = (*top_ref);
/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;
/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;
return(tNode);
}
/* Driver program to test above functions*/
int main()
{
struct tNode *root = newtNode(5);
root->left = newtNode(6);
root->right = newtNode(7);
root->left->left = newtNode(8);
root->left->right = newtNode(9);
root->right->left = newtNode(10);
root->right->right= newtNode(11);
inOrder(root);
getchar();
return 0;
}
我尝试了以下解决方案并且有效。
private static void inorderTraversal(int array[], int pos, Node[] nodes) {
if (pos >= array.length) {
return;
}
inorderTraversal(array, 2 * pos + 1, nodes);
nodes[Node.count] = new Node(array[pos], Node.count);
Node.count++;
inorderTraversal(array, 2 * pos + 2, nodes);
}
这里是节点类型声明
static private class Node implements Comparable<Node> {
private static int count = 0;
public Node(int value) {
this.value = value;
}
public Node(int value, int position) {
this(value);
this.position = position;
}
private int value;
private int position;
private boolean visited;
public boolean isVisited() {
return visited;
}
public void markVisited() {
visited = true;
}
@Override
public int compareTo(Node o) {
if (this.value >= o.value) {
return 1;
}
return -1;
}
}
我正在解决 HackerEarth 问题之一。问题陈述如下,
给定一棵具有 N 个节点的完整二叉树,并且每个节点都有一个不同的整数 ai,求将二叉树转换为的最小交换次数二叉搜索树。在一次交换中,您可以 select 任意两个节点并交换它们的值。
你将得到二叉树的数组表示。树的根将在 a[1] 根的左 child 将在 a[2] 和右 [=根的 34=] 将位于 a3。数组位置 k 节点的左 child 将在节点的 a[2*k] 和右 child在数组位置 k 将在 a[2*k+1].
问题是如何将给定数组转换为 tree.I 的 in-order 数组,尝试了以下代码。在网上我没有找到任何 link.
static void inOrderArr(int destIndex,int index, int[] source, int[] dest) {
int leftIndex = (index ) * 2;
int rightIndex = (((index ) * 2) + 1);
if(leftIndex<source.length){
inOrderArr(destIndex,leftIndex, source,dest);
}
System.out.println(index);
dest[destIndex++] = source[index-1];
if(rightIndex<source.length){
inOrderArr(destIndex,rightIndex, source,dest);
}
}
试试这个!
思路是利用二叉搜索树的中序遍历是它们的递增顺序value.So,求出二叉树的中序遍历存入数组,尝试对数组。
这是 c 中的代码,用于将给定数组转换为树的有序数组。
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;
while (!done)
{
/* Reach the left most tNode of the current tNode */
if(current != NULL)
{
/* place pointer to a tree node on the stack before traversing
the node's left subtree */
push(&s, current);
current = current->left;
}
/* backtrack from the empty subtree and visit the tNode
at the top of the stack; however, if the stack is empty,
you are done */
else
{
if (!isEmpty(s))
{
current = pop(&s);
printf("%d ", current->data);
/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
current = current->right;
}
else
done = 1;
}
} /* end of while */
}
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}
/* put in the data */
new_tNode->t = t;
/* link the old list off the new tNode */
new_tNode->next = (*top_ref);
/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;
/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;
return(tNode);
}
/* Driver program to test above functions*/
int main()
{
struct tNode *root = newtNode(5);
root->left = newtNode(6);
root->right = newtNode(7);
root->left->left = newtNode(8);
root->left->right = newtNode(9);
root->right->left = newtNode(10);
root->right->right= newtNode(11);
inOrder(root);
getchar();
return 0;
}
我尝试了以下解决方案并且有效。
private static void inorderTraversal(int array[], int pos, Node[] nodes) {
if (pos >= array.length) {
return;
}
inorderTraversal(array, 2 * pos + 1, nodes);
nodes[Node.count] = new Node(array[pos], Node.count);
Node.count++;
inorderTraversal(array, 2 * pos + 2, nodes);
}
这里是节点类型声明
static private class Node implements Comparable<Node> {
private static int count = 0;
public Node(int value) {
this.value = value;
}
public Node(int value, int position) {
this(value);
this.position = position;
}
private int value;
private int position;
private boolean visited;
public boolean isVisited() {
return visited;
}
public void markVisited() {
visited = true;
}
@Override
public int compareTo(Node o) {
if (this.value >= o.value) {
return 1;
}
return -1;
}
}