二叉树运算 发表评论(0) 编辑词条

二叉树运算

　　对于二叉树有下列基本运算：
　　（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），即按某种次序，依次访问二叉树中每个结点，且每个结点只访问一次
　　三种遍历运算
　　1.二叉树的前序遍历
　　先访问根结点,再访问左子树,最后访问右子树的次序访问二叉树中所有的结点,且每个结点仅访问一次.
　　void preorder(btree *p)
　　{
　　if(p!=NULL)
　　{ printf("%d",p->data);
　　preorder(p->left);
　　preorder(p->right);
　　}
　　}
　　2.二叉树的中序遍历
　　先访问左子树,再访问根结点,最后访问右子树的次序访问二叉树的所有结点,且每个结点仅访问一次.
　　void inorder(btree *p)
　　{
　　if(p!=NULL)
　　{ inorder(p->left);
　　printf("%d",p->data);
　　inorder(p->right);
　　}
　　}
　　3.后序遍历
　　先访问左子树,再访问右子树,最后访问根结点的次序访问二叉树中所有的结点,且每个结点仅访问一次
　　void postorder(btree *p)
　　{
　　if(p!=NULL)
　　{ postorder(p->left);
　　postorder(p->right);
　　printf("%d",p->data);
　　}
　　}
　　4.输出二叉树
　　首先输出根结点,然后再输出它的左子树和右子树.依次输出的左,右子树要至少有一个不能为空.
　　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(")");
　　}
　　}
　　}
　　5.求二叉树的深度
　　若一棵二叉树为空,则其深度为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);
　　}
　　}