一文学会树及二叉树的操作
目录
树的概念及相关术语
二叉树及性质
二叉树的操作
创建二叉树
二叉树的结点个数
叶子结点个数
二叉树的深度
二叉树第k层结点个数
判断一个结点是否在二叉树中
获取一个结点的左孩子，右孩子结点
判断一棵树是否是完全二叉树
给定一棵二叉树，判断它是否是BST树
一、树的定义
一棵树是由n（n>0）个元素组成的有限集合，其中：
（1）每个元素称为结点(node)；
二叉树
二叉树性质
1.在二叉树的第i层上最多有2i-1个结点（i>=1）。
2.深度为k的二叉树至多有2k–1个结点（k>=1）。
4.具有n个结点的完全二叉树的深度k=[log2n]+1
5.对于一棵n个结点的完全二叉树，对任一个结点（编号为i），有：
①如果i=1,则结点i为根，无父结点；如果i>1,则其父结点编号为i/2。
如果2*i>n，则结点i无左孩子（当然也无右孩子，即结点i为叶结点）；否则左孩子编号为2*i。
②如果2*i+1>n，则结点i无右孩子；否则右孩子编号为2*i+1。
1.顺序存储结构
char a[100];
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
2.链式存储结构
typedefstructnode{intdata;struct node *lchild;struct node * rchild;}BTNode,*tree;tree root=NULL;
优点：节约空间
建立一棵二叉树
void pre_crt(tree &bt)//按先序次序输入二叉树中结点的值，生成{charch;ch= getchar( ); //二叉树的单链表存储结构，bt为指向根结点的指针,'$'表示空树if(ch!= '$'){bt= new node; //建根结点bt->data= ch;pre_crt(bt->lchild); //建左子树pre_crt(bt->rchild); //建右子树}else bt= NULL;}
二叉树结点个数
intBTNodeSize(treeroot){if (root == NULL) return 0;return BTNodeSize(root->lchild) + BTNodeSize(root->rchild) + 1;}
二叉树叶子结点个数
intBTNodeLeaf(treeroot){if (root == NULL)return 0;if ((root->lchild==NULL) && (root->rchild==NULL)) return 1;return BTNodeLeaf(root->lchild) +BTNodeLeaf(root->rchild);}
二叉树深度
intBTDepth(pBTNoderoot){if (root == NULL) return 0;intleft = BTDepth(root->lchild);intright = BTDepth(root->rchild);return (left>right)? (left+1) : (right+1);}
判断一个结点是否在二叉树中
tree BTFind(treeroot,intx){tree ret;if (root == NULL || root->data ==x) return root;ret = BTFind(root->lchild,x);if (ret) return ret;ret = BTFind(root->rchild,x);if (ret) return ret;return NULL;}
求k层结点的个数
intBTNodeKLevel(treeroot, int k){if(root == NULL)return0;if(k == 1)return1;returnBTNodeKLevel(root->lchild, k -1)+BTNodeKLevel(root->rchild, k -1);}
获取一个结点的左孩子结点
tree GetBTNodeLeftChild(treeroot,intx) {tree ret =NULL;if (root == NULL){ return NULL; }ret = BTFind(root,x);if (ret->lchild)return ret->lchild;}
获取一个结点的右孩子结点
tree GetBTNodeRightChild(treeroot,intx){tree ret = NULL;if (root == NULL)return NULL;ret = BTFind(root, x);if (ret->rchild)return ret->rchild;}
二叉树某结点的层数
void getNodeLayer(node *root,intx,int layer){if(root ==NULL) return;if(root->data == x){printf(“%d\n”,layer);return;}getNodeLayer(root->lchild,x,layer+1);getNodeLayer(root->rchild,x,layer+1);}
-
判断二叉树棵树是否为搜索二叉树
//中序遍历二叉树，采用递归方法void mid_order(treeroot,vector<char>& v1){if(root == NULL)return;mid_order(root->lchild,v1);//先遍历左子树v1.push_back(root->data); //然后遍历根节点，将值存储在vector中mid_order(root->rchild,v1);//再遍历右子树}boolisValidBST(treeroot){if(root == NULL)returntrue;vector<char> v;mid_order(root,v);int size = v.size();for(inti = 0; i <size - 1 ; ++i){if(v[i] >= v[i +1])//不符合升序，或者存在重复，返回falsereturn false;}//经中序遍历后为无重复的升序序列，则是二叉搜索树return true;}
判断一棵二叉树是否为完全二叉树
借助queue，将各个结点，以层序遍历序列进行入队。
如果发现front为NULL时，表示读取到了一个空结点，若它后面的结点都是NULL，则表示为完全二叉树；
若它后面的结点出现不为NULL的情况，表示为非完全二叉树。
bool BTComplete(tree root) //判断是否是完全二叉树{queue<tree> q;;if (root == NULL)return true;q.push(root);while (!q.empty()){tree f = q.front();;q.pop();if (f == NULL){while (!q.empty()){q.pop();if (q.front()){return false;}}return true;}else{q.push(f->lchild);q.push(f->rchild);}}}
参考书籍《信息学奥赛一本通》
往期精彩回顾