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是右子树的指针。