注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Aspirer's blog

停止维护,新博客地址:http://aspirer.wang/

 
 
 

日志

 
 

二叉树  

2009-08-19 11:56:10|  分类: 学习心得 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

二叉树 - aspirer - Aspirers blog

#include <iostream>
#include <cstdio>

using namespace std;


typedef struct node
{
 int data;
 struct node *leftchild;
 struct node *rightchild;
}Node;

typedef struct BinaryTree
{
 Node *root;
 int size;
}BinTree;

void InsertNode(Node *root, int data);
void Destroy(Node *root);
Node *GetParentNode(Node *root, Node *curr);
Node *GetRightestNode(Node *curr);


BinTree *CreatTree(BinTree *tree)
{
 int data;
 Node *tmp;
 //Node *s;
 
 if (NULL == tree)
 {
  tree = (BinTree *)malloc(sizeof(BinTree));
  tree->root = NULL;
  tree->size = 0;
 }

 if (tree->size != 0)
 {
  Destroy(tree->root);
  tree->size = 0;
 }

 cout << "input node data.\n";
 //scanf("%d", &data);
 //fflush(stdin);
 while ((cin >> data) && (data != 0))
 //while (data != 0)
 {
  if (NULL == tree->root)
  {
   tmp = (Node *)malloc(sizeof(Node));
   tmp->data = data;
   tmp->leftchild = NULL;
   tmp->rightchild = NULL;
   tree->root = tmp;
  }
  else
  {
   InsertNode(tree->root, data);
  }
  tree->size++;
  cout << "input node data." << endl;
  //fflush(stdin);
  //data = 0;
  //cin >> data;
  //scanf("%d", &data);
  printf("Data : %d\n", data);
  //cout << data << endl;
    // cout << "input node data." << endl;
  //fflush(stdin);
 }
 return tree;
}

void InsertNode(Node *root, int data)
{
 Node *tmp = NULL;

 if (data > root->data)
 {
  if (NULL == root->rightchild)
  {
   tmp = (Node *)malloc(sizeof(Node));
   tmp->data = data;
   tmp->leftchild = NULL;
   tmp->rightchild = NULL;
   root->rightchild = tmp;
   return;
  }
  else
  {
   InsertNode(root->rightchild, data);
  }
 }
 else if (data < root->data)
 {
  if (NULL == root->leftchild)
  {
   tmp = (Node *)malloc(sizeof(Node));
   tmp->data = data;
   tmp->leftchild = NULL;
   tmp->rightchild = NULL;
   root->leftchild = tmp;
   return;
  }
  else
  {
   InsertNode(root->leftchild, data);
  }
 }
 else
 {
  cout << "==" << endl;
 }
}

Node* RemoveNode(Node *root, Node *curr, int data)
{
 Node *rightest, *tmp;
 if (NULL == root)
 {
  return NULL;
 }

 if (NULL == curr)

 {

    return root;

 }

 if (data < curr->data)
 {  
  RemoveNode(root, curr->leftchild, data);
 }
 else if (data > curr->data)
 {  
  RemoveNode(root, curr->rightchild, data);
 }
 //如果找到要删除的节点
 else
 {
  //如果要删除的节点有左子树
  if (curr->leftchild)
  {
   //找到其左子树的最右端叶子节点
   rightest = GetRightestNode(curr->leftchild);
   //将最右端的叶子节点数据复制到要删除的节点
   curr->data = rightest->data;
   //删除最右端节点(递归调用)
   RemoveNode(root, rightest, rightest->data);
  }
  //如果要删除的节点没有左子树
  //则将其右子树代替要删除的节点
  else
  {
   //如果要删除的是根节点且没有左子树
   if (curr == root)
   {
    root = root->rightchild;
    free(curr);    
   }
   else
   {
    //找到要删除节点的父节点
    tmp = GetParentNode(root, curr);
    if (tmp->leftchild == curr)
    {
     tmp->leftchild = curr->rightchild;
    }
    else
    {
     tmp->rightchild = curr->rightchild;
    }
    free(curr);
   }
  }
  return root;
 }
}

Node *GetParentNode(Node *root, Node *curr)
{
 while (root && root->rightchild != curr && root->leftchild != curr)
 {
  if (root->rightchild->data > curr->data)
  {
   root = root->leftchild;
  }
  else
  {
   root = root->rightchild;
  }
 }
 return root;
}

Node *GetRightestNode(Node *curr)
{
 while (curr->rightchild)
 {
  curr = curr->rightchild;
 }
 return curr;
}

void PrintTree(Node *root)
{
 if (root)
 {
  cout << root->data << "\t";
  PrintTree(root->leftchild);
  PrintTree(root->rightchild);  
 } 
 
}

int SearchNode(BinTree *tree, int data)
{
 return 0;
}

void Destroy(Node *root)
{
 if (root)
 {
  Destroy(root->leftchild);
  Destroy(root->rightchild);
  free(root);
  root = NULL;
 }
}

int Depth(Node *root)
{
    int ld, rd, max;
    if (root)
    {
             ld = Depth(root->leftchild);
             rd = Depth(root->rightchild);
             max = ld > rd ? ld : rd;
             return max + 1;
    }
    else
    {
             return 0;
    }
}


int main()
{
 
 BinTree *tree = (BinTree *)malloc(sizeof(BinTree));
 tree->root = NULL;
 //tree->root->data = 10;
 //tree->root->leftchild = NULL;
 //tree->root->rightchild = NULL;
 tree->size = 0;

 CreatTree(tree);
 PrintTree(tree->root);
 cout << endl;

 tree->root = RemoveNode(tree->root, tree->root, 5);
 tree->size--;
 PrintTree(tree->root);
 cout << endl;

 InsertNode(tree->root, 5);
 tree->size++;
 PrintTree(tree->root);
 cout << endl;

 cout << Depth(tree->root) << endl;

 Destroy(tree->root);
 //tree->size = 0;
 free(tree);

 tree = NULL;

 return 0;
}

  评论这张
 
阅读(373)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018