二叉樹運算，通常指對二叉樹進行新建、刪除、遍歷查找等運算。是算法中最常見的基本類型之一。
基本介紹
- 中文名：二叉樹運算
- 常見算法：前序遍歷、中序遍歷、後序遍歷
基本運算,三種遍歷運算,前序遍歷,中序遍歷,後序遍歷,輸出二叉樹,求二叉樹的深度,
基本運算
對於二叉樹有下列基本運算：
（1）建空二叉樹Setnull（BT），置BT為空二叉樹。
（2）求二叉樹的根root（x），求結點x所在二叉樹的根。
（3）求雙親結點parent（BT，x），在二叉樹BT中求結點x的雙親結點。
（4）求左或右孩子結點lchild（BT，x）或rchild（BT，x），在二叉樹BT中求結點x的左孩子結點或右孩子結點。
（5）插入左孩子或右孩子結點int_lchild(BT，x，y)或ins_child（BT，x，y），在二叉樹中，將結點y置為結點x的左孩子或右孩子。
（6）刪除左孩子或右孩子結點del_lchild（BT，x）或del_rchild（BT，x），在二叉樹中，刪除結點x的左孩子或右孩子結點（實際上是刪除x的左子樹或右子樹）。
（7）遍歷二叉樹TRAVERSE（BT），即按某種次序，依次訪問二叉樹中每個結點，且每個結點只訪問一次
三種遍歷運算
前序遍歷
先訪問根結點,再訪問左子樹,最後訪問右子樹的次序訪問二叉樹中所有的結點,且每個結點僅訪問一次.
void preorder(btree *p)
{
if(p!=NULL)
{ printf("%d",p->data);
preorder(p->left);
preorder(p->right);
}
}
中序遍歷
先訪問左子樹,再訪問根結點,最後訪問右子樹的次序訪問二叉樹的所有結點,且每個結點僅訪問一次.
void inorder(btree *p)
{
if(p!=NULL)
{ inorder(p->left);
printf("%d",p->data);
inorder(p->right);
}
}
後序遍歷
先訪問左子樹,再訪問右子樹,最後訪問根結點的次序訪問二叉樹中所有的結點,且每個結點僅訪問一次
void postorder(btree *p)
{
if(p!=NULL)
{ postorder(p->left);
postorder(p->right);
printf("%d",p->data);
}
}
輸出二叉樹
首先輸出根結點,然後再輸出它的左子樹和右子樹.依次輸出的左,右子樹要至少有一個不能為空.
void print(btree *b)
{
if(b!=NULL)
{ printf("%d",b->data);
if(b->left!=NULL||b->right!=NULL)
{ printf("(");
printf(b->left);
if(b->right!=NULL)printf(",");
printf(b->right);
printf(")");
}
}
}
求二叉樹的深度
若一棵二叉樹為空,則其深度為0,否則其深度等於左子樹和右子樹的最大深度加1,即有如下遞歸模型:
depth(b)=0 /*如果b=NULL*/
depth(b)=max(depth(b->left,b->right)+1 /*其它*/
因此求二叉樹深度的遞歸函式如下:
int depth(btree *b)
{
int dep1,dep2;
if(b==NULL)return(0);
else
{ dep1=depth(b->left);
dep2=depth(b->right);
if(dep1>dep2)return(dep1+1);
else return(dep2+1);
}
}
