大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 交换二叉树的左右子树——非递归方式

交换二叉树的左右子树——非递归方式


[摘要]本文主要是对交换二叉树的左右子树——非递归方式的讲解,希望对大家学习交换二叉树的左右子树——非递归方式有所帮助。

  这是华为的一道机试题,其实并不难,不让用递归可以用栈来解决,具体的代码如下:

  #include <STDIO.H>

  #include <STDLIB.H>

  struct node{

  char data ;

  struct node* left ;

  struct node* right ;

  };

  struct tree{

  struct node* root ;

  };

  void tree_create( struct node** node){

  char data;

  scanf("%c" , &data);

  if(data == '#' ){

  *node = NULL;

  }

  else{

  *node = ( struct node*)malloc(sizeof( struct node));

  (*node)-> data = data;

  tree_create(&(*node)-> left);

  tree_create(&(*node)-> right);

  }

  }

  void tree_destory( struct node** node){

  if(*node != NULL){

  tree_destory(&(*node)-> left);

  tree_destory(&(*node)-> right);

  free(node);

  }

  }

  void tree_first( struct node* node){

  if(node == NULL)

  return;

  printf("%c " , node->data);

  tree_first(node-> left);

  tree_first(node-> right);

  }

  static struct node* stack[5] = {0};

  static int pos = -1;

  void push( struct node* node){

  stack[++pos] = node;

  }

  void pop(){

  --pos;

  }

  int empty(){

  return pos == -1;

  }

  struct node* top(){

  return stack[pos];

  }

  void exchange( struct node* node){

  struct node* tnode = node;

  struct node* tmp = NULL;

  if(node == NULL)

  return;

  while(1){

  tmp = tnode-> left;

  tnode-> left = tnode->right ;

  tnode-> right = tmp;

  if(tnode->right ){

  push(tnode-> right);

  }

 

  if(tnode->left ){

  tnode = tnode->left;

  }

  else{

  if(!empty()){

  tnode = top();

  pop();

  }

  else{

  break;

  }

  }

  }

  }

  int main(){

  struct tree tree;

  tree_create(&tree. root);

  printf("交换前的先序遍历:" );

  tree_first(tree. root);

  printf("\n" );

  exchange(tree. root);

  printf("交换后的先序遍历:" );

  tree_first(tree. root);

  printf("\n" );

  tree_destory(&tree. root);

  return 0;

  }


相关Java技巧推荐

    暂时没有相关推荐



    相关评论