数据结构（二叉树）１

二叉树：每个节点最多有两棵字数，左子树和右子树

完全二叉树：叶节点只能出现在最下层和次下层，而且最下面一层的结点都集中在该层最左边的若干位置的二叉树。每层节点都完全填满，在最后一层上如果不是满的，则只缺少右边的若干节点。

满二叉树：要么叶子节点，要么节点同时具有左右子树

存储方式：

1）顺序存储: 遍历速度上有优势，但占空间大，是非主流二叉树。二叉树通常以链式存储

typedef char datatype;

typedef struct node{

datatype data;

int lchild, rchild;

int parent;

} Node;

Node tree[Length];

2）链式存储：

typedef char datatype;

typedef struct node{

　　 datatype data;

　　struct node *lchild;

struct node *rchild;

}node;

node *tree;

二叉树的遍历

前序遍历：根节点->左子树->右子树

中序遍历：左子树->根节点->右子树

后序遍历：左子树->右子树->根节点

实现：

问题：

取地址符&

　　int a=0;

　　int *p=&a;

　　int *M=& 0X01000; wrong, 对于一个数值常量，没有地址。变量有地址要有一个存储单元对变量进行标识

引用&

　　int a=0;

　　int &r=a;

new delete 和malloc free: new 是operator， malloc是函数

创建：

void creatBinTree(node * t)
{
char c;
cin>>c;
if(c=='#')
t=NULL;
else
{
// t=(node *) malloc(sizeof(node *));
t=new node;
t->data=c;
creatBinTree(t->lchild);
creatBinTree(t->rchild);
}

}



int main()
{

node * tree1;
creatBinTree(tree1);

visit(tree1);
return 0;
}

错误，tree没有创建成功，因为没有改变tree；

将函数改为：

void creatBinTree(node * &t)

成功

分析：

C++中的值传递，指针传递，引用传递

1）值传递：

　　形参是实参的拷贝，改变形参的值不会影响外部实参的值（如果函数内部需要修改参数，并且不希望这个改变影响其他调用，采用值传递）

2）指针传递：

形参为指向实参地址的指针，当对形参的指向操作时，就相当于对实参本身进行操作。

3）引用传递

形参相当于实参的“别名”，对形参的操作，就是对实参的操作。在引用传递过程中，被调函数的形式参数虽然作为局部变量在栈中开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的地址。被调函数对形参的任何操作都被处理成间接寻址，即通过栈中存放的地址访问主调函数中的实参变量。

void change1(int n)
{

    cout<<"值传递--函数操作地址"<<&n<<endl;
    n++;
    }
void change2(int &n)
{
    cout<<"引用传递--函数操作地址"<<&n<<endl;
    n++;
}

void change3(int *n)
{
    cout<<"指针传递--函数操作地址"<<n<<endl;
    *n=*n+1;
}
int main()
{
    int n=10;
    cout<<"实参的地址"<<&n<<endl;
    change1(n);
    cout<<n<<endl;
    change2(n);
    cout<<n<<endl;
    change3(&n);
    cout<<n<<endl;
    return 0;
}

引用于指针传递的区别：

1）引用被创建的同时必须被初始化（指针可在任何时候初始化）

2）不能有NULL引用，必须有合法的存储单元关联

3）引用一旦初始化，就不能改变引用的关系（指针可以随时改变所指的对象）

指针传递的本质是值传递，传递一个地址值。

1）递归方式访问二叉树：

void visit(node * root)
{
    if(root)
    {
        cout<<root->data<<endl;
        if(root->lchild)
        {
            visit(root->lchild);
        }

        if(root->rchild)
        {
            visit(root->rchild);
        }
    }
}

2）非递归的访问二叉树：

（递归操作遍历过的根节点还要回来，所以需要存起来）-->栈存储

对于前序遍历，优先访问根节点，然后在分别访问左孩子和右孩子。

　　对于任一节点P:

　　1）访问节点P，并将节点P入栈；

　　2）判断节点P的左孩子是否为空，若为空，则取栈顶节点并出栈，将栈顶节点的右孩子置为当前的节点P，看其是否为空，若不为空，则循环1），如为空，则继续出栈。

　　　若左子树不为空，将P的左孩子置为当前的节点P，重复1）

　　3）直到P为NUL并且栈为空

存在栈中是为了倒叙访问右节点

ＡＢＤ入先后入栈，并在入栈时输出，

Ｄ的左孩子为空，将Ｄ出栈，但不输出，将其有孩子作为当前节点，为空，将Ｂ出栈，并将右节点Ｅ作为当前节点，入栈，输出Ｅ。

Ｅ和Ｄ情况相同，类推。。。

void preOrder2(node *root)
{
    stack <node*>s;
    node * p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            cout<<p->data<<endl;
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }

}

中序遍历为出栈的时候再输出

后序遍历稍稍复杂

数据结构 （二叉树）１

数据结构（二叉树）１