二叉树链表构建和应用

本文最后更新于 2020年4月7日 下午

递归遍历

中序

1
2
3
4
5
6
7
8
9
void inorder(binarytree *T)
{
    if(T != NULL)
    { 
        inorder(T->left);
        cout << T->data << endl;
        inorder(T->right);
    }
}

前序
1
2
3
4
5
6
7
8
9
void preorder(binarytree *T)
{
    if(T != NULL)
    {
        cout << T->data << endl;
        preorder(T->left);
        preorder(T->right);
    }
}

后序遍历同理。

这个算法是以当前节点为基点，先输出当前节点数值，然后再去输出左子树数值，然后再递归输出左子树数值知道NULL，才又递归输出右子树数值。

应用

二叉树构建

如果我们只给出数值和构建顺序，是无法构建二叉树的。例如，给出三个数，然后给出构建顺序是123这样总共有5中构建方法。因此还要把空节点加上才可以构建。空节点的值为-1或@

前序遍历构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void create(binarytree *T)
{
    char c;
    cin >> c;
    if(c == '@')
    {
        T = NULL;
    }
    else
    {
        T = new binarynode;
        if(T == NULL)
        {
            return ;
        }
        T->data = c;
        create(T->left);
        create(T->right);
    }
}

这里是先构造当前节点，如果当前节点不是空节点，那么构造左节点和右节点。如果是，直接空节点返回。

计算叶结点个数

叶节点的特点就是左右子树都是空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int calculate(binarytree *T)
{
    if(!T)//空树
    {
        return 0;
    }
    if(T->left == NULL && T->right == NULL)
    {
        return 1;
    {
    else
    {
        return calculate(T->left) + calculate(T->right);
    }
}

计算节点个数

1
2
3
4
5
6
7
8
9
10
11
int calulate(binarytree *T)
{
    if(!T)
    {
        return 0;
    }
    else
    {
        return 1 + calculate(T->left) + calculate(T->right);
    }
}

计算二叉树高度

1
2
3
4
5
6
7
8
9
10
11
12
13
int counthigh(binarytree *T)
{
    if(T == NULL)
    {
        return 0;
    }
    else
    {
        int m = counthigh(T->left);
        int n = counthigh(T->right);
        return m > n ? m+1 : n+1;
    }
}

它的思想是比较左子树和右子树高度，然后再加上根的高度。

复制二叉树

按前序遍历的方法最好复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
binode* copy(binarytree *T)
{
    if(T == NULL)
    {
        return NULL;
    }
    binode *temp = new node;
    if(!temp)
    {
        exit(overflow);
    }
    temp->data = T->data;
    temp->left = copy(T->left);
    temp->right = copy(T->right);
    return temp;
}

非递归搜索二叉树

非递归构造二叉树主要用到了栈来模拟递归过程。

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
void inorder(binode *T)
{
    binode *p;
    stack<binode*> s;//如果不行就自己构建一个栈
    s.push(T);//初始化
    while(!s.empty())
    {
        while( p == s.gettop() && p != NULL)
        {
            push(p->left);
        }
        s.pop();
        /*因为是push左子树，所以最后先push进一个空然后才会退出循环
        所以要先把这个NULL去掉*/
        if(!s.empty())
        {
            p = s.gettop();
            cout << p->data;
            s.pop();//去掉p节点
            s.push(p->right);
            /*如果p是叶结点，那么push右边也是NULL,内层循环不会执行，然后
            执行pop取点NULL，之后if中又会取出上一层节点继续找右子树*/
            //如果右子树中还有分支，那么会继续这个过程
        }
    }
}

这段程序的含义是先找左节点，然后把中间节点退出去，找右节点，在右节点中重复找左节点。

前序遍历又稍有不同，因为前序遍历是先直接输出根节点，所以根节点就不需要存入栈中，实际栈中存入的是右节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void preorder(binode *T)
{
    stack<binode*> s;
    binode *p = T;
    s.push(NULL);
    while(!s.empty())
    {
        cout << p->data << endl;
        if(!p->right)
        {
            s.push(p->right);
        }
        if(!p->left)
        {
            p = p->left;//进入左子树
        }
        else
        {
            p = s.gettop();
            s.pop();
        }
    }
}

这段代码是先输出根，然后把右子树拖入栈中，进入左子树，如果左子树遍历完了，p->left == NULL,之后就到右子树那边去遍历。

后序遍历更为麻烦，stack要用自己的，设置一个标志位确定现在是左子树还是右子树

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
30
31
32
33
34
35
36
struct stacknode
{
    binode *ptr;
    enum tag{L,R};
}
void postorder(binode *T)
{
    stack s;
    stacknode w;
    binode *p = T;
    do
    {
        while(!p)
        {
            w.ptr = p;
            w.tag = L;
            push(s,w);
            p = p->leftchild;
        }//遍历左子树
        int continue = 1;
        while(continue != 0 && !stackempty(s))
        {
             pop(s,w);
             p = w.ptr;
             switch(w.tag)
             {
                 case L: w.tag = R;//这时算作根节点，根节点为R那么下次就会输出
                      push(s,w);
                      continue = 0;//退出循环
                      p = p->right;
                      break;
                 case R: cout << p->data << endl;
             }
        }
    }while(p != NULL || !stackempty(s));
}
数据结构
二叉树链表构建和应用
https://www.xinhecuican.tech/post/11799.html
作者
John Doe
发布于
2020年3月29日
许可协议