二叉叉树树树树

二叉叉树树树树

目录

 7-4

 7-3

---

 

 7-4

输入样例:

2
1 1
4 1 4 0 2

输出样例:

1
1
2 4 1
3

 

u1s1这个题目虚节点会不会合法给出我有点不大明白

不知道虚节点下面到底有没有数

概念理解应该也没有问题

完全二叉树：用二维数组记录 且 数组前面部分都能填满的二叉树

中序遍历： 左    根    右

深度: 层数（用数学公式得）应该这里没问题（换底公式）

由pow(2,n)=lay  得到如下公式

int t = (ceil)(log(n +1.0) / log(2.0)) ;//深度

之前还用了这个计算公式

int t = (int)(log(n *1.0) / log(2.0)) +1;//深度

 感觉这个会有问题，但是改了后也不对

思路：

找到最左端子叶（遇到0终止下找）

ps:一开始是从左下角开始找起
   但是如果根节点和左下角的值
   之间有虚节点也会找到错误的开端
   如：1 0 2 3 4 0 6
   于是从根节点开始找最左子叶（遇到0终止）

打印      给标记

返回上一层

检测左右分支是否都被标记

是，一直向上返回至没被标记的分支

否，进入未被标记的分支进入（都是先左子树 后右子树）

终止条件：i=1  （回到根节点）并且i=1已经被标记

代码：

#include
#include
#include
#include
#include
#include
using namespace std;
//string a = "1245367", b = "4251637";
//string a, b;
int T, n;
int a[1010];//数据数组
int b[1010];//标记数组
int i, j, k;
int main()
{
   
    cin >> T;
    while (T--)
    {
        k = 0;//格式控制
        memset(b, 0, sizeof(b));
        memset(a, 0, sizeof(a));

        cin >> n;
        //
        int t = (ceil)(log(n +1.0) / log(2.0)) ;//深度

        for (i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        i = 1;
        int temp = t;
        
        while(a[2*i]!=0)
            i*=2;
        //
        //printf("开始下标：%dn", i);
        //system("pause");
        while (1)
        {

            if (a[i] != 0&&b[i]!=1)// b[i]!=1  写不写没影响貌似
            {
                if (k != 0)
                {
                    printf(" ");
                }
                printf("%d",a[i]);
                b[i] = 1;
                k++;
            }


            if (a[2 * i] != 0 && b[2 * i] == 0)//左孩子未被标记且值非0
            {
                i = 2 * i;
               // continue;
            }
            else if ( a[2 * i + 1] != 0 &&b[2 * i + 1]==0)//右孩子
            {
                //要找右孩子的左叶子
                i = 2 * i + 1;
                while (a[2 * i] != 0&&b[2*i]==0)
                    i = i * 2;

                //continue;
            }
            else//左右都被标记 或 值为0
            {
                i = i / 2;       //返回上一级
                while (b[i] == 1)//上一级被标记 一直返回
                {
                    i = i / 2;   //第一次遇见i=1不会终止
                    if (i == 0)
                        break;//终止
                }
                if (i == 0)
                    break;//终止
            }
        }
        printf("n");
        printf("%dn", temp);

    }
}

有点小难找了，不知道是错在哪里

下面是另一份错误代码 

经过1时转换成搜索左子树模式

但是若是最后一行中间是虚节点

而最右下角是实节点就会被忽略

#include
#include
#include
#include
#include
#include
using namespace std;
//string a = "1245367", b = "4251637";
//string a, b;
int T, n;
int a[1010];//数据数组
int b[1010];//标记数组
int i, j, k;
int main()
{
   
    cin >> T;
    while (T--)
    {
        k = 0;//格式控制
        memset(b, 0, sizeof(b));
        memset(a, 0, sizeof(a));

        cin >> n;
        //
        int t = (int)(log(n * 1.0) / log(2.0)) + 1;//深度
        int num = 0;//节点数
        for (i = 1; i <= n; i++)
        {
            cin >> a[i];
            if (a[i] != 0)
                num++;
        }
        if (n == 1)
        {
            cout << a[1]< 
7-3 
 
 一个很巧妙的方法
 
根据前序遍历特点
 
将前序遍历的数字    看做   中序遍历的数字里面的根节点
 
而当前根节点又将该区间分成两部分
 
如果左边还有数（分支）也就是pos>left2
 
进入左支
 
右边同理
 
都没有数开始打印
 
返回上一层，继续上一层的任务，和常规递归很像，但是更巧妙
 
这题是数值，不好用string
 
#include
#include
#include
#include
#include
using namespace std;
//string a = "1245367", b = "4251637";
//string a, b;
int  a[100], b[100];
void pro_digui(int L1, int R1, int L2, int R2);
int n;
int main()
{

    //cin >> a >> b;
    cin >> n;
    if(n)
    {
        for (int i = 0; i < n; i++)
        {
            //scanf_s("%d", &a[i]);
            cin >> a[i];
        }
        //getchar();
        for (int i = 0; i < n; i++)
        {
            //scanf_s("%d", &b[i]);
            cin >> b[i];
        }
        pro_digui(0, n-1, 0,n-1);
    }


}
void pro_digui(int L1, int R1, int L2, int R2)
{
    int pos = 0;
    int i, j;
    for (i = 0; i < n; i++)
    {
        if (b[i] == a[L1])
        {
             pos = i;
            break;
        }

    }


    if (pos > L2)
    {
        pro_digui(L1 + 1, R1 + pos - L2, L2, pos - 1);
    }
    if (pos < R2)
    {
        pro_digui(L1 + pos - L2 + 1, R1, pos + 1, R2);
    }
    cout << a[L1]<<" ";
}
 
 
 
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5691309.html