大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

go语言讲解二叉树 golang二叉树层序遍历

完全二叉树叶子节点的算法

设:度为i的结点数为ni,由二叉树的性质可知:

为太和等地区用户提供了全套网页设计制作服务,及太和网站建设行业解决方案。主营业务为成都网站建设、做网站、太和网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!

n0 = n2 + 1……………………①式

n = n0 + n1 + n2……………②式

由①式可得 n2 = n0 - 1,带入②式得:

n0 = (n + 1 - n1)/ 2

由完全二叉树性质可知:

如图,当n为偶数时,n1 = 1, n0 = n / 2

如图,当n为奇数时,n1 = 0,n0 = (n + 1)/2

将两式合并,写作:n0 = ⌊(n+1)/2⌋(向下取整符号不能丢)

扩展资料:

完全二叉树的特点:

1.叶子结点只可能在层次最大的两层上出现。

2.对任一结点,若其由分支下的子孙的最大层次为l,则其左分支下的子孙的最大层次必为l或l+1。

完全二叉树的性质:

1.具有n个结点的完全二叉树的深度为⌊log₂n⌋+1。

2.如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i,有:

(1)如果i=1,则结点i是二叉树的根节点,无双亲;如果i1,则其双亲是结点⌊i/2⌋。

(2)如果2in,则结点i无左孩子;否则其左孩子是结点2i。

(3)如果2i+1n,则结点i无右孩子;否则其右孩子是结点2i+1。

二叉树用C++如何实现?

二叉树是程序应用得比较多的一种结构。它可以反映物体之间的层次结构,还能通过孩子和双亲反映两物体之间某些特殊关系;排序二叉树还能帮助我们进行排序,并因此而提供快速的查找;二叉树基础上的伸展树能不断地优化我们系统的结构。并查集能很好地让进行分类;小根堆能帮助快速找到值最小的结点,它是优先队列的雏形。所有的这些都是以二叉树为基础的。

实现的二叉树的基本功能包括前中后序的递归和非递归访问,求结点个数和叶子结点个数,还有求树高。这些是用C++类实现的。

BTree.h文件(类声明文件)

[cpp] view plain copy

#ifndef BTREE_H  

#define BTREE_H  

struct BTreeNode  

{  

int data;  

BTreeNode *lChild,*rChild;  

};  

class BTree  

{public:  

void setRoot(BTreeNode* r){ root=r;}  

BTreeNode* getRoot(){ return root;}  

//中序遍历(递归)  

void inOrder();  

//中序遍历(非递归)  

void NotReInOrder();  

BTreeNode* createBTree();  

//前序遍历(递归)  

void preOrder();  

//前序遍历(非递归)  

void NotRePreOrder();  

//后序遍历(递归)  

void postOrder();  

//后序遍历(非递归)  

void NotRePostOrder();  

//求结点个数  

int BTreeSize();  

//求叶子结点个数  

int BTreeLeaves();  

//求树高  

int BTreeHeight();  

//层次法求树高  

int layerHeight();  

protected:  

//中序遍历  

void inOrder(BTreeNode*);  

//前序遍历  

void preOrder(BTreeNode*);  

//后序遍历  

void postOrder(BTreeNode*);  

//结点个数  

int BTreeSize(BTreeNode*);  

//叶子结点  

int BTreeLeaves(BTreeNode*);  

//树高  

int BTreeHeight(BTreeNode*);  

private:  

BTreeNode* root;  

};  

#endif  

BTree.cpp(类的实现文件)

[cpp] view plain copy

#include iostream  

#include stack  

#include queue  

#include "BTree.h"  

using namespace std;  

//建立二叉树的算法  

BTreeNode* BTree::createBTree()  

{  

BTreeNode* current=0;  

int val=0;  

cinval;  

//-1的个数比数值的个数多1  

if(val==-1)  

return NULL;  

else  

{  

current=new BTreeNode;  

current-data=val;  

current-lChild=createBTree();  

current-rChild=createBTree();  

return current;  

}  

}  

//利用重载的方法  

void BTree::inOrder()  

{  

inOrder(root);  

coutendl;  

}  

//中序访问二叉树(递归)  

