二叉樹增刪改查方法定義在哪裡

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型結點的棧~

希望能幫上你~~