递归和非递归的方法往二叉排序树中插入新的节点

今天在回寝室的路上同学跟我讨论往二叉排序树中插入新的节点，我一想这不很简单吗，回到寝室立马写了个程序让他看，他一看说我要的是递归的方法。我一想递归的话，每次调用函数不都插入了一个新节点，那不建立成一颗二叉排序树了吗，不是插入一个节点。我又看了一下非递归的方法，发现当根为空时直接将新建的节点p赋给根节点t,这主要用到了引用赋值的原理，对，我可以利用引用的原理。(1)当根为空时,直接将根 t 赋值为新建的节点指针返回 (2) 当根节点的值大于要插入节点的值时，递归的将新建的节点插入到根节点的左子树的合适位置（3）否则,递归的将新建的节点插入到根节点的右子树的合适位置。

具体代码如下:

// 二叉树的建立.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

using namespace std;

//定义二叉排序树的节点
typedef struct Node
{
   int data;
   struct Node * lchild;//左孩子
   struct Node * rchild;//右孩子
}Node,* PNode;

PNode T=NULL;//二叉排序树的根节点

//中序遍历二叉树
void MidSequence(PNode t)
{
   if(t!=NULL)
   {
      MidSequence(t->lchild);
	  cout<<t->data<<" ";
	  MidSequence(t->rchild);
   }
}

//往二叉排序树中插入一个新节点(非递归实现)
void  CreateBSortTree(PNode & t,int data)
{
   //建立一个新节点
   PNode p=(PNode)malloc(sizeof(Node));
   p->data=data;
   p->lchild=NULL;
   p->rchild=NULL;

   if(t==NULL)
   {
      t=p;
	  return;
   }

   PNode q=t,parent;
   do{
    parent=q;
    if(parent->data>data)
		q=parent->lchild;
	else
		q=parent->rchild;
   }while(q!=NULL);
   if(parent->data>data)
      parent->lchild=p;
   else
	   parent->rchild=p;
}

//往二叉排序树中插入一个新节点(递归实现)
void  CreateBSortTree2(PNode & t,int data)
{
  if(t==NULL)
  {
	  //建立一个新节点
	  PNode p=(PNode)malloc(sizeof(Node));
      p->data=data;
      p->lchild=NULL;
      p->rchild=NULL;
	  t=p;
	  return;
  }
  else if(t->data>data)
     CreateBSortTree2(t->lchild,data);
  else
     CreateBSortTree2(t->rchild,data);
}

//测试
int _tmain(int argc, _TCHAR* argv[])
{
	int a[]={0,5,8,4,2,3,10};
	int len=sizeof(a)/sizeof(int);
	for(int i=0;i<len;i++)
	{
	  CreateBSortTree2(T,a[i]);
	}
    MidSequence(T);
	system("PAUSE");
	return 0;
}

递归和非递归的方法往二叉排序树中插入新的节点

相关推荐