后序遍历的第k个节点

数据结构_输出二叉树中先序、中序、后序遍历方式中第k个节点的数据

千次阅读 2014-07-20 14:20:10

//输出先序遍历中第k个节点的值 int n =0; void Travel(BTNode *T, int k) { if(NULL != T) { if(++n == k) { printf("第%d个节点的数据为:%c\n",k,T->data);

//输出先序遍历中第k个节点的值

int n =0;

void Travel(BTNode *T, int k)

{

     if(NULL != T)

     {

             if(++n == k)

             {

                    printf("第%d个节点的数据为:%c\n",k,T->data);

                    return ;

             }

             

             Travel(T->lchild,k);

             Travel(T->rchild,k);

             

     }

     

}   








//输出中序遍历中第k个节点的值

int n =0;

void Travel(BTNode *T, int k)

{

     if(NULL != T)

     {

            

             Travel(T->lchild,k);


           if(++n == k)
             {
                    printf("第%d个节点的数据为:%c\n",k,T->data);
                    return ;
             }
             

             Travel(T->rchild,k);

             

     }

     

}   









//输出后序遍历中第k个节点的值

int n =0;

void Travel(BTNode *T, int k)

{

     if(NULL != T)

     {

           

             

             Travel(T->lchild,k);

             Travel(T->rchild,k);


           if(++n == k)
             {
                    printf("第%d个节点的数据为:%c\n",k,T->data);
                    return ;
             }

             

     }

     

}

收起

展开全文

c语言数据结构源代码 c

数据结构-------二叉树的基本性质（先序遍历、中序遍历、后序遍历、层序遍历、求节点个数等）

2020-04-12 11:48:58

文章目录二叉树的特征二叉树的重要性质二叉树的创建二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历二叉树的层序...在二叉树的第i层上至多有 2^(i-1)个节点 深度为k的二叉树上至多含有2^k-1(k>=1)个节点 对...


文章目录
二叉树的定义
二叉树的特征
二叉搜索树
平衡二叉树
二叉树的重要性质
二叉树的创建
二叉树的先序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的层序遍历
二叉树的深度
二叉树的节点数目
复制二叉树
二叉树叶子节点的数目
全部代码
测试结果

二叉树的定义
一个有穷的节点集合
二叉树的特征

每个节点最多只有两棵子树
每棵子树有左右之分，其次序不能颠倒，是有序数

二叉搜索树
定义：一棵二叉树，可以为空；如果不为空，满足以下性质：

非空左子树的所有值小于其根节点的键值
非空右子树的所有值大于其根节点的键值
左右子树都是搜索二叉树

平衡二叉树
空树或者任一节点左、右子树高度差的绝对值不超过1
二叉树的重要性质

