二叉树增删改查方法定义在哪里

1. 如何定义二叉树

Treenode * SearchBST( Treenode *root, int target)
{
if (root != Null){
if (target < root->data)
root = SearchBST(root->lchild, target);
if (target > root->data)
root = SearchBST(root->rchild, target);
return root; }
}

2. 二叉排序树 删除结点 定义

二叉排序树节点的删除有2种方法
你上面我没有看懂你的
但是我讲的你肯定能听懂
假设要删除的是节点p,pl为p的左子树pr为p的右子树
a:前驱后继法
首先中序遍历二叉树得到一个序列你的例子是51 20 48 89 112 56 得到89的后继是112，前驱是48.
这下就证明书上的没有错了。这里我用后继的方法用112替代根节点，此时原来根节点的左子树仍要满足二叉排序树的性质，所以要接在112的后面。
总的来说就是删除一个节点p，用前驱（后继）取代p，而前驱（后继）的右子树就取代p的位置（！！此时后继没有左子树，因为假如后继有左子树的话那么后继就是p的左子树了啊，而不是p要是存在左右子树的话，那么后继的兄弟右子树就不要变动了）p的子树不变位置，依然接在新的节点后面，作为其左右子树。
b：左右子树替代法
删除节点p，我这里用左子树法，首先用48取代89，那么89的右子树（包含112 56）就接在新的节点48后面作为其右子树，依然满足二叉排序树的特征。
总的来说，删除节点p，用它的右（左）子树替代节点p，然后将p的左（右）子树作为p左（右）子树的接在右（左）子树的最左（右）节点后面作为左（右）子树即可。你这个例子用右子树替代的话，最左节点是56。
我是个学生，以后多多交流，我的QQ是314251898
谢谢。

3. 二叉树的基本操作

//创建二叉树,请输入节点的总数量:7
//请连续输入7个节点的数据:4261357
//前序遍历序列:4213657
//中序遍历序列:1234567
//后序遍历序列:1325764
//二叉树的节点一共有7个,度为1的节点有0个,度为2的节点有3个,
//叶子节点有4个,数据值的最大值是7,最小值是1
//
//对应的二叉树:
//
//4
///
//26
////
//1357

#include"stdio.h"
#include"stdlib.h"
structTree
{
intdata;
structTree*left;
structTree*right;
};
typedefstructTreeTreeNode;
typedefTreeNode*Bitree;

typedefstructstack_node//栈的结构体
{
Bitreebt;
	structstack_node*next;
}stack_list,*stack_link;