void BTree::inOrder(BTreeNode* r)  

{  

if(r!=0) //是if,而不是while  

{  

inOrder(r-lChild); //递归访问  

coutr-data" ";  

inOrder(r-rChild); //递归访问  

}  

}  

//中序遍历(非递归)  

void BTree::NotReInOrder()  

{  

stackBTreeNode* s;  

BTreeNode* r=getRoot();  

while(!s.empty()||r!=0)  

{  

while(r!=0)  

{  

s.push(r);  

r=r-lChild;  

}  

if(!s.empty())  

{  

r=s.top();  

s.pop();  

coutr-data" ";  

r=r-rChild;  

}  

}  

}  

//重载形式  

void BTree::preOrder()  

{  

preOrder(root);  

coutendl;  

}  

//前序递归访问二叉树(递归)  

void BTree::preOrder(BTreeNode* r)  

{  

if(r!=0) //是if,而不是while  

{  

coutr-data" ";  

preOrder(r-lChild); //递归访问  

preOrder(r-rChild); //递归访问  

}  

}  

//前序遍历(非递归)  

void BTree::NotRePreOrder()  

{  

stackBTreeNode* s;  

BTreeNode* r=getRoot();  

s.push(r);  

while(!s.empty())  

{  

r=s.top();  

s.pop();  

coutr-data" ";  

if(r-rChild!=0)  

s.push(r-rChild);  

if(r-lChild!=0)  

s.push(r-lChild);  

}  

}  

//重载形式  

void BTree::postOrder()  

{  

postOrder(root);  

coutendl;  

}  

//后序遍历(递归)  

void BTree::postOrder(BTreeNode* r)  

{  

if(r!=0) //是if,而不是while  

{  

postOrder(r-lChild); //递归访问  

postOrder(r-rChild); //递归访问  

coutr-data" ";  

}  

}  

//后序非递归访问要定义新的结构体类型  

struct Node  

{  

BTreeNode* tp;  

bool flag;  

};  

//后序遍历(非递归)  

void BTree::NotRePostOrder()  

{  

Node node; //定义Node结构体的一个结点  

stackNode s;  

BTreeNode* r=getRoot();  

while(!s.empty()||r!=0)  

{  

while(r!=0)  

{  

node.tp=r;  

node.flag=0;  

s.push(node);  

r=r-lChild;  

}  

if(!s.empty())  

{  

node=s.top();  

s.pop();  

r=node.tp; //将栈顶的BTreeNode*部分赋给r  

if(node.flag==1)  

{  

coutr-data" ";  

r=0; //表示已经访问了该结点  

}  

else  

{  

node.flag=1;  

s.push(node);  

r=r-rChild;  

}  

}  

}  

}  

//重载形式  

int BTree::BTreeSize()  

{  

return BTreeSize(root);  

}  

//求二叉树结点个数的函数  

int BTree::BTreeSize(BTreeNode* r)  

{  

//二叉树的结点个数为左右子树的高度之和再+1  

if(r==0) return 0;   

else  

return 1+BTreeSize(r-lChild)+BTreeSize(r-rChild);  

}  

//重载形式  

int BTree::BTreeLeaves()  

{  

return BTreeLeaves(root);  

}  

//求二叉树叶子结点个数的函数  

int BTree::BTreeLeaves(BTreeNode* r)  

{  

//当为空时,返回0;当找到叶子时返回1  

if(r==0) return 0;   

else  

if(r-lChild==0r-rChild==0)  

return 1;  

else  

return BTreeLeaves(r-lChild)+BTreeLeaves(r-rChild);  

}  

//重载形式  

int BTree::BTreeHeight()  

{  

return BTreeHeight(root);  

}  

//求二叉树高度的函数  

int BTree::BTreeHeight(BTreeNode* r)  

{  

if(r==0) return 0;  

else  

{  

//二叉树的高度为左右子树的最大者+1  

int lHei=BTreeHeight(r-lChild);  

int rHei=BTreeHeight(r-rChild);  

return (lHeirHei) ? lHei+1:rHei+1;  

}  

}  

//层次遍历求树高需要利用的新结构  

struct LayerBTreeNode  

