二叉树基础

2024-12-06 技术教程

二叉树：二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。

二叉树节点结构：

structBinaryTreeNode{T_data;//数据BinaryTreeNode<T>*_left;//指向左子树BinaryTreeNode<T>*_right;//指向右子树BinaryTreeNode(constT&d):_data(d),_left(NULL),_right(NULL){}};

二叉树的创建：

Node*_CreateTree(constT*a,size_tsize,size_t&index,constT&invilid){Node*root=NULL;if(index<size&&a[index]!=invilid){root=newNode(a[index]);//创建根节点root->_left=_CreateTree(a,size,++index,invilid);//递归实现左子树root->_right=_CreateTree(a,size,++index,invilid);//递归实现右子树}returnroot;//返回根节点}

前序遍历：

/*前序遍历：根->左子树->右子树*/void_PrevOrder(Node*root){if(root==NULL){return;}cout<<root->_data<<"";//打印根节点数据_PrevOrder(root->_left);//递归遍历左子树_PrevOrder(root->_right);//递归遍历右子树}

中序遍历：

/*中序遍历：左子树->根->右子树*/void_InOrder(Node*root){if(root==NULL){return;}_InOrder(root->_left);//递归遍历左子树cout<<root->_data<<"";//打印根节点数据_InOrder(root->_right);//递归遍历右子树}

后序遍历：

/*后序遍历：左子树->右子树->根*/void_PostOrder(Node*root){if(root==NULL){return;}_PostOrder(root->_left);//递归遍历左子树_PostOrder(root->_right);//递归遍历右子树cout<<root->_data<<"";//打印根节点数据}

层次遍历：

/*层次遍历：第一层->最后一层*/void_LevelOrder(Node*root){queue<Node*>qt;if(root==NULL){return;}qt.push(root);//将根节点压到队列中while(!qt.empty()){/*当根节点的左孩子不为空，就说明这一层还没有完全压入队列中*/if(qt.front()->_left!=NULL){qt.push(qt.front()->_left);//将根节点左子树压到队列中}/*当根节点的右孩子不为空，就说明这一层还没有完全压入队列中*/if(qt.front()->_right!=NULL){qt.push(qt.front()->_right);//将根节点右子树压到队列中}cout<<qt.front()->_data<<"";//依次打印节点qt.pop();//将打印的节点出队列}}

二叉树节点的个数 = 就是左子树节点个数加上右子树节点的个数再加上根节点

size_t_Size(Node*root){if(root==NULL){return0;}return_Size(root->_left)+_Size(root->_right)+1;//左子树节点+右子树节点+根节点}

二叉树的深度 = 左子树 >= 右子树 ? 左子树+1，右子树+1；

size_t_Depth(Node*root){if(root==NULL){return0;}size_tLeftDepth=_Depth(root->_left);size_tRightDepth=_Depth(root->_right);if(LeftDepth>=RightDepth){returnLeftDepth+1;}else{returnRightDepth+1;}}

二叉树叶子节点的个数 = 左子树的叶子节点个数+ 右子树的叶子节点个数

size_t_LeafSize(Node*root){if(root==NULL){return0;}if(root->_left==NULL&&root->_right==NULL)//只有根节点{return1;}return_LeafSize(root->_left)+_LeafSize(root->_right);}

整体代码：

#include<iostream>#include<queue>usingnamespacestd;template<classT>structBinaryTreeNode{T_data;//数据域BinaryTreeNode<T>*_left;//指向左子树BinaryTreeNode<T>*_right;//指向右子树BinaryTreeNode(constT&d):_data(d),_left(NULL),_right(NULL){}};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;//类型重命名，方便后面使用public:BinaryTree():_root(NULL){}BinaryTree(constT*a,size_tsize,constT&invilid):_root(NULL){size_tindex=0;_root=_CreateTree(a,size,index,invilid);}BinaryTree<T>(constBinaryTree&tree){_root=_Copy(tree._root);}BinaryTree&operator=(BinaryTreetree)//现代式写法{swap(_root,tree._root);return*this;}~BinaryTree(){if(_root!=NULL){_Destroy(_root);}}public:voidPrevOrder(){_PrevOrder(_root);cout<<endl;}voidInOrder(){_InOrder(_root);cout<<endl;}voidPostOrder(){_PostOrder(_root);cout<<endl;}voidLevelOrder(){_LevelOrder(_root);cout<<endl;}size_tSize(){return_Size(_root);}size_tDepth(){return_Depth(_root);}size_tLeafSize(){return_LeafSize(_root);}protected:size_t_Size(Node*root){if(root==NULL){return0;}/*左子树节点+右子树节点+根节点*/return_Size(root->_left)+_Size(root->_right)+1;}size_t_Depth(Node*root){if(root==NULL){return0;}size_tLeftDepth=_Depth(root->_left);size_tRightDepth=_Depth(root->_right);if(LeftDepth>=RightDepth){returnLeftDepth+1;}else{returnRightDepth+1;}}size_t_LeafSize(Node*root){if(root==NULL){return0;}if(root->_left==NULL&&root->_right==NULL){return1;}return_LeafSize(root->_left)+_LeafSize(root->_right);}protected:/*前序遍历：根->左子树->右子树*/void_PrevOrder(Node*root){if(root==NULL){return;}cout<<root->_data<<"";//打印根节点数据_PrevOrder(root->_left);//递归遍历左子树_PrevOrder(root->_right);//递归遍历右子树}/*中序遍历：左子树->根->右子树*/void_InOrder(Node*root){if(root==NULL){return;}_InOrder(root->_left);//递归遍历左子树cout<<root->_data<<"";//打印根节点数据_InOrder(root->_right);//递归遍历右子树}/*后序遍历：左子树->右子树->根*/void_PostOrder(Node*root){if(root==NULL){return;}_PostOrder(root->_left);//递归遍历左子树_PostOrder(root->_right);//递归遍历右子树cout<<root->_data<<"";//打印根节点数据}/*层次遍历：第一层->最后一层*/void_LevelOrder(Node*root){queue<Node*>qt;if(root==NULL){return;}qt.push(root);while(!qt.empty()){if(qt.front()->_left!=NULL){qt.push(qt.front()->_left);}if(qt.front()->_right!=NULL){qt.push(qt.front()->_right);}cout<<qt.front()->_data<<"";qt.pop();}}protected:Node*_Copy(Node*root){if(root==NULL){returnNULL;}Node*NewRoot=newNode(root->_data);//创建新的根节点Node*NewCur=NewRoot;NewCur->_left=_Copy(root->_left);NewCur->_right=_Copy(root->_right);returnNewRoot;}void_Destroy(Node*root){if(root==NULL){return;}if(root->_left==NULL&&root->_right==NULL){deleteroot;root=NULL;return;}_Destroy(root->_left);_Destroy(root->_right);}Node*_CreateTree(constT*a,size_tsize,size_t&index,constT&invilid){Node*root=NULL;if(index<size&&a[index]!=invilid){root=newNode(a[index]);//创建根节点root->_left=_CreateTree(a,size,++index,invilid);//递归实现左子树root->_right=_CreateTree(a,size,++index,invilid);//递归实现右子树}returnroot;//返回根节点}protected:Node*_root;//根节点};intmain(){Test();system("pause");return0;}

测试结构：

测试代码：

voidTest(){intarray[10]={1,2,3,'#','#',4,'#','#',5,6};BinaryTree<int>tree(array,10,'#');tree.PrevOrder();tree.InOrder();tree.PostOrder();tree.LevelOrder();BinaryTree<int>tree2(tree);tree2.PrevOrder();BinaryTree<int>tree3=tree2;tree3.PrevOrder();}

测试结果：