BitreeinsertNode(Bitreeroot,intdata)//插入结点
{
Bitreenewnode;
Bitreecurrent;
Bitreeback;
newnode=(Bitree)malloc(sizeof(TreeNode));
if(newnode==NULL)
{
printf("
动态分配内存出错.
");
exit(1);
}
newnode->data=data;
newnode->left=NULL;
newnode->right=NULL;
if(root==NULL)
{
returnnewnode;
}
else
{
current=root;
while(current!=NULL)
{
back=current;
if(current->data>data)
current=current->left;
else
current=current->right;
}
if(back->data>data)
back->left=newnode;
else
back->right=newnode;
}
returnroot;
}

BitreecreateTree()//创建二叉树(非递归)
{
Bitreeroot=NULL;
intlen;
intdata;
inti;
printf("创建二叉树,请输入节点的总数量:");
scanf("%d",&len);
printf("请连续输入%d个节点的数据:",len);
for(i=0;i<len;i++)
{
scanf("%d",&data);
root=insertNode(root,data);
}
returnroot;
}


voidpreOrder(Bitreeptr)//先序遍历(递归法)
{
if(ptr!=NULL)
{
printf("%d",ptr->data);
preOrder(ptr->left);
preOrder(ptr->right);
}
}

voidinOrder(Bitreeptr)//中序遍历(递归法)
{
if(ptr!=NULL)
{
inOrder(ptr->left);
printf("%d",ptr->data);
inOrder(ptr->right);
}
}

voidpostOrder(Bitreeptr)//后序遍历(递归法)
{
if(ptr!=NULL)
{
postOrder(ptr->left);
postOrder(ptr->right);
printf("%d",ptr->data);
}
}

//检查[栈]是否是空
intisEmpty(stack_linkstack)
{
	if(stack==NULL)
{
return1;
}
else
{
return0;
}
}

//入栈
stack_linkpush(stack_linkstack,Bitreebt)
{
	stack_linknew_node;

	new_node=(stack_link)malloc(sizeof(stack_list));
	if(!new_node)
	{
		returnNULL;
	}
	new_node->bt=bt;
	new_node->next=stack;
	stack=new_node;
	returnstack;
}

//出栈
stack_linkpop(stack_linkstack,Bitree*bt)
{
	stack_linktop;

	if(isEmpty(stack))
	{
		*bt=NULL;
		returnNULL;
	}
	top=stack;
	*bt=top->bt;
	stack=top->next;
	free(top);
	returnstack;
}
//统计节点(非递归)
voidreportByStack(Bitreebt,int*pTotal,int*pCount0,int*pCount1,
int*pCount2,int*pMaxValue,int*pMinValue)
{
Bitreep=NULL;
stack_linkoneStack=NULL;
inttotal=0;
intcount0=0,count1=0,count2=0;
intmaxValue=0,minValue=0;

if(bt==NULL)
{
return;
}

p=bt;//当前二叉树的节点
minValue=p->data;
maxValue=minValue;
while(p!=NULL)
{
if(minValue>p->data)
{
minValue=p->data;
}
if(maxValue<p->data)
{
maxValue=p->data;
}
total++;//total=count0+count1+count2
if(p->right==NULL&&p->left==NULL)//叶子
{
count0++;
}
elseif(p->right!=NULL&&p->left!=NULL)//度2
{
count2++;
}
else//度1
{
count1++;
}
if(p->right!=NULL)//如果有右子树,马上入栈
{
oneStack=push(oneStack,p->right);
}
if(p->left!=NULL)//如果有左子树,设为当前节点
{
p=p->left;
}
else
{
oneStack=pop(oneStack,&p);
if(p==NULL)
{
break;
}
}
}
*pTotal=total;
*pCount0=count0;
*pCount1=count1;
*pCount2=count2;
*pMaxValue=maxValue;
*pMinValue=minValue;
}

intmain()
{
Bitreeroot=NULL;
inttotal=0;
intcount0=0,count1=0,count2=0;
intmaxValue=0,minValue=0;

root=createTree();//创建二叉树

printf("
前序遍历序列:");
preOrder(root);
printf("
中序遍历序列:");
inOrder(root);
printf("
后序遍历序列:");
postOrder(root);

//统计节点(非递归)
reportByStack(root,&total,&count0,&count1,&count2,&maxValue,&minValue);
printf("
二叉树的节点一共有%d个,度为1的节点有%d个,度为2的节点有%d个,
",
total,count1,count2);
printf("叶子节点有%d个,数据值的最大值是%d,最小值是%d",
count0,maxValue,minValue);

printf("
");
return0;
}

4. 二叉树的实现（定义，创建，遍历），求救

以前编的程序，有前序遍历的非递归
#include<iostream>
#include<list>
using
namespace
std;
class
binarytreenode
//树的节点定义
{
public:
int
number;
binarytreenode
*left;
binarytreenode
*right;
binarytreenode(int
a=0,binarytreenode
*first=0,binarytreenode
*second=0)
{
number=a;
left=first;
right=second;
}
};
class
stack
//栈的定义
{
private:
list<binarytreenode
*>
lst;
public:
stack()
{};
void
push(binarytreenode
*el)
{
lst.push_back(el);
}
binarytreenode
*pop()
{
binarytreenode
*el=lst.back();
lst.pop_back();
return
el;
}
bool
isEmpty()
{
return
lst.empty();
}
};
class
binarytree
//树的定义
{
public:
binarytreenode
*root;
binarytree(binarytreenode
*a=0)
{
root=a;
}
void
insert(int
a);
void
preorder();
};
void
binarytree::insert(int
a)
{
binarytreenode
*temp;
temp=new
binarytreenode;
temp->number=a;
binarytreenode
*work=root;
binarytreenode
*prep=root;
if(root==0)
root=temp;
else
{
while(work)
{
prep=work;
if((temp->number)<(work->number))
work=work->left;
else
work=work->right;
}
if((temp->number)<(prep->number))
prep->left=temp;
else
prep->right=temp;
}
}
void
binarytree::preorder()
{
binarytreenode
*p=root;
stack
s;
s.push(p);
while(!s.isEmpty())
{
p=s.pop();
cout<<p->number<<"
";
if(p->right!=0)
s.push(p->right);
if(p->left!=0)
s.push(p->left);
}
}
void
main()
{
binarytree
tr;
cout<<"请输入数字构建二叉搜索树,输入-1结束";
int
temp;
cin>>temp;
while(temp!=-1)
{
tr.insert(temp);
cout<<"请输入数字,输入-1结束";
cin>>temp;
}
tr.preorder();
}

5. 二叉树的基本操作

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//基于先序遍历算法创建二叉树
//要求输入先序序列，其中加入虚结点"#"以示空指针的位置
BinTree CreatBinTree(void){
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//先序遍历
void Preorder(BinTree T){
if(T){
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//中序遍历
void Inorder(BinTree T){
if(T){
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//后序遍历
void Postorder(BinTree T){
if(T){
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法
int TreeDepth(BinTree T){
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//主函数
void main(){
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do{ //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-4）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
}while(i!=0);
}
//按层遍历
Levelorder( BinTNode *root){
BinTNode * q[Max]; //定义BinTNode类型的队列 用于存放节点 队列长最大为20个元素
int front=0,rear=0; //初始化队列为空
BinTNode *p; //临时节点指针
if(root!=NULL){ //将根节点进队
rear=(rear+1)%Max;
q[rear]=root;
}
while(front!=rear){
front=(front+1)%Max;
p=q[front]; //删除队首的元素 让两个节点（左右节点）孤立
printf("%c",p->data); //输出队列首元素的值
if(p->left!=null){ //如果存在左孩子节点，则左孩子节点进入队列
rear=(rear+1)%Max;
q[rear]=p->left;
}
if(p->right!=null){ //如果存在右孩子节点，则右孩子节点进入队列
rear=(rear+1)%Max;
q[rear]=p->right;
}
}
}

6. JAVA中怎么样在文件中存储二叉树的信息并读取出来！例如实现简单的词典功能（增删改查）~

id
name
parentId //是0的时候，表示顶层的。

7. 二叉树基本操作

试试，挺好的！还有菜单！

#include <iostream>
using namespace std;
struct Node
{
char data;
Node *left;
Node *right;
}*BiTree;

class Tree
{
public:
void Setroot();//设置二叉树的根节点
void CreateTree(Node*); //先序递归创建二叉树函数
void DeleteTree(Node*);//二叉树的销毁函数
void PostOrderTraverse(Node*);//后续递归遍历二叉树函数
void InOrderTraverse(Node*);//中序非递归遍历二叉树函数
void LevelOrder(Node *);//层次遍历二叉树函数
void leaves1(Node *);//输出二叉树的叶子节点函数
void leaves2(Node *);//输出二叉树的二叉节点函数
void leaves3(Node *);//输出二叉树的一叉节点函数
//int Showleaves(Node *);//输出二叉树的叶子节点个数函数
int Depthoftree(Node *);//计算二叉树的深度函数
bool Iscomplete(Node *);//判断二叉树是否为完全二叉树函数
bool Isp(Node *);//判断二叉树是否已初始化
~Tree(){DeleteTree(root);}//Tree的析构函数
static Node *root;//定义二叉树的根节点为静态变量
};
Node* Tree::root=0;//初始化二叉树的根节点
void Tree::Setroot()//设置二叉树的根节点
{
cout<<"输入树的根节点(如果为空输入#):\t";
root=new Node;
cin>>root->data;
CreateTree(root);//调用CreateTree()函数生成二叉树
}
bool Tree::Isp (Node *p=root)//判断二叉树是否已存在
{
if(p){return true;}
else return false;
}

void Tree::CreateTree(Node *p)//先序递归创建二叉树
{
if(p)
{
char x,y; Node *q;
cout<<"输入节点"<<p->data<<"的左孩子和右孩子:\t";
cin>>x>>y;
if(x=='#')
p->left=0;
else
{
q=new Node;
q->data=x;
p->left=q;
}
if(y=='#')
p->right=0;
else
{
q=new Node;
q->data=y;
p->right=q;
}
CreateTree(p->left);
CreateTree(p->right);
}
}

void Tree::InOrderTraverse(Node *p=root)//中序非递归遍历二叉树
{
Node *q;
Node *stack[100];
int top=0;
q=p;
if(p)
{
while(q||top!=0)
{
while(q)
{
stack[top++]=q;
q=q->left ;
}
q=stack[--top];
cout<<q->data <<" ";
q=q->right ;
}
}
else{cout<<"请先建立二叉树!!!"<<endl;}
}

void Tree::LevelOrder(Node *p=root)//层次遍历二叉树
{
Node stack[100];//设置堆栈
int front=0,rear=0;
Node q;
if(p)
{
stack[rear]=*p;
rear=(rear+1)%100;
}
while(front!=rear)
{
p=&stack[front];
front=(front+1)%100;
cout<<p->data<<" ";
if(p->left )
{
stack[rear]=*p->left ;
rear=(rear+1)%100;
}
if(p->right )
{
stack[rear]=*p->right ;
rear=(rear+1)%100;
}
}
}

void Tree::PostOrderTraverse(Node *p=root)//后续递归遍历二叉树
{
if(p)
{
PostOrderTraverse(p->left);
PostOrderTraverse(p->right);
cout<<p->data<<" ";
}
}

void Tree::DeleteTree(Node *p=root)//销毁二叉树
{
if(p)
{
DeleteTree(p->left);
DeleteTree(p->right);
delete p;
}
}

int Tree::Depthoftree (Node *p=root)//计算二叉树的深度
{
if(p)
{
int h1=Depthoftree(p->left );
int h2=Depthoftree(p->right );
return(1+(h1>h2?h1:h2));
}
else return 0;
}

/*int Tree::Showleaves (Node *p=root)//计算二叉树的叶子结点个数
{
int rnum,lnum;
int i=0;
if(p)
{
if((p->left ==NULL)||(p->right==NULL))
{
return 1;
}
else
{
rnum=Showleaves(p->left);
lnum=Showleaves(p->right);
return rnum+lnum;
}
}
else return 0;
}*/

void Tree::leaves1 (Node *p=root)//输出二叉树的叶子节点
{
if(p)
{
if((p->left ==NULL)&&(p->right==NULL))
{
cout<<p->data <<" ";
}
leaves1(p->left );
leaves1(p->right );
}
}
void Tree::leaves2 (Node *p=root)//输出二叉树的二叉节点
{
if(p)
{
if((p->left !=NULL)&&(p->right!=NULL))
{
cout<<p->data <<" ";
}
leaves2(p->left );
leaves2(p->right );
}
}
void Tree::leaves3(Node *p=root)//输出二叉树的一叉节点
{
if(p)
{
if(((p->left !=NULL)&&(p->right==NULL))||((p->left==NULL)&&(p->right!=NULL)))
{
cout<<p->data <<" ";
}
leaves3(p->left );
leaves3(p->right );
}
}
bool Tree::Iscomplete(Node *p=root)//判断二叉树是否为完全二叉树
{
Node stack[100],*q,*r;/*定义队列*/
int front=0,rear=0;
if(p)
{
stack[rear]=*p;
rear=(rear+1)%100;
}
/*此while的作用是在根节点在队内的初始情况下开始*/
/*按层次遍历二叉树*/
/*只遍历左右子树都有的节点 while结束时 p指向第一个例外节点*/
while(rear!=front)
{
q=&stack[front];
front=(front+1)%100;
if((rear+1)%100!=front&&p->left!=NULL&&p->right!=NULL) /*当队不满，*/
{
stack[rear]=*p->left;
rear=(rear+1)%100;
stack[rear]=*p->right;
rear=(rear+1)%100;

}
else break;
}
/*经前面的while，p肯定指向第一个没有双子的节点*/
/*此时又分四种情况*/
if(p->left==NULL&&p->right!=NULL)return false; /*第一种:有右无左 肯定不是完全二叉树*/
else if(p->left!=NULL&&(p->left->left!=NULL||p->left->right!=NULL))
return false; /*第二种:有左无右但左子树还有子树 排除*/
/*第三种:有左无右 左也无子,*/
/*但在继续按层次遍历过程中*/
/*发现后来的某个节点有子树,排除*/
else
{
while(rear!=front)
{
q=&stack[front];
front=(front+1)%100;
if(p->left!=NULL||p->right!=NULL) return false;
}
} /*经过层层筛选,剩下的就是真金*/
//return true;
}

void main()
{
int /*leave=0,*/depth=0;
bool key,t=true;//key接受Isp()的返回值；t接受Iscomplete()的返回值
Tree tree;
int select=0;
while(select!=8)
{
cout<<endl;
cout<<" ————————————————————————"<<endl;
cout<<" ╭————————请选择操作号————————╮"<<endl;
cout<<" ∣ ∣"<<endl;
cout<<" ├——————————————————————┤"<<endl;
cout<<" ∣ 1.建立一棵二叉树（先序） ∣"<<endl;
cout<<" ∣ 2.递归后序遍历二叉树 ∣"<<endl;
cout<<" ∣ 3.中序非递归遍历二叉树 ∣"<<endl;
cout<<" ∣ 4.层次遍历二叉树 ∣"<<endl;
cout<<" ∣ 5.列出该树的叶子节点、二叉节点、一叉节点∣"<<endl;
cout<<" ∣ 6.求出树的深度 ∣"<<endl;
cout<<" ∣ 7.判断该树是否是完全二叉树 ∣"<<endl;
cout<<" ∣ 8.退出 ∣"<<endl;
cout<<" ╰——————————————————————╯"<<endl;
cout<<" ————————————————————————"<<endl;
cout<<" 请选择您要服务的类别: " ;
cin>>select;
switch(select)
{
case 1:
tree.DeleteTree ();
tree.Setroot (); break;
case 2:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树******!!!"<<endl;break;}
cout<<"***************************"<<endl;
cout<<"树的后序遍历结果为:";
tree.PostOrderTraverse ();
cout<<endl<<"***************************"<<endl;break;
case 3:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树******!!!"<<endl;break;}
cout<<"***************************"<<endl;
cout<<"树的中序遍历结果为:";
tree.InOrderTraverse ();
cout<<endl<<"***************************"<<endl;break;
case 4:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树******!!!"<<endl;break;}
cout<<"***************************"<<endl;
cout<<"树的层次遍历结果为:";
tree.LevelOrder ();
cout<<endl<<"***************************"<<endl;break;
case 5:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树!!!"<<endl;break;}
/*leave=tree.Showleaves ();
cout<<"***************************"<<endl;
cout<<"叶子结点数为：";
cout<<leave<<endl;*/
cout<<"叶结点为：";
tree.leaves1 ();
cout<<endl;
cout<<"二叉结点为：";
tree.leaves2 ();
cout<<endl;
cout<<"一叉结点为：";
tree.leaves3 ();
cout<<endl<<"***************************"<<endl;break;
case 6:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树*******!!!"<<endl;break;}
depth=tree.Depthoftree();
cout<<"***************************"<<endl;
cout<<"树的深度为："<<depth<<endl;
cout<<endl<<"***************************"<<endl;break;
case 7:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树******!!!"<<endl;break;}
cout<<"***************************"<<endl;
t=tree.Iscomplete() ;
if(t){cout<<"是完全二叉树！"<<endl;}
else{cout<<"不是完全二叉树！"<<endl;}
cout<<endl<<"***************************"<<endl;break;
case 8:break;
default:
cout<<"警告!命令错误,请重新输入!!!"<<endl;
}
if(select == 8)
cout<<"系统已经退出!"<<endl;
break;
}
exit(1);

8. 数据结构二叉树定义问题

你玩过跳棋吗？就是在跳棋的10个格子里，下面4个往上面3个然后两个最后一个，金字塔状，你想那样也是有序树，只是这个数其中的节点共享了同一个子节点

这样的树是有序的，但不是二叉树，因为二叉树每个节点只能有一个前驱结点。。

9. 二叉树的程序设计结点的增加删除修改查询

这样的代码网上有很多，这里我再VS运行成功的C语言代码供参考吧。也是自己学习二叉树创建查找的资料。

/*************************************************************************
这是一个二叉查找树，实现了以下操作：插入结点、构造二叉树、删除结点、查找、
查找最大值、查找最小值、查找指定结点的前驱和后继。上述所有操作时间复杂度
均为o(h),其中h是树的高度
注释很详细，具体内容就看代码吧
*************************************************************************/
#include<stdio.h>
#include<stdlib.h>
//二叉查找树结点描述
typedefintKeyType;
typedefstructNode
{
KeyTypekey;//关键字
structNode*left;//左孩子指针
structNode*right;//右孩子指针
structNode*parent;//指向父节点指针
}Node,*PNode;
//往二叉查找树中插入结点
//插入的话，可能要改变根结点的地址，所以传的是二级指针
voidinseart(PNode*root,KeyTypekey)
{
//初始化插入结点
PNodep=(PNode)malloc(sizeof(Node));
p->key=key;
p->left=p->right=p->parent=NULL;
//空树时，直接作为根结点
if((*root)==NULL){
*root=p;
return;
}
//插入到当前结点（*root）的左孩子
if((*root)->left==NULL&&(*root)->key>key){
p->parent=(*root);
(*root)->left=p;
return;
}
//插入到当前结点（*root）的右孩子
if((*root)->right==NULL&&(*root)->key<key){
p->parent=(*root);
(*root)->right=p;
return;
}
if((*root)->key>key)
inseart(&(*root)->left,key);
elseif((*root)->key<key)
inseart(&(*root)->right,key);
else
return;
}
//查找元素,找到返回关键字的结点指针，没找到返回NULL
PNodesearch(PNoderoot,KeyTypekey)
{
if(root==NULL)
returnNULL;
if(key>root->key)//查找右子树
returnsearch(root->right,key);
elseif(key<root->key)//查找左子树
returnsearch(root->left,key);
else
returnroot;
}
//查找最小关键字,空树时返回NULL
PNodesearchMin(PNoderoot)
{
if(root==NULL)
returnNULL;
if(root->left==NULL)
returnroot;
else//一直往左孩子找，直到没有左孩子的结点
returnsearchMin(root->left);
}
//非递推查找最小关键字
PNodesearchMin2(PNoderoot)
{
if(root==NULL)
returnNULL;
while(root->left!=NULL)
root=root->left;
returnroot;
}
//查找最大关键字,空树时返回NULL
PNodesearchMax(PNoderoot)
{
if(root==NULL)
returnNULL;
if(root->right==NULL)
returnroot;
else//一直往右孩子找，直到没有右孩子的结点
returnsearchMax(root->right);
}
//查找某个结点的前驱
PNodesearchPredecessor(PNodep)
{
//空树
if(p==NULL)
returnp;
//有左子树、左子树中最大的那个
if(p->left)
returnsearchMax(p->left);
//无左子树,查找某个结点的右子树遍历完了
else{
if(p->parent==NULL)
returnNULL;
//向上寻找前驱
while(p){
if(p->parent->right==p)
break;
p=p->parent;
}
returnp->parent;
}
}
//查找某个结点的后继
PNodesearchSuccessor(PNodep)
{
//空树
if(p==NULL)
returnp;
//有右子树、右子树中最小的那个
if(p->right)
returnsearchMin(p->right);
//无右子树,查找某个结点的左子树遍历完了
else{
if(p->parent==NULL)
returnNULL;
//向上寻找后继
while(p){
if(p->parent->left==p)
break;
p=p->parent;
}
returnp->parent;
}
}
//根据关键字删除某个结点,删除成功返回1,否则返回0
//如果把根结点删掉，那么要改变根结点的地址，所以传二级指针
intdeleteNode(PNode*root,KeyTypekey)
{
PNodeq;
//查找到要删除的结点
PNodep=search(*root,key);
KeyTypetemp;//暂存后继结点的值
//没查到此关键字
if(!p)
return0;
//1.被删结点是叶子结点，直接删除
if(p->left==NULL&&p->right==NULL){
//只有一个元素，删完之后变成一颗空树
if(p->parent==NULL){
free(p);
(*root)=NULL;
}else{
//删除的结点是父节点的左孩子
if(p->parent->left==p)
p->parent->left=NULL;
else//删除的结点是父节点的右孩子
p->parent->right=NULL;
free(p);
}
}
//2.被删结点只有左子树
elseif(p->left&&!(p->right)){
p->left->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if(p->parent==NULL)
*root=p->left;
//删除的结点是父节点的左孩子
elseif(p->parent->left==p)
p->parent->left=p->left;
else//删除的结点是父节点的右孩子
p->parent->right=p->left;
free(p);
}
//3.被删结点只有右孩子
elseif(p->right&&!(p->left)){
p->right->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if(p->parent==NULL)
*root=p->right;
//删除的结点是父节点的左孩子
elseif(p->parent->left==p)
p->parent->left=p->right;
else//删除的结点是父节点的右孩子
p->parent->right=p->right;
free(p);
}
//4.被删除的结点既有左孩子，又有右孩子
//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)
//删掉后继结点,后继结点的值代替该结点
else{
//找到要删除结点的后继
q=searchSuccessor(p);
temp=q->key;
//删除后继结点
deleteNode(root,q->key);
p->key=temp;
}
return1;
}
//创建一棵二叉查找树
voidcreate(PNode*root,KeyType*keyArray,intlength)
{
inti;
//逐个结点插入二叉树中
for(i=0;i<length;i++)
inseart(root,keyArray[i]);
}
intmain3(void)
{
inti;
PNoderoot=NULL;
KeyTypenodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};
create(&root,nodeArray,11);
for(i=0;i<2;i++)
deleteNode(&root,nodeArray[i]);
printf("%d
",searchPredecessor(root)->key);
printf("%d
",searchSuccessor(root)->key);
printf("%d
",searchMin(root)->key);
printf("%d
",searchMin2(root)->key);
printf("%d
",searchMax(root)->key);
printf("%d
",search(root,13)->key);
system("pause");
return0;
}

10. C语言二叉树定义问题

typedef struct BTREE
{
int data;
struct BTREE *left;
struct BTREE *right;
}
BTNode,*BTree;
---------------------------
这段是定义一个二叉树结构体BTREE~

BTree root;
---------------------------
这是二叉树的根结点~~

BTNode stack[50];
---------------------------
这是用来存储BTNode型结点的栈~~

BTNode popstack[50];
---------------------------
这是用来存储弹出栈的BTNode型结点的栈~

希望能帮上你~~