二叉树基本概念
二叉树的存储结构struct node { typename data; //数据域 node* lchild; //指向左子树根结点的指针 node* rchild; //指向右子树结点的指针 }
由于在二叉树建树前根结点并不存在,因此其结点一般设为NULL:
node *root = NULL;
而如果需要新建结点(例如往二叉树插入结点的时候),就可以使用下面的函数:
//生成一个新结点,v为结点权值 node* newNode(int v) { node* Node = new node; //申请一个node型变量的地址空间 Node->data = v; //结点权值为v Node->lchild = Node->rchild = NULL; //没有左右孩子 return Node; //返回新建结点的地址 }二叉树的查找、修改
void search(node* root, int x, int newdata) { if(root == NULL) return; //空树,死胡同(递归边界) if(root->data == x) { root->data = newdata; //找到数据域为x的结点然后修改成newdata } search(root->lchild, x, newdata); //往左子树搜索 search(root->rchild, x, newdata); //往右子树搜索 }二叉树结点的插入
//insert函数将在二叉树中插入一个数据域为x的新结点 //注意根结点指针root要使用引用,否则插入不会成功 void insert(node* &root, int x) { if(root == NULL) { root = newNode(x); return; } if(由题意,x应该插入左子树) { insert(root->lchild, x); //往左子树搜索 }else { insert(root->rchild, x); //往右子树搜索 } }
在上述代码中,很关键的一点是根结点root使用了引用&,即在函数中修改root会直接修改原变量。这么做的原因是,在insert函数中新建了结点,并把新结点的地址赋给了当层的root,如果不使用引用,root = new node这个语句对root的修改就无法作用到原变量,也就不能把新结点接到二叉树上面。
那为什么search函数无需引用呢?这是因为search函数修改的是root指向的内容而不是root本身。
那么,如何判断是否要加引用呢?一般来说,如果函数中需要新建结点,即对二叉树的结构做出修改,就需要加引用;如果只是修改当前已有结点的内容,或仅仅是遍历树,就不用加引用。
最后注意,务必使新结点的左右指针域为NULL,表示这个新结点暂时没有左右子树。
二叉树的创建//二叉树的建立 node* Create(int data[], int n) { node* root = NULL; //新建根结点 for(int i = 0; i < n; i ++) { insert(root, data[i]); //插入数据域 } return root; //返回根结点 }完全二叉树的存储结构
完全二叉树可以采用更简单的存储方法。
对完全二叉树当中的任何一个结点(设编号为x),其左孩子的编号一定为2x,右孩子的编号一定为2x+1。也就是说,完全二叉树完全可以通过建立一个大小为的数组来存放所有的信息,其中k是树的最大高度,且1号位必须为根结点(想想为什么不是0号位),这样,对于一个结点,它的左右孩子的编号都可以通过计算得到。
事实上,如果不是完全二叉树,也可以将其视作完全二叉树,即把空结点也进行实际的编号工作。但这样做会使整条树是一条链的时候空间消耗巨大(对k个结点需要个元素的数组),因此不常采用。
除此之外,该数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列(以后会说,先记住结论)。而判断某个结点是否为叶结点的标志为:该结点(记下标为root)的左子结点的编号root*2大于结点总个数n(想一想为什么不需要判右边结点);判断某个结点是否为空结点的标志为:该结点下标root大于结点总个数n。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)