{  

BTreeNode* ptr;  

int height;  

};  

//层次遍历求高度  

int BTree::layerHeight()  

{  

queueLayerBTreeNode que;  

LayerBTreeNode temp,lTemp,rTemp; //牺牲空间来获得算法的清晰度  

BTreeNode* r=getRoot();  

int hei=1;  

temp.ptr=r;  

temp.height=1;  

que.push(temp); //先将根对应的LayerBTreeNode对象进队  

//不为空时  

while(!que.empty())  

{  

//BTreeNode* btreePtr=0;  

temp=que.front(); //取出队首元素  

que.pop();  

r=temp.ptr;  

//用当前的高度跟取出的队首进行比较  

if(heitemp.height)  

hei=temp.height;  

if(r-lChild!=0||r-rChild!=0)  

{  

//如果它的左右子树不为空,则进队列  

if(r-lChild!=0)  

{  

lTemp.ptr=r-lChild;  

lTemp.height=temp.height+1; //在原来高度基础上加1,再入队列  

que.push(lTemp);  

}  

if(r-rChild!=0)  

{  

rTemp.ptr=r-rChild;  

rTemp.height=temp.height+1;  

que.push(rTemp);  

}  

}  

}  

return hei;  

}

二叉树结点权值

权值就是指的一个节点的权重,比如把二叉树应用在编码中,权重就可以理解为码出现的概率。

树的带权路径长度=所有叶子节点带权路径长度之和,即所有叶子节点的权值乘以该叶子节点所在的层次(第一层为0)之和。

二叉树前序中序后序怎么读

你这里有两个C,我把左边那个当成O来写了

前序:ABOGHDIJCEKLFMN

中序:GOHBIDJAKELCMFN

后序:GHOIJDBKLEMNFCA

数据结构中二叉树的#是什么意思?

二叉树二叉树能够说是人们假想的一个模型,因此,允许有空的二叉树是无争议的。二叉树是有序的,左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定,是因为人们赋予了左孩子和右孩子不同的意义,在二叉树的各种应用中,您将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书,您会发现一个有趣的现象:在二叉树这里,基本操作有计算树高、各种遍历,就是没有插入、删除——那树是怎么建立起来的?其实这很好理解,对于非线性的树结构,插入删除操作不在一定的法则规定下,是毫无意义的。因此,只有在具体的应用中,才会有插入删除操作。

节点结构

数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲,或是资源紧张,建议附加一个双亲指针,这将会给很多算法带来方便,尤其是在这个“空间换时间”的时代。

求大虾讲解清空二叉树的算法 谢谢

可以这样想,

DeleteAllNodes(Node *root)

是清空以 root 为根的子树。也就是释放树上所有节点所占用的内存空间。

显然如果 root == NULL 的话,说明这个子树不存在(或者可以想象成是个空子树),它本来就不占用内存空间,也不可能存在子节点,于是对于这种情况,DeleteAllNodes 可以不做任何处理就返回。

但如果 root != NULL 的话,就说明这是一个实际存在的子树了,最起码 root 这个节点是存在的,占用了内存空间。那么你可以这样做:

1. 释放root的左子树

2. 释放root的右子树

3. 释放root节点占用的空间

这样以root为根的这棵树就整个释放掉了。

所以按照上面的说法,这个递归过程可以简单描述如下:

DeleteAllNodes(Node *root) {

if (root == NULL) { // 空子树,直接返回

return;

}

else { // 非空子树

DeleteAllNodes(root-left); // 删除左子树

DeleteAllNodes(root-right); // 删除右子树

free(root); // 释放根节点

}

}

把这个过程整理一下,就可以重新写成你给出的那段代码的样子,其实结构是一样的。

补充:

楼主说的两次递归是指??

如果是两次调用 DeleteAllNodes,那他们对应的分别是清空二叉树的两颗子树啊。

DeleteAllNodes(root-left); 是删除左子树

DeleteAllNodes(pright); 是删除右子树,pright是右子树的指针。


本文题目:go语言讲解二叉树 golang二叉树层序遍历
网站URL:http://dzwzjz.com/article/dosdggd.html
在线咨询
服务热线
服务热线:028-86922220
TOP