数据结构学习

四、树

所有的二叉链表都基于二叉树结点的基本定义

class BinTreeNode
{
	public:
		int data;
		BinTreeNode *leftChild;
		BinTreeNode *rightChild;
		BinTreeNode(T n,BinTreeNode *l=NULL,BinTreeNode *r=NULL)
		{
			leftChild=l;
			rightChild=r;
		}
};

1、最关键也是最基础的一道题：
 

5、统计二叉树的宽度，即在二叉树的各层上，具有结点数最多的那一层上的结点总数
先前序遍历求出每一层的宽度，再求出最大宽度，即树的宽度

每一次递归时都会碰到一个结点，每碰到一个节点就在对应位置的数组上++，因此需要一个level来计数这是第几层

这些都是基于root指向的二叉树已经建立的前提之下写出来的

void levelNumber(BinTreeNode *root,int a[],int level)
{
//level通过主函数调用的时候给值，给定的初值肯定是0
    if(root!=NULL)
    {
        a[level]++;
        levelNumber(root->leftChild,a[],level+1);
        levelNumber(root->rightChild,a[],level+1);
    }
}


//这样就可以了，每层的宽度都存储在了a[]中，只需要再比较各层的宽度即可
int width(BinTreeNode *root)
{
    int n;
    
    levelNumber(root,a,0)  //此时数组a中已经存放了所有层次的宽度
    wid=a[0];
    for(int i=0;i<)
    {
        if(a[i]>wid) wid=a[i];
    }    
    return wid;
}

6、从以t为根的二叉树中删去所有叶结点

//若二叉树非空且当前结点既是根结点也是叶结点，直接删除
//否则递归在其左右子树中删除其中的叶结点。注意参数表中引用参数t的使用
//叶结点或空树是递归到底层的情况
//对于上层的子树，总是先做递归语句、
void defoliate(BinTreeNode *root)
{
    if(root==NULL) return;
    if(root->leftChild==NULL&&root->rightChild==NULL)
    {
        delete root;
        root=NULL;
    }
    else
    {        
        defoliate(root->leftChild);
        defoliate(root0>rightChild);
    }
}

7、计算以t为根的二叉树中指点结点*p所在层次

void Level(BinTreeNode *root,BinTreeNode *p,int level)
{
    if(root==NULL) return;
    if(root==p) return level;
    Level(root->leftChild,p,level+1);
    Level(root->rightChild,p,level+1);
}

8、计算以t为根的二叉树中各结点中的最大元素的值

void Preorder_Max(BinTreeNode *root,int &max)
{
    if(root==NULL) return;
    if(root->data>max) max=root->data;
    Preorder_Max(root->leftChild,max);
    Preorder_Max(root->rightChild,max);        
}

9、以前序次序输出一颗二叉树所有结点的数据值以及结点所在层次

void Preorder(BinTreeNode *root,int level)
{
    cout<<root->data<<" "<<level;
    Preorder(root->leftChild,level+1);
    Preorder(root->rightChild,level+1);
}

10、已知一棵具有n个结点的完全二叉树被顺序存储于一维数组的T[n]，试编写一个算法打印出编号为i的结点的父结点和所有子女

void printParent_Child(int T[],int i,int n,bool flag)
{
    if(i>n) return;
    if(!flag)   //相当巧妙的算法，通过flag使得打印父结点的操作只发生一次，后续的递归之中只会cout子女了 
    {
        if(i==0) cout<<"No Parent"<<" "<<cout<<"Child:";
       else cout<<"Parent:"<<cout<<T[(i-1)/2]<<endl<<"Child:"
    }
    flag=1;
    cout<<T[i];
    printParent_Child(T,2*i+1,n,flag);
    printParent_Child(T,2*i+2,n,flag);
}