在二叉树的第i层上至多有 2^(i-1)个节点
深度为k的二叉树上至多含有2^k-1(k>=1)个节点
对任意一棵二叉树，若它含有n0个叶子节点、n2个度为2的节点，则必存在n0 = n2+1
具有 n 个结点的完全二叉树的深度为 [ log2n]+1  ([ log2n]：表示以2为底，对n取对数，并向下取整）
若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：

(1) 若 i=1，则该结点是二叉树的根，无双亲；否则，编号为 [i/2] 的结点为其双亲结点；

(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；

(3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。

二叉树的创建
Node * CreatBiTree() {
	//先序创建二叉树
	char ch;
	scanf("%c", &ch);
	if (ch=='#')
	{
		return NULL;
	}
	else {
		Node *T = (Node *)malloc(sizeof(Node));
		T->data = ch;
		T->lchild = CreatBiTree();
		T->rchild = CreatBiTree();
		return T;
	}
}


二叉树的先序遍历
void PreOrderTraverse(Node *T) {
	//先序遍历
	if (T)
	{
		printf("%2c ", T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}


二叉树的中序遍历
void MidOrderTraverse(Node *T) {
	//中序遍历
	if (T)
	{
		
		MidOrderTraverse(T->lchild);
		printf("%2c ", T->data);
		MidOrderTraverse(T->rchild);
	}
}


二叉树的后序遍历
void LaOrderTraverse(Node *T) {
	//后序遍历
	if (T)
	{

		LaOrderTraverse(T->lchild);
		LaOrderTraverse(T->rchild);
		printf("%2c ", T->data);
	}
}


二叉树的层序遍历
/**
层序遍历要结合队列的出队，入队来写*/
void LevelOrderTraversal(Queue *q, struct node *root) {
	//层次遍历，边进边出
	struct node *temp;
	Push(q, root);
	while (!empty(q))
	{
		temp = Pop(q);
		printf("%2c", temp->data);
		if (temp->lchild)
		{
			Push(q, temp->lchild);
		}
		if (temp->rchild)
		{
			Push(q, temp->rchild);
		}
	}


二叉树的深度
int countDepth(Node *t) {
	//求二叉树的深度
	if (t==NULL)
	{
		return 0;
	}
	else if (t->lchild == NULL && t->rchild == NULL) {
		return 1;
	}
	else {
		int depth1 = countDepth(t->lchild) ;
		int depth2 = countDepth(t->rchild) ;
		return depth1 > depth2 ? depth1 + 1 : depth2 + 1;
	}
}


二叉树的节点数目
int countNode(Queue *q, struct node *root) {
	//通过对队列的遍历求节点数目

	struct node *temp;
	Push(q, root);
	int num = 0;
	while (!empty(q))
	{
		temp = Pop(q);
		num++;
		if (temp->lchild)
		{
			Push(q, temp->lchild);
		}
		if (temp->rchild)
		{
			Push(q, temp->rchild);
		}
	}
	return num;
}




复制二叉树
//二叉树的复制
Node *CopyTree(Node *T) {
	Node *t = (Node *)malloc(sizeof(Node));
	if (T == NULL) {
		t = NULL;
		return t;
	}
	else {
		t->data = T->data;
		t->lchild = CopyTree(T->lchild);
		t->rchild = CopyTree(T->rchild);
		return t;
	}
}

二叉树叶子节点的数目
int CountLeaf(Node *t) {//叶子节点的数目
	static int num = 0;
	if (t == NULL) {
		return 0;
	}
	else {
		if (t->lchild==NULL&&t->rchild==NULL)
		{
			num++;
		}
		CountLeaf(t->lchild);
		CountLeaf(t->rchild);
	}
	return num;
}




//统计叶子节点
void CountLeaf(Node *T) {
	if (T == NULL) {
		return ;
	}

	else {
		if (T->lchild == NULL && T->rchild == NULL) {
			printf("%2c ", T->data);
		}
		CountLeaf(T->lchild);
		CountLeaf(T->rchild);
	}
}

全部代码
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<malloc.h>
#define max 100
typedef struct node {
	char data;
	struct node *lchild, *rchild;
}Node;
typedef struct queue {
	struct node * num[max];
	int front;
	int rear;
}Queue;
Queue * initilize() {
	Queue *q = (Queue*)malloc(sizeof(Queue));
	q->front = 0;
	q->rear = 0;
	return q;//初始化队列
}
void Push(Queue *q, struct node *root) {
	q->num[++q->rear] = root;//入队
}
struct node *Pop(Queue *q) {
	return q->num[++q->front];//出队
}
bool empty(Queue *q) {
	return q->front == q->rear;//判断队列是否为空
}
Node * CreatBiTree() {
	//先序创建二叉树
	char ch;
	scanf("%c", &ch);
	if (ch=='#')
	{
		return NULL;
	}
	else {
		Node *T = (Node *)malloc(sizeof(Node));
		T->data = ch;
		T->lchild = CreatBiTree();
		T->rchild = CreatBiTree();
		return T;
	}
}
void PreOrderTraverse(Node *T) {
	//先序遍历
	if (T)
	{
		printf("%2c ", T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}
void MidOrderTraverse(Node *T) {
	//中序遍历
	if (T)
	{
		
		MidOrderTraverse(T->lchild);
		printf("%2c ", T->data);
		MidOrderTraverse(T->rchild);
	}
}
void LaOrderTraverse(Node *T) {
	//后序遍历
	if (T)
	{

		LaOrderTraverse(T->lchild);
		LaOrderTraverse(T->rchild);
		printf("%2c ", T->data);
	}
}
void LevelOrderTraversal(Queue *q, struct node *root) {
	//层次遍历，边进边出
	struct node *temp;
	Push(q, root);
	while (!empty(q))
	{
		temp = Pop(q);
		printf("%2c", temp->data);
		if (temp->lchild)
		{
			Push(q, temp->lchild);
		}
		if (temp->rchild)
		{
			Push(q, temp->rchild);
		}
	}
}
int countDepth(Node *t) {
	//求二叉树的深度
	if (t==NULL)
	{
		return 0;
	}
	else if (t->lchild == NULL && t->rchild == NULL) {
		return 1;
	}
	else {
		int depth1 = countDepth(t->lchild) ;
		int depth2 = countDepth(t->rchild) ;
		return depth1 > depth2 ? depth1 + 1 : depth2 + 1;
	}
}
int countNode(Queue *q, struct node *root) {
	//通过对队列的遍历求节点数目

	struct node *temp;
	Push(q, root);
	int num = 0;
	while (!empty(q))
	{
		temp = Pop(q);
		num++;
		if (temp->lchild)
		{
			Push(q, temp->lchild);
		}
		if (temp->rchild)
		{
			Push(q, temp->rchild);
		}
	}
	return num;
}
int CountLeaf(Node *t) {//叶子节点的数目
	static int num = 0;
	if (t == NULL) {
		return 0;
	}
	else {
		if (t->lchild==NULL&&t->rchild==NULL)
		{
			num++;
		}
		CountLeaf(t->lchild);
		CountLeaf(t->rchild);
	}
	return num;
}
int main() {
	printf("先序遍历输入：");
	Node *T = CreatBiTree();
	printf("先序遍历输出：\n");
	PreOrderTraverse(T);
	printf("\n");
	printf("中序遍历输出：\n");
	MidOrderTraverse(T);
	printf("\n");
	printf("后序遍历输出：\n");
	LaOrderTraverse(T);
	printf("\n");
	printf("层次遍历输出：\n");
	Queue *q = initilize();
	LevelOrderTraversal(q, T);
	printf("\n");
	printf("树的深度为：%d\n", countDepth(T));
	printf("节点的数目为：%d\n", countNode(q,T));
	printf("叶子节点的数目为：%d\n", CountLeaf(T));
}



测试结果

收起

展开全文

求后序遍历序列的第k个结点值（二叉树）

千次阅读 2013-11-02 20:14:44

现输入其扩展二叉树的前序遍历序列，要求建立该二叉树，并输出其后序遍历序列的第k个结点值（假设该值一定存在）。 Input 第一行为一个整数n，表示以下有n组数据，每组数据占两行，第一行为一个整数...

1.题目：





 Problem Description

设有一棵二叉树，其节点值为字符型并假设各值互不相等，采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列，要求建立该二叉树，并输出其后序遍历序列的第k个结点值（假设该值一定存在）。





 Input

第一行为一个整数n，表示以下有n组数据，每组数据占两行，第一行为一个整数k（1<=k<=二叉树中的结点总数），第二行为扩展二叉树的前序遍历序列。




 Output

输出该二叉树后序遍历序列的第k个结点值。




 Sample Input

2
1
AB#D##C##
4
ABD##E##C#F##





 Sample Output

D
F






2.参考代码：

#include <iostream>
using namespace std;

char ans[1111];
int t;
struct BiNode{
	char data;
	BiNode* lchild,* rchild;
};

class BiTree{
private:
	BiNode* root;
	BiNode* Creat();
	void Release(BiNode* root);
public:
	BiTree();
	~BiTree();
	BiNode* GetRoot(){
		return root;
	}
	void PostOrder(BiNode* root);
};

BiNode* BiTree::Creat(){
	BiNode* root=new BiNode;
	char ch;
	cin>>ch;
	if(ch=='#')
		root=NULL;
	else{
		root->data=ch;
		root->lchild=Creat();
		root->rchild=Creat();
	}
	return root;
}

void BiTree::Release(BiNode* root){
	if(root){
		Release(root->lchild);
		Release(root->rchild);
		delete root;
	}
}

BiTree::BiTree(){
	root=Creat();
}

BiTree::~BiTree(){
	Release(root);
}

void BiTree::PostOrder(BiNode* root){
	if(root==NULL)
		return ;
	else{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		ans[t++]=root->data;
	}
}

int main()
{
	int n,x;
	cin>>n;
	while(n--)
	{
		cin>>x;
		BiTree bt;
		BiNode* root=bt.GetRoot();
		bt.PostOrder(root);
		cout<<ans[x-1]<<endl;
		t=0;
	}
	return 0;
}

收起

展开全文

二叉树的前、中、后序遍历（递归和非递归）、层序遍历、深度、叶子节点个数

2016-06-22 20:16:05

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2...


二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

下边的代码：

#pragma once
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
typedef char DataType;

template <class T >
struct BinaryTreeNode
{
public:
	BinaryTreeNode(T value)
		:_value(value)
		, _right(NULL)
		, _left(NULL)
	{}
	T _value;
	BinaryTreeNode<T>* _right;
	BinaryTreeNode<T>* _left;

};

template <class T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;
private:
	BinaryTreeNode<T>* _root;
public:
	BinaryTree()
		:_root(NULL)
	{}
	BinaryTree(char* str)
	{
		_CreateTree(_root, str);
	}
	~BinaryTree()
	{}
	void PrevOrder()
	{
		cout << "前序遍历:	";
		_PrevOrder_R(_root);
		cout << endl;
	}
	void PrevOrder_NR()
	{
		stack<Node*> s;
		if (_root)
			s.push(_root);

		while (!s.empty())
		{
			Node* top = s.top();
			cout << top->_value << " ";
			s.pop();

			if (top->_right)
				s.push(top->_right);
			if (top->_left)
				s.push(top->_left);
		}
	}
	void Inorder_NR()
	{
		stack<Node*> s;
		Node* cur = _root;
		
		while (cur ||!s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			Node* top = s.top();
			cout << top->_value << " ";
			s.pop();

			if (top->_right)
			{
				cur = top->_right;
			}
		}
	}
	void Postorder_NR()
	{
		stack<Node*> s;
		Node* cur = _root;
		Node* prev = NULL;

		while (cur||!s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			Node* top = s.top();
			if (top->_right == NULL || top->_right == prev)
			{
			
				cout << top->_value << " ";
				s.pop();
				prev = top;	
			}
			else 
			{
				cur = top->_right;
			}
		}
	}
	void PostOrder()
	{
		cout << "后序遍历:	";
		_PostOrder_R(_root);
		cout << endl;
	}

	void InOrder()
	{
		cout << "中序遍历:	";
		_InOrder(_root);
		cout << endl;
	}
	void PrevOrder_NonR()
	{
		cout << "前序遍历：" << " ";
		_PrevOrder_NonR();
		cout << endl;
	}
	void Mirror()
	{
		_Mirror(_root);
		cout << endl;
	}
	int LeafSize()
	{
		return _LeafSize(_root);
	}
	int GetKSize(int k)
	{
		return _GetKSize(_root,k);
	}
	int Size()
	{
		return _Size(_root);
	}

	int Depth()
	{
		return _Depth(_root);
	}

	//二叉树的层序遍历
	void LeverOrder()
	{
		queue<Node*> q;
		if (_root == NULL)//没有节点
		{
			return;
		}
		else if (_root->_left == NULL && _root->_right == NULL)//一个节点
		{
			cout << _root->_value << " ";
			return;
		}
		else
		{
			Node* cur = _root;
			q.push(cur);
			while (!q.empty() && cur != NULL)
			{
				Node* front = q.front();
				cout << front->_value << " ";
				q.pop();
				if (front->_left != NULL)
					q.push(front->_left);
				if (front->_right != NULL)
					q.push(front->_right);
			}
			cout << endl;
		}
	}
protected:

	void _CreateTree(BinaryTreeNode<T>*& root, char* &str)//创建二叉树
	{
		if (*str != '\0' && *str != '#')
		{
			root = new BinaryTreeNode<T>(*str);
			_CreateTree(root->_left, ++str);
			if (*str == '\0')
			{
				return ;
			}
			_CreateTree(root->_right, ++str);
		}
	}
	
	void _PrevOrder_R(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
		{
			return;
		}
		else
		{
			cout << root->_value << " ";
			_PrevOrder_R(root->_left);
			_PrevOrder_R(root->_right);
		}
	}


	void _PostOrder_R(BinaryTreeNode<T>* root)//后序遍历 递归
	{
		if (root == NULL)
		{
			return;
		}
		else
		{
			_PostOrder_R(root->_left);
			_PostOrder_R(root->_right);
			cout << root->_value << " ";
		}
	}

	void _InOrder(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
		{
			return;
		}
		else
		{
			_InOrder(root->_left);
			cout << root->_value << " ";
			_InOrder(root->_right);
		}
	}

	void _InOrder_NonR(BinaryTreeNode<T>* root)//中序遍历 非递归
	{
		queue<BinaryTreeNode<T>*> q;
		if (root)
		{
			q.push(root);
		}
		while (!q.empty())
		{
			BinaryTreeNode<T>* front = q.front();
			cout << front->_value << " ";
			q.pop();
			if (front->_left != NULL)
			{
				_LevelOrder(front->_left);
			}
			if (front->_right != NULL)
			{
				_LevelOrder(front->_right);
			}
		}
	}


	void _PrevOrder_NonR()    // 二叉树前序遍历(非递归)
	{
		stack<Node*> s;
		if (_root)  //root 不为空 压栈
		{
			s.push(_root);
		}
		while (!s.empty())
		{
			Node* top = s.top();
			cout << top ->_value<< " ";
			s.pop();
			if (top->_right != NULL) //先压右 后压左
			{
				s.push(top->_right);
			}
			if (top->_left != NULL)
			{
				s.push(top->_left);
			}
		}
	}


	int _GetKSize(BinaryTreeNode<T>* root, int k)//求第K层节点数
	{
		if (root == NULL)
			return 0;
		else if (k == 1)
			return 1;
		else
			return _GetKSize(root->_left, k - 1) + _GetKSize(root->_right, k - 1);
	}
	int _LeafSize(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
			return 0;
		else if (root->_left == NULL&&root->_right == NULL)
			return 1;
		else
			return _LeafSize(root->_left) + _LeafSize(root->_right);
	}
		int _Size(BinaryTreeNode<T>* root)
		{
			if (root == NULL)
			{
				return 0;
			}
			return 1 + _Size(root->_left) + _Size(root->_right);
		}


		int _Depth(BinaryTreeNode<T>* root)
		{
			int leftDepth;
			int rigthDepth;
			if (root == NULL)
			{
				return 0;
			}
			leftDepth = _Depth(root->_left);
			rigthDepth = _Depth(root->_right);
			return 1 + (leftDepth > rigthDepth ? leftDepth : rigthDepth);
		}

};


测试代码：

#include<iostream>
#include"BinaryTree.hpp"
using namespace std;


void Test1()
{
	char str[] = "123##4##56";
	BinaryTree<char> gl(str);
	
	gl.PrevOrder();
	gl.InOrder();
	gl.PostOrder();
	cout << gl.Size() << endl;
	cout << gl.Depth() << endl;
}

void Test2()
{
	char str1[] = "123##4##56";
	BinaryTree<char> g(str1);
	g.PrevOrder_NonR();
	//g.PrevOrder_NR();
	//g.Inorder_NR();
	//cout << endl;
	//g.Postorder_NR();
	//g.LevelOrder_NonR();

	//cout << g.LeafSize() << endl;
	//cout << g.GetKSize(3) << endl;
	//g.PrevOrder();
	g.LeverOrder();
	
}
int main()
{
	Test1();
	Test2();
	return 0;
}

收起

展开全文

二叉树输出先序遍历的第k个节点
千次阅读 2016-03-15 21:30:30
思路：寻找第k个节点无非就是先序遍历一下 void trave(BTNode *p,int k) { int n=0; if(P!=NULL) { ++n; if(k==n) { countdata; return ; } trave(p->lchild,k); trave(p->rchild,k); } } 同样也可以用...
收起
Pre-Post-erous! POJ - 1240 （已知前序和后序遍历求原来树的种类）
2018-08-03 09:26:02
传送门 ...前序遍历序列中的第二个字符x1一定是k叉树根节点的第一棵子树的根节点，那么在后序遍历中，从开始到x1的部分一定是k叉树的第一颗子树的后序遍历序列，将这部分截下来，若第一颗子树的节点个...
收起
tree
剑指offer第二十三题【二叉搜索树的后序遍历序列】c++实现
2015-10-18 22:15:14
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。后序遍历最后一个是根节点,往前找第一个比根节点小的
收起
c语言剑指offer 算法
二叉搜索树的后序遍历序列
2017-08-02 11:44:29
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思路：数组的末尾肯定是树的根从头开始遍历数组找到第一个比根节点...
收起
树的先序，中序，后序遍历
2019-08-03 20:28:08
先序输出:根左右（左子树，右子树） A B D G H E C K F I J 中序输出:（左根右） G D H B E A K C I J F 后序输出:（左右根） G H D E B K J I F C A ...对于后序遍历而言，树的第一个根节点总是最后输出的 ...
收起
【剑指offer】二叉搜索树的后序遍历序列
2020-03-27 09:38:46
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思路递归，因为后序遍历中序列的最后一位是根节点，然后找到序列中第...
收起
剑指offer：二叉树的后序遍历序列
2018-09-14 17:03:21
　输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。时间限制：1秒空间限制：32768K 思路：根据题意，如果已知二叉...
收起
剑指offer 搜索二叉树
剑指 Offer 33. 二叉搜索树的后序遍历序列---递归
2020-08-18 18:08:25
取根节点, 从从左向右遍历数组段, 以第一个大于根节点的元素的索引(k)分割数组段若右子树存在小于根节点的元素则false class Solution { public boolean verifyPostorder(int[] postorder) { if(postorder==...
收起
【剑指offer】面试题 33：二叉搜索树的后序遍历序列
2017-07-18 22:56:24
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。时间限制：1秒空间限制：32768K 热度指数：102891 ...
收起
二叉树的前序、中序和后序遍历（递归和非递归的方法）
千次阅读 2020-02-06 20:09:21
二叉树的前序、中序和后序遍历（递归和非递归的方法）二叉树的基础概念 ...二叉树的第 iii 层至多有 2i−12^{i-1}2i−1 个节点 深度为 kkk 的二叉树至多有 2k−12^k-12k−1 个节点 一颗含有 nnn 个...
收起
前序遍历中序遍历
完全二叉树的前序遍历，中序遍历，后序遍历
千次阅读 2017-02-08 23:04:01
在高度为K的二叉树中，则最多有2的K次方-1个节点（k>0） 3.设一棵二叉树个数为n,则父节点个数n/2。若2i+1这里写代码片 public class MyNode<E>{ MyNode<E> left; MyNode<E> right; int d
收起
【Java数据结构】BST树(二叉搜索树)总结02（前、中、后序遍历，层序遍历）
2019-07-07 16:12:04
4、返回中序遍历第k个节点的值 5、判断一个二叉树是否是BST树，判断一个BST树是否是AVl树 6、BST树的镜像 7、把BST树满足[begin，end]区间的值放在集合中、打印出来 8、判断是否是子树 9、按层打印二叉树 1...
收起
数据结构 JAVA
二叉树及先序遍历二叉树，中序遍历二叉树，后序遍历二叉树
千次阅读 2018-11-07 16:43:24
在二叉树的第i层上最多有2 i-1 个节点 。（i>=1） <2>.二叉树中如果深度为k(有k层),那么最多有2k-1个节点。(k>=1） <3>.若二叉树按照从上到下从左到右依次编号，则若...
收起
输出先序遍历二叉树的第k个节点
千次阅读 2019-06-08 19:03:56
输出先序遍历二叉树的第k个节点 2. 思路分析：因为先序遍历是按照先访问根节点，假如有左孩子的话访问左孩子，有有孩子的话访问右孩子，，所以我们可以在一进入递归方法里面就对访问的节点进行计数，计数之后判断...
收起
实现一个简单的二叉树容器，并且实现中序、先序、后序遍历
2019-03-20 17:57:18
二叉树的第i层上最多有 2^(i-1) 个结点，（i>=1）；深度为k的二叉树最多有 2^k - 1 个结点，（k >=1）；对任何一颗二叉树，如果其终端结点数为N0，度为2的节点数为N2，那有N0 = N2 + 1...
收起
数据结构
二叉树的基本操作、面试题：前、中、后序遍历，创建、销毁二叉树，得到二叉树中叶子节点的个数、第K层结点...
千次阅读 2018-09-03 11:02:21
我们要先搞清楚二叉树的特点：每个结点最多有两颗子树，即二叉树不存在度大于2的结点；二叉树的子树有左右之分，其子树的次序不能颠倒。...若规定根节点的层数为1，则一颗非空二叉树的第i层上最...
收起
Python数据结构之树和二叉树(先序遍历、中序遍历和后序遍历)
2018-03-19 14:54:57
转载自：点击打开链接树树是nn（n≥0n≥0）个结点的有限集。在任意一棵非空树中，有且只有一个根结点。二叉树是有限个元素的集合，该集合或者为空、或者...二叉树的第i层至多有2^{i-1}个结点深度为k的二叉树至多有2^...
收起
Python 先序遍历中序遍历
二叉树的创建，二叉搜索树的创建，（前序，中序，后序遍历）
2020-08-03 09:55:52
第i层最多有2^(i-1)个结点，如果每层都是满的，就是满二叉树。如果只在最后一层缺失，缺失的都在最后，就是完全二叉树。完全二叉树结点数量为k，i>1，父节点为i/2，2i>k，i没有孩子，2i+1>k，i没有右孩子...
收起
一篇文看透二叉树，先序遍历、中序遍历、后序遍历、广度优先、深度优先，java实现
2020-04-30 20:04:42
1 二叉树的定义在计算机科学中，二叉树（英语：Binary tree）是...二叉树的第iii层至多拥有2i−12^{i-1}2i−1个节点；深度为kkk的二叉树至多总共有2k−12^k-12k−1个节点（定义根节点所在深度k0=0k_0=0k0=0)，而...
收起
【Java数据结构】BST树(二叉搜索树)总结04（返回中序遍历 第k个节点的值）
2019-07-07 20:32:51
4、返回中序遍历第k个节点的值 5、判断一个二叉树是否是BST树，判断一个BST树是否是AVl树 6、BST树的镜像 7、把BST树满足[begin，end]区间的值放在集合中、打印出来 8、判断是否是子树 9、按层打印二叉树 ...
收起
BST树 JAVA
先序遍历序列第k节点值，删去以x为根的子树,最近的公共祖先节点,非空二叉树的宽度,求解后序序列,...
2020-12-03 00:48:23
设计算法，求解先序遍历序列第k(1<=k)个节点的值 2.对于树中每个元素为x的节点，删去以它为根的子树，释放相应的空间 3. p和q分别为指向二叉树中的任意两个节点的值，其中数值不会重复,找到离p和q最近的公共祖先...
收起
链表算法数据结构
##数据结构##二叉树的三种遍历，以及求叶子节点，第k层，求树的高度等代码实现
2018-01-07 17:44:09
树：n个有限数据元素的集合结点：包含了数据和指向其他结点的指针结点的度：结点拥有的子节点的个数高度：树当中距根节点最远系欸但的路径长度前序遍历：根左子树右子树中序遍历：左子树根右子树后序遍历：左...
收起
二叉树的的四种遍历先序、中序、后序以及层次遍历
2020-08-14 18:23:06
二叉树的第i层上最多有2^i个节点，i从0开始；深度为k的二叉树上至多有2^(k+1) - 1个节点，k从0开始；当前节点编号为i，则其子节点（如果有）为2i+1和2i+2；完全二叉树叶子节点只在最大两层出现；对于任一节点，...
收起
c++
二叉树的，前/中/后序的遍历（递归，非递归），层序遍历，以及各种应用功能
2017-09-19 21:32:55
① 二叉树中的所有结点 ② 二叉树中所有叶子节点个数 ③ 二叉树的深度（高度） ④ 二叉树中第K层的结点个数以下是代码的具体实现 #include #include #include using namespace std;template <cla
收起
递归
二叉树的前序后序中序遍历（非递归形式）
2019-09-03 14:19:12
首先为大佬献上膝盖：https://blog.csdn.net/Benja_K/article/details/88389039### ...前序和中序均是每个节点经过两次：第一次经过时入栈（若是先序则入栈，并输出该节点），入完后往左子树走；第二次经...
收起

数据结构_输出二叉树中先序、中序、后序遍历方式中第k个节点的数据

数据结构-------二叉树的基本性质（先序遍历、中序遍历、后序遍历、层序遍历、求节点个数等）

文章目录

二叉树的定义

二叉树的特征

二叉搜索树

平衡二叉树

二叉树的重要性质

二叉树的创建

二叉树的先序遍历

二叉树的中序遍历

二叉树的后序遍历

二叉树的层序遍历

二叉树的深度

二叉树的节点数目

复制二叉树

二叉树叶子节点的数目

全部代码

测试结果

求后序遍历序列的第k个结点值（二叉树）

Problem Description

Input

Output

Sample Input

Sample Output

二叉树的前、中、后序遍历（递归和非递归）、层序遍历、深度、叶子节点个数

二叉树输出先序遍历的第k个节点

Pre-Post-erous! POJ - 1240 （已知前序和后序遍历求原来树的种类）

剑指offer第二十三题【二叉搜索树的后序遍历序列】c++实现

二叉搜索树的后序遍历序列

树的先序，中序，后序遍历

【剑指offer】二叉搜索树的后序遍历序列

剑指offer：二叉树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列---递归

【剑指offer】面试题 33：二叉搜索树的后序遍历序列

二叉树的前序、中序和后序遍历（递归和非递归的方法）

完全二叉树的前序遍历，中序遍历，后序遍历

【Java数据结构】BST树(二叉搜索树)总结02（前、中、后序遍历，层序遍历）

二叉树及先序遍历二叉树，中序遍历二叉树，后序遍历二叉树

输出先序遍历二叉树的第k个节点

实现一个简单的二叉树容器，并且实现中序、先序、后序遍历

二叉树的基本操作、面试题：前、中、后序遍历，创建、销毁二叉树，得到二叉树中叶子节点的个数、第K层结点...

Python数据结构之树和二叉树(先序遍历、中序遍历和后序遍历)

二叉树的创建，二叉搜索树的创建，（前序，中序，后序遍历）

一篇文看透二叉树，先序遍历、中序遍历、后序遍历、广度优先、深度优先，java实现

【Java数据结构】BST树(二叉搜索树)总结04（返回中序遍历 第k个节点的值）

先序遍历序列第k节点值，删去以x为根的子树,最近的公共祖先节点,非空二叉树的宽度,求解后序序列,...

##数据结构##二叉树的三种遍历，以及求叶子节点，第k层，求树的高度等代码实现

二叉树的的四种遍历先序、中序、后序以及层次遍历

二叉树的，前/中/后序的遍历（ 递归，非递归），层序遍历，以及各种应用功能

二叉树的前序后序中序遍历（非递归形式）

后序遍历的第k个节点

【Java数据结构】BST树(二叉搜索树)总结04（返回中序遍历第k个节点的值）

二叉树的，前/中/后序的遍历（递归，非递归），层序遍历，以及各种应用功能