二叉树的基本运算

二叉树的基本运算

上一讲我们已经讲了创建二叉树,所以这一讲,我们来说一下二叉树的基本运算方法,为以后二叉树的运用打下基础:

(1)查找节点FindNode(*b,x):

在二叉树b中寻找data域值为x的节点,并返回指向该节点的指针

(2)找孩子节点LchildNode§和Rchild-Node§:

分别求二叉树中节点*p的左孩子节点和右孩子节点.

(3)求高度BTNodeDepth(*b):

求二叉树b的高度.若二叉树为空,则其高度为0;否则,其高度等于左子树和右子树中的最大高度加一.

(4)输出二叉树DispBTNode(*b):

以括号表示法输出一颗二叉树.

如上图,就是我们举的例子:

我们定义的二叉树节点结构如下:

typedef struct node
{
	ElemType data;
    struct node *lchild,*rchild;
}BTNode;
1
2
3
4
5

(1)查找节点 FindNode(*b,x)

•找到值为x的节点后返回节点指针,否则返回NULL

•用递归算法,采用"根-左子树-右子树"的顺序,查找值为x的节点.

查找思路:

我们先在同一层级上查找,因为我们每次都是处理 根、左、右节点,在同一层级上进行处理,至于同一层级的节点还有子树 , 我们就直接让他调用自身 , 我们先认为,他能够完成任务,因为每次重新调用我们都是把传入的节点当成一个树来进行操作,所以自然会返回我们想要的结果,我们目前要构建的就是当我们面对一颗传入的树,如何处理好其同一层级的节点.

①首先我们传入要查找的树根和要查找的值

BTNode *FindNode(BTNode *b,ElemType x)
{    
1
2

②然后我们定义每次查找对比的指针的节点

BTNode *p;
1

③如果传入的树,此时是空,说明我们什么也查找不到,就返回空,如果根结点就是要找的x,就返回其指针

if(b==NULL)
    return NULL;
else if(b->data==x)
    return b;
1
2
3
4

④如果根节点不是, 那就看其左子树和右子树有没有所要找的节点了,没有则返回空即可

else
{
    //看左子树返回的值有没有所要找的节点
	P=FindNode(b->lchild,x);
    //返回的不是空,就说明找到了
    if(p!=NULL)
    {
    	retrun p;
    } 
    //不然就是没找到,接着去找右子树,不管找不找得到,都返回即可,找到了返回其指针,找不到返回空
    else
    {
    	return FindNode(b->rchild,x);
    }          
}   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(2)找孩子节点LchildNode§和RchildNode§

•直接返回 *p节点的左孩子或右孩子节点的指针.

思路:我们构建的时候,就已经定义好了左孩子节点和右孩子节点,所以我们直接调用即可

//左孩子
BTNode *LchildNode(BTNode *p)
{
	return p->lchild;
}    
//右孩子
BTNode *RchildNode(BTNode *p)
{
	return p->rchild;
}   
1
2
3
4
5
6
7
8
9
10

(3)求高度*BTNodeDepth(b)

• 二叉树的高度的递归模型f()

思路:

把同一层级的高度算出来,每递归返回一层,我们的高度都在原来基础上增1,因为我们是求树的高度,也就是最大高度,所以需要把左子树和右子树的高度做比较.至于左子树和右子树的高度怎么算,调用自身即可(其有可看成下一层级的子树)

下面开始代码实现:

//传入要求高度的树
int BTNodeDepth(BTNode *b)
{
	//定义本层级左子树和右子树的高度;
	int lchilddep,rchilddep;
    //根节点为空,则返回0
    if(b==NULL)
    {
    	return(0);
    }
    else
    {
    	//求左子树的高度
        lchilddep=BTNodeDepth(b->lchild);
        //求右子树的高度
        rchilddep=BTNodeDepth(b->rchild);
        //返回左子树和右子树较大的高度即可,在其基础上增一(因为要带上根节点)
        return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);
    }       
}   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

(4)输出二叉树*DispBTNode(b)

•用括弧表示法输出二叉树.

•对于非空二叉树b

​ • 先输出其元素值

​ • 当存在左孩子或右孩子节点时

​ ①输出一个“（”符号

​ ②递归处理左子树

​ ③输出一个“，”符号

​ ④递归处理右子树

​ ⑤最后输出一个“）”符号

代码思路： 我们其实还是在同一层级上先构建一层节点，然后再递归调用输出其子树

下面开始代码构建：

//传入二叉树的根节点
void DispBTNode(BTNode *b)
{
	//先判断根节点是否为空,为空则跳出即可
    if(b!=NUll)
    {
    	//不为空,就先把头结点输出
        printf("%c",b->data);
        //如果接下来根节点还有孩子的话,最起码我们需要先输出一对括号
        if(b->lchild!=NULL||b->rchild!=NULL)
        {
        	printf("(");	//同一层级的左括号
            //接着我们把其左子树或右子树输出即可
            //先输出左子树,就是把左子树当做一个独立的树输出,因为我们已经在其外层套了括号
            DispBTNode(b->lchild);
            //接着看此层级是否有右子树,有的话,就输出个逗号,没有的话,就输出逗号加"#"号
            if(b->rchild!=NULL)
            {
            	printf(",");
                DispBTNode(b->rchild);
            }
            else
            {
            	printf(",#");
            }
            printf(")");	//同一层级的右括号
        }
    }
}